Optimal search trees
Finding the best possible sequence of choices.
Getting closer to the goal is generally considered good, but it may lead to dead ends or non-optimal choices.
Oracle
Knowing the minimum path length to the goal, the search algorithm records the length of path already extended and always extends the shortest path first until all paths are longer than the known shortest length.
Branch & Bound
With the same principle, if the shortest path is not known yet (no “Oracle”) paths are extended to the goal and recorded. Other paths are extended until the are as long or longer than the current shortest path to the goal.
The algorithms extends the first path and then sorts them by length.
Branch & Bound + Extended List
In addition to the branch and bound algorithm, new branches that lead back to node previously extended with a longer path are discarded.
Branch & Bound + Admissible Heuristic
The estimated remaining distance to the goal is added to the path extended. Only the shortest path extended + remaining estimated distance is extended until the goal is reached. All longer paths are discarded.
A* = Branch & Bound + Extended List + Admissible Heuristic
In the algorithm, instead of sorting extensions to put the shortest paths (leading to many calculations), only test if the shortest path leads to the goal.
Consistency Heuristic
In certain cases (especially not about maps), the Admissible Heuristic may lead to problems. The consistency heuristic uses a stronger condition, namely that the distance to the goal from a given node x, minus the distance to the goal from another node y, in absolute value, has to be inferior to the distance between x and y.