DPS906 Lecture 7

The problem with A* Search is that the search space grows exponentially. Even the A* has too many branches for normal sized worlds.

Another method called Iterative Deepening A* Search
- set a threshold for search = to a minimal estimate (cannot over estimate)

eg
Arad to Bucharest - 366 (crow flies distance) is minimal estimate THRESHOLD
A->Z = 75 + straight line from Z->B (374) == 449
A->S = 140 + S->B (253) == 393
A->T = 118 + 329 == 447

all checks are bigger than threshold... so set new threshold (smallest of previous checks)
A-S = 393 THRESHOLD
A->S->O = 140 (A-O) + 151(S->O) + 380(O->B) == 671
A->S->F = 140 (A-O) + 99(S-F) + 178(F->B) == 417
A->S->R = 140 (A-O) + 80(S-R) + 193(R->B) == 413 THRESHOLD

etc

The idea is that you keep making your threshold bigger until you can prove that your trip is the threshold.