Search: Example 2, Best-First Search, Tower of Hanoi

• To do best-first search using your basic search procedure, you only need to define a new merge-queue procedure. best-first-merge takes the queue, the new paths, and the problem-specific estimate procedure, adds the new paths to queue, and then sorts the new queue by the values returned by estimate when applied to the first state on each path. You can use the Scheme procedure sort to do this. sort takes a comparison predicate and a list and sorts the list using the predicate to compare items.

• Figure out how you will represent states for your particular problem.
  • For the Tower of Hanoi Puzzle, states are lists consisting of a sublist for the disks on each peg. Numbers represent the widths of the pegs, and they are arranged from top to bottom. Thus this is the initial state for the 3-disk puzzle:

    ((1 2 3) () ())

• Write the goal?, extend, estimate, and print-state procedures for your particular problem.
  • For the Tower of Hanoi Puzzle, these are one possibility.

• Callthe search procedure on the problem-specific states and procedures.
  • Best-first search on the Tower of Hanoi Puzzle: a trace indicating states which are searched and the queue at each point in the search

Search: Previous Page

Representation and Reasoning: First Page