Necessary expansions in optimal search

When performing search, an important theoretical question is which states must be expanded by which algorithms. Early work by Dechter and Pearl showed that all optimal unidirectional algorithms must expand all states with f(s) < C*, where C* is the optimal solution cost. Note that the theory says nothing about states with f(s) = C*. The app on this page contains three "games" related to understanding necessary expansions in unidirectional and bidirectional search.

Start by drawing or erasing any obstacles in the map. Then, select a start and goal state for the game.

Next, play the first game -- try to identify a state that, if it were not expanded, A* would not be guaranteed to find the optimal solution. (That is, a state with f(s) < C*.)

In the second game you will try to identify a similar state for bidirectional search. If you are having trouble with the second game, you can try the third game -- an alternate version of the second game.

Related Videos

Selected Related Publications