Bi-Directional Search
- Bidirectional search means to start search from both direction simutaneously.
- The reason to use bidirectional is that in many cases it is faster, it dramatically reduce the amount of required exploration.
1 | Alternate forward search from s |
Note:
- Algorithm terminates when some vertex w has been processed, i.e., deleted from the queue of both searches, $Q_f$ and $Q_b$
- Subtlety: After search terminates, find node x with minimum value of df(x) + db(x). x may not be the vertex w that caused termination as in example to the left!
- Find shortest path from s to x using $Π_f$ and shortest path backwards from t to x using $Π_b$. Note: x will have been deleted from either $Q_f$ or $Q_b$ or both.
Goal directed search or A*
- A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals.
Modify edge weights with potential function over vertices.
$$\bar w(u,v) = w(u,v) - \lambda (u) + \lambda (v)$$
For A* algorithm, one of the item is the real distance, another one is heuristic distance, which can be manhattan, eucliean or other distance.