Chapter 4, Problem 7E

Program Plan Intro

Figure 4.14:

Admissible heuristic:

A heuristic h(s) is admissible, if for every node n,

h(s) ≤ 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.

A* search algorithm:

• The A* search algorithm is a search algorithm used to search a particular node of a graph.
• A* algorithm is a variant of the best-first algorithm based on the use of heuristic methods to achieve optimality and completeness.
• The algorithm A* is an example of a best-first search algorithm.
• If a search algorithm has the property of optimality, it means that the best possible solution is guaranteed to be found. Here, the user wants the shortest path to the final state.