双方向探索

ウィキペディア

双方向探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/26 09:50 UTC 版)

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