Next: Heuristic Functions Previous: Example

Heuristic Functions

If a heuristic function is wrong (bad estimate), it either overestimates (guesses too high) or underestimates (guesses too low).

For A*, overestimating is much worse than underestimating.

                              A (15)
                              |
                 +------------+-------------+
               3 |          2 |           3 |
                 B (6)        C (20)        D (10)
                 |            |             |
         +-------+            |      +------+-----+
  3+15=18|  3+6=9|     2+20=22|      |       3+5=8|
         E (20) *F*(0)        G      H (20)      *I*(0)


         Solution cost: ABF = 9
                        ADI = 8

         Open List:  A15 B9 F9

Missed optimal solution