双方向探索
双方向探索(英: 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*の方がよい選択となることが多い。