Reference no: EM132210520

You are to write a program that performs the A* search and apply that program to the problem described below. Your program should recognize revisited (duplicated) states.

Each state should be given a number, starting from 1, that represents the order in which the nodes have been generated.

In each iteration of the algorithm, your program should print the following information:

1. The state number along with the corresponding g, h, and f values in order of the states in the OPEN queue.

2. The state number of the states to be expanded.

3. The new state(s) with state number, configuration, g, h, and f values.

4. After reaching the goal state, print out the solution path (from goal state to initial state) with state number, configuration, g, h, and f values.

Problem: Tower of Hanoi There are three pegs and three discs. The discs are of different sizes. Initially the discs are all on peg A with the smallest disc on the top and the largest one on the bottom.

The top disc on any peg may be moved in the top of another peg so long as no larger disc is ever placed on top of a smaller one.

The object is to get all the discs (in proper order) onto peg C. Let us represent this problem with three lists of integers, with 1 representing the smallest disc, 2 the middle one, etc.

The initial state configuration is:

1

2

3

--- --- ---

A B C

The cost of any move (g) is the number of the disc (that is, cost 3 to move disc 3 to any other peg). Use h = (6 - sum of discs on the target peg).