IDA*
IDA* (Korf, 1985) is a commonly used algorithm for heuristic search on exponential domains with unit edge costs. These videos show the search in progress on the 2x3 sliding tile puzzle. The graph of the complete search space is shown on the left. The current search state is shown on the right/bottom. The search control information is on the right/top.
States are colored by their f-cost; all states with the same f-cost are the same color. States that are not marked with a colored box have f-cost greater than the goal.
NOTE: These videos are now available as interactive demos.
Example #1: Small search tree, accurate heuristic, very slow speed:
Example #2: Small search tree, less accurate heuristic, medium speed:
Example #3: Larger tree, less accurate heuristic, high speed: