5.2 Heuristic Functions

  • A heuristic function h(n) is applied to a node n to measure its "promise"

  • The heuristic function is an estimate of the distance remaining to the goal from node n

  • The lower the heuristic value the more promising the node

  • Useful heuristic functions for 8-puzzle
    • Tiles out of place (h1)
    • Manhattan / City Block Distance (h2)

    1

    2

    3

    4

    5

    6

    7

    8

    .
    Goal State

    1

    2

    3

    4

    5

    6

    7

    .

    8

    1

    3

    6

    4

    2

    8

    7

    .

    5

    h1=1
    h2=1    		 h1=5
    h2=7
[MAIN PAGE] [PREVIOUS PAGE] [NEXT PAGE]
RMiT Copyright © 1999. Department of Computer Science, RMIT University.
Last Modified: 20th June, 1999.