Chapter 11, Problem 29CRP

Program Plan Intro

Heuristic search:

• It denotes a technique to reach goal state by choosing best promising state.
• It leads to goal state and this search is identified as heuristic search.
• The heuristic values are chosen for each node.
• It denotes that node that has low heuristic value is been chosen over another nodes.

Goal:

• The objective is to find state sequence that would lead to final state.
• The numbers are been ordered from initial state that is unordered and it follows the productions.
• The count of tiles that are out of place denotes heuristic in problem.

Algorithm for creating search tree:

• The algorithm is shown below:
  • Step 1:
    • Construct parent node by taking initial node
  • Step 2:
    • Check whether the node signifies a final state.
  • Step 3:
    • If step 2 fails, make child nodes that are possible states and could be attain by moving empty tile in parent nodes.
    • Find heuristic value of states.
    • Select node that has low heuristic value and move to step 2.
  • Step 4:
    • If step 2 is true, then algorithm constructed search tree.
    • Stop construction of tree further.