双方向探索

双方向探索︵英: bidirectional search︶とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する。それぞれの探索の計算量は $O(b^{d/2})$$O(b^{d/2})$︵ランダウの記号︶であり、両方を合わせても $O(b^{d/2}+b^{d/2})$$O(b^{d/2}+b^{d/2})$となり、一方向から全部の探索を行った場合の $O(b^{d})$$O(b^{d})$よりも効率がよい。

しかし、よいことばかりではない。並列に2つの探索を行う複雑さは別として、探索木をどう拡張していくかを各ステップで決定する必要がある。また、最終状態から逆方向に探索できる状況は限られているし、事前に用意が必要になる場合もある。また、2つの探索木の交差を見つける効率的方法も必要になる。このような問題があるため、うまいヒューリスティックがあるならA*の方がよい選択となることが多い。

双方向探索でもヒューリスティックを使うことができる。A*について証明されているように、許容的ヒューリスティックによって最短解が得られる場合がある。

拡張されるノードは、オープンなノード数が最も少なく最も見込みがある最先端から選ばれる。そのようなノードがもう一方の最先端にもある時に、アルゴリズムは終了する。子ノードのf値の計算に当たっては、もう一方の最先端の全てのオープンなノードのg値を考慮しなければならない。そのため、ノードの拡張はA*よりも計算量が多くなる。訪れるノードの数は上で概説したように少なくなることが期待できる。従って、個々の計算量が多くても調べるノード数が少なくなる。参考文献に示した1977年の文献では、A*では解けなかった問題を双方向探索で解いた例が示されている。許容的でないヒューリスティックを使った場合でもより短い経路が見つかっている。これらの検証は Ira Pohl が15パズルで行った。

Ira Pohl は、世界で初めて双方向ヒューリスティック探索アルゴリズムを設計・実装した。最先端の子ノードは、もう一方の側のターゲットについてだけ評価していた。彼の報告によれば、2つの探索木は相手と交差したことを検出できなかったという。

参考文献

• Dennis de Champeaux & Lenie Sint, An Improved Bi-directional Heuristic Search Algorithm, Journal ACM, vol 24, no 2, 1977 May, pp 177-191.
• Dennis de Champeaux, Bi-Directional Heuristic Search Again, Journal ACM, vol 30, no 1, 1983 January, pp 22-32.
• Ira Pohl, Bi-directional Search, in Machine Intelligence, vol. 6, eds. Meltzer and Michie, Edinburgh University Press, 1971, pp. 127-140.
• Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach, 2nd ed., Prentice Hall, 2002 (§3.4).