igo-javascript で N-Best解を出力してみた

igo-javascript で N-Best解を出力してみたよ。

http://shogo82148.github.com/igo-javascript/

Igoは前から順番にビタビアルゴリズムで最小コストを求めた後、後ろから最小となるルートを貪欲法でたどっていきます。これは単純な動的プログラミングなので簡単ですが、これからNBest解の求め方がよくわからなかった。

で、いろいろ調べたところ、後ろ向きの検索を貪欲法でなくA*のような検索アルゴリズムにすればよいようです。(そろそろChaIMEについて一言いっておくか - 射撃しつつ前転)

A*検索には「ゴールにたどり着くにはどれくらいのコストがかかるか」を予想するヒューリスティック関数が必要となります。ヒューリスティック関数は何でもいいわけではなく、最適解が出力されることを保証するためには「ヒューリスティック関数≦実際にゴールにたどりつくまでのコスト」という条件を満たさなくてはいけません。(A* - Wikipedia)
ビタビアルゴリズムで求めた最小コストはこの条件にぴったりなので、これをヒューリスティック関数として使うと効率的な検索ができます。最適解が見つかった後も検索を続ければNBest解の出力もできるというわけです。


この検索方法を実装するにあたって、解の候補から最小コストのものを取り出す、という操作をしなくてはなりません。
これを効率的に行うためにヒープ(優先キュー)をJavascriptで実装しました。ライブラリ部分だけ取り出して別レポジトリに上げておいたので見たい方はそちらから。

https://github.com/shogo82148/jsheap


さて、NBest解を使って何をしようか・・・