Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph by running two simultaneous searches, one forward from the start and one backward from the goal, stopping when they meet. Ira Pohl was the first to design and implement a bidirectional heuristic search algorithm, and later work by de Champeaux corrected the termination conditions that caused early versions to fail to meet in the middle; as in A* search, the method can be guided by a heuristic estimate of the remaining distance.
Facts
Time Complexity
Time Complexity (category)Exponential Time -- O(2^n) 1 Sources
1. Bidirectional search (Wikipedia)
Wikipedia article body, read for Browse By backfill (w-bbfill-computing6-0927)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.