| Heuristic Searches - A* Algorithm |
|
|
|
|
|
|
|
|
|
|
| Typical
solution is about twenty steps |
|||||||||
| Branching
factor is approximately three. Therefore a |
|||||||||
| complete
search would need to search 320 states. But |
|||||||||
| by keeping track of repeated states we would only need |
|||||||||
| to
search 9! (362,880) states |
|||||||||
| But
even this is a lot (imagine having all these in |
|||||||||
| memory) |
|||||||||
| Our
aim is to develop a heuristic that does not over |
|||||||||
| estimate
(it is admissible) so that we can use A* to find |
|||||||||
| the
optimal solution |
|||||||||
