## 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*.