Prev Up
Go backward to Solution to part (d)
Go up to 1 Finding Paths in a Grid

Solution to part (e)

If the graph had extended infinitely in all directions, A* would still find a solution. Depth-first search would wander off infinitely. Dynamic programming would find a path from s to g, but then continue off forever. If you stopped it when it had included s in the distance map, it would find the shortest path, but this would be the same as a shortest-first search from g, which still isn't as good as A*. It would, however, let us reuse the distance function built for other starting positions to the same goal.
Computational Intelligence online material, ©David Poole, Alan Mackworth and Randy Goebel, 1999

Prev Up