双方向探索のソースを表示

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

しかし、よいことばかりではない。並列に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).

{{アルゴリズム}}
{{Computer-stub}}

{{DEFAULTSORT:そうほうこうたんさく}}
[[Category:グラフ理論]]
[[Category:検索アルゴリズム]]
[[Category:数学に関する記事]]