双方向探索

双方向探索: bidirectional search)とは、グラフ探索アルゴリズムの一種で、同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する。それぞれの探索の計算量は O ( b d / 2 ) {\displaystyle O(b^{d/2})} ランダウの記号)であり、両方を合わせても O ( b d / 2 + b d / 2 ) {\displaystyle O(b^{d/2}+b^{d/2})} となり、一方向から全部の探索を行った場合の O ( b d ) {\displaystyle 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).
ソート
比較ソート
線形時間ソート
並行ソート
非効率的
グラフ
探索
リスト
木・グラフ
文字列
最短経路問題
最小全域木
最大フロー問題
最小カット問題
線型計画問題
順序統計量
計算幾何学
種類
その他
カテゴリ
  • 表示
  • 編集