heuristic search
go from s to e
different paths exist
algorithms differ on:
- how to organize the search
- where to search first
methods
next: the principles of these on the example
destination (point e) is on the right
A*
[dijstra-g.fig]
expand the explored area from s
prefer expanding on the right
backtracking
[dijstra-j.fig]
move to the right, but
remember roads not taken
when on a dead end:
go back to a crossroad and take a different direction
LRTA*
[dijstra-k.fig]
move to the right
remember that some road are bad
even if they go to the right
do not take them again
description of the methods
classification: families of search algorithms