Lower Bound
  • What is "expected solution length"?
  • Find a lower-bound function for the distance to a goal.
  • This is the heuristic knowledge of the program.
  • The accuracy of this function determines the efficiency of the program.
  • We will use a matching for stones and goals.
stones on goals on
Bb Ic If
Cc 2 6 9
Hb 6 Infinity Infinity
Id Infinity 1 2

GPW'99, October 16, 1999. Pushing the Limits: New Developments in Single-Agent Search previous up next