Solved–Assignment-2: –A* Search– Solution

Description

(Read all the instructions carefully & adhere to them.)

In a general search algorithm each state (n) maintains a function

f(n) = g(n) + h(n)

where g(n) is the least cost form source state to state n found so far and h(n) is the estimated cost of the optimal path from state n to the goal state.

Implement a search algorithm for solving the 8-puzzle problem withng prob-lem with following assumptions.

1. g(n) = least cost from source state to current state so far.

2. Heuristics

1. 1. h₁(n) = 0.

1. 2. h₂(n) = number of tiles displaced from their destined position.

1. 3. h₃(n) = sum of Manhattan distance of each tiles from the goal position.

1. 4. h₄(n) = Devise a heuristics such that h(n) > h (n).

1. Observe and verify that better heuristics expands lesser state.

2. Observe and verify that all the states expanded by better heuristics should also be expanded the inferior heuristics.

3. Observe and verify whether monotone restriction is followed for the following two Heuristics:

1. 1. h₂(n) = number of tiles displaced from their destined position.

   2. h₃(n) = sum of Manhattan distance of each tiles from the goal position.

4. Observe and verify that if cost of the empty tile is added (considering empty tile as another tile) then monotonicity will be violated.

Instructions:

1. You should make use of two lists for the implementation. One (close list) for maintaining the already explored states and other (open list) for maintaining the states which are found but yet to be explored.

2. Input is given in a le in the following format. Read the input and store the information in a matrix. Con guration of start state and goal state can be anything. For the example given below, T1, T2, …, T8 are the tiles number and B is blank space.

Total number of states on optimal path. Optimal Path

Optimal Cost of the path.

On failure

Failure message

Start state / Goal state

Total number of states explored before termination.

4. Please make a table that should list the following for all the heuristics

4. 1. Total number of states explored.

4. 2. Total number of states on optimal path.

4. 3. Optimal path

4. 4. Optimal Cost of the path.

4. 5. Total time taken for execution

4. Please try to make your code as generic as possible (Preferably in C/C++/Java/Python).

4. Please collaborate with your group members.

4. Make your submission at https://bit.ly/2YULOL8. The submission

le should be as follows: Group-NUMBER Assignment-NUMBER.zip

3