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 Francisco (Santa Cruz) | |
| Santa Cruz (Monterey) | Queue item 2: San Jose (Santa Cruz) | ||
| Gilroy (Monterey) | |||
| 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 Jose (Gilroy, 115) | |
| Gilroy (Monterey, 109) | Set item: San Francisco (Santa Cruz, 130) | ||
| Santa Cruz (Monterey, 110) |
Warning: Here the depth-first search did not need to backtrack, so the order of visited states is the same as the solution path. But in general, depth-first may need to backtrack and remove items from the stack when it finds it cannot reach a goal from a state.
Click here to see the next step with each of the four searches.