しばらく非最適探索ばっかりやって来ましたが、ちょっと最適探索に戻ります。
(昨日の記事は夜中1時過ぎに投稿しました。見逃してませんか?)
A* with Lookahead とは、A* のノード展開に 数歩 の Depth First Lookahead (先読み) を追加することで性能を高めるという手法です。
Search Algorithm Triangle
今までIDA*, A*, EHC と色々なアルゴリズムを見てきましたが、これらのアルゴリズムは次のような図に抽象的に表すことが出来ます(Pearl 1984 より)。横軸$R$は やり直しが効く意思決定 の割合、縦軸$S$は 可能な選択肢のうち実際に検証される選択肢 の割合を指します。右上の BestFirstは、 グラフ探索では**$A^＊$**に相当します。また、Backtrackingは IDA*に相当します。Hill climbing はそのまま山登り法です。
なお、Pearl 1984 というのは、2011 年にチューリング賞を受賞したJudea Pearlが書いた探索の教科書です。
Pearl 1984 では、これらのスペクトラムの中間に位置する様々な ハイブリッドアルゴリズム の可能性に言及しています。たとえば、BF-BT (BestFirst - BackTracking) の例として、下のような図を描いています。
A* with Lookahead
Stern, R. T., Kulberis, T., Felner, A., & Holte, R. (2010, March). Using Lookaheads with Optimal Best-First Search. In Twenty-Fourth AAAI Conference on Artificial Intelligence.
A* with Lookahead, $LA^＊$ は、上の2.12(a) に似たアルゴリズムです。A*でノードを展開したするたびに、そのノードから深さに制限を設けたDFS を行います。
DFS中にゴールが見つかった場合、最適性を担保するためには、アルゴリズムをそこで終了させることが出来ません。よりコストの低いゴールノードがあるかもしれないからです。そこで、DFSがゴールを見つけた場合、それより$f$ 値の低いノードを全部調べる必要があります。
このとき、見つかった非最適解の$f$値を上界とする枝刈りができるので、Aよりも早く探索を終えられる可能性があります。上の実験結果からは、AL がA*よりも素早く最適解を見つけていることがわかります。このように、非最適な解にも、最適解を探すための上界を得るという大切な役割があります。この考え方は、Depth-First Branch and Bound (DF-BnB, Korf 1993) で出された考え方です。
また、ALをBPMX を組み合わせると、Inconsistentなヒューリスティクスを用いた時に Aよりもさらに高速化することが論文では示されています。
まとめ
A*, IDA*, HC のハイブリッドアルゴリズムの可能性、そしてその1つであるAL* について紹介しました。