かな漢字変換の実装を行なっていて
後ろ向き探索をA*アルゴリズムで行い、n-best解を求めたいのですが
どのように実装すればよろしいのでしょうか。
現在、前向き探索をコスト最小法で行なっていて、
ある文字で終わるノードのコストはわかっています。

できれば、Rubyでの実装法を教えていただけるとありがたいです。
スレ違いでしたら申し訳ございません。