The starting state is Monterey and the only goal state is San Francisco.
The evaluation function values (measured as straight-line distance to San Francisco): Monterey: 100; Santa Cruz: 65; Gilroy: 74; San Jose: 45; San Francisco: 0; Oakland: 15.
The costs between states (measured as road distance in miles): Monterey to Santa Cruz, 45; Monterey to Gilroy, 35; Santa Cruz to San Jose, 30; Gilroy to San Jose, 35; Santa Cruz to San Francisco, 85; San Jose to San Francisco, 50; San Jose to Oakland, 50; Oakland to San Francisco, 20.
The working data structure for depth-first is a stack where items are added and removed only at the front; for breadth, a queue where items are added at the rear and removed from the front; for best-first and A*, a set of items where the lowest-value item is chosen at each step. The argument after the state name is the backpointer, and the number after that in best-first and A* is the evaluation of the state.
| Search method | States visited | Agenda | Solution path |
|---|---|---|---|
| Depth-first search | Monterey | Stack top: Santa Cruz | Monterey - |
| Santa Cruz | Santa Cruz - | ||
| San Francisco | San Francisco | ||
| Breadth-first search | Monterey (-) | Queue front: San Jose (Santa Cruz) | Monterey - |
| Santa Cruz (Monterey) | Santa Cruz - | ||
| Gilroy (Monterey) | San Francisco | ||
| San Francisco (Santa Cruz) | |||
| Best-first search | Monterey (-, 100) | Set item: Gilroy (Monterey, 74) | Monterey - |
| Santa Cruz (Monterey, 65) | Set item: San Jose (Santa Cruz, 45) | Santa Cruz - | |
| San Francisco (Santa Cruz, 0) | San Francisco | ||
| A* search | Monterey (_, 100) | Set item: San Francisco (San Jose, 120) | |
| Gilroy (Monterey, 109) | Set item: Oakland (San Jose, 135) | ||
| Santa Cruz (Monterey, 110) | |||
| San Jose (Gilroy, 115) |
Note in A*, the second route found to San Francisco, through San Jose, is lower in cost than the previously found route through Santa Cruz, so both the backpointer and evaluation for San Francisoc are changed. Its total is 35+35+50+0 = 120; the total for Oakland is 35+35+50+15.
Click here to see the next step with each of the four searches.