Bidirectional A* -- 双方向探索に決着がついた日 - Qiita本日学振DC2の採択通知が来た浅井です。クリスマスプレゼントかな。罰ゲームかも 今日は双方向探索の話をします。A*がある程度知られていたのと同様、双方向探索もあるていど知られていると思います。結論としては、双方向探索は ブルートフォースかそれとほとんど変わらない弱いヒューリスティクスを用いた時ぐらいしか使えない ということを示します。強力なヒューリスティクスがある場合には、A*のほうがよいです。 双方向探索 という手法があります(Pohl 1971)。スタートとゴールから交互に逆向きに探索を始め、どちらかが出会ったところで探索が終了するというものです。双方向探索を$A^＊$に用いたものを、Bidirectional A* と呼びます。 http://www.massey.ac.nz/~mjjohnso/notes/59302/l03.html より。 1つの見方としては、これはとても優れた
