Chapter 11, Problem 23CRP

a.

Program Plan Intro

Search tree:

Search tree is that tree which consists of the part of the state graph. It is used to solve the eight-puzzle. The start state is the root node of the search tree and children of nodes are those possible states which are reachable from parent node for one production.

Breadth first search:

A breadth first search is an algorithm used to search and transverse tree or graph data structure. It starts from any arbitrary node and explore all the never nodes at the present depth level.

b.

Explanation of Solution

The state found in the backward search is also a binary tree and the rate of progress of both the search is same.

The total number of nodes considered when the search is conducted can be reduced by conducting two searches at a time as:

• The tree should be binary tree when a search begins from the goal so that the leaf node can be eliminated to reduce the number of nodes form a binary tree when the tree traversal occurs from backward...