Chapter 3, Problem 29E

Program Plan Intro

Admissible heuristic:

• A heuristic h(s) is admissible, if for every node n, $h(s)\le h*(s)$ is the true cost to reach the goal state from n
• An admissible heuristic never over estimates the cost to reach the goal. That is optimistic. Sensorless search problem defines by four items. That are given below,
• 1. 1. Initial state
  2. 2. Description of action: successor function h(s) = set of action-state pairs
  3. 3. Goal test, can be
     • Explicit
     • Implicit
  4. 4 Path cost. It reflects the performance measure.
• An admissible heuristic can be obtained by taking maximum of h*(s). Since any sequences of actions that solve all states would solve each state, this heuristic is admissible.

Inconsistent heuristic:

• A heuristic function is said to be inconsistent in the analysis of path-finding problems in artificial intelligence, if its approximation is always greater than to the approximate distance from any neighbouring vertex to the target.
• Inconsistent heuristic can be represented as,

$h(N)>c(N,p)+h(p)$

where,

• h is the consistent heuristic function
• N is any node of the graph
• P is any decedent of N
• G is the goal node
• c(N,P) is the cost of reaching node P from N