Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Heuristic Functions

  • Definition – Admissible Heuristic Function

      Let (S, s0 , succ , Sol) be a search scheme. A heuristic function h is admissible if h(s ) sd(s ) for all s S .

    • In other words, an admissible heuristic function is a heuristic function that never overestimates the actual cost i.e. the solution distance.

    • e.g. h1 heuristic function defined below is admissible

      h1(s) = n sum(b(i )) , i =1… n , where

      • b(i )=0 in state s if the block i is resting on a wrong thing

      • b(i )=1 in state s if the block i is resting on the thing it is supposed to be resting on;

      • n is the total number of blocks


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.