Description

Assignment-2: A* Search
(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 with following assumptions.
1. g(n) = least cost from source state to current state so far.
2. Heuristics
(a) h1(n) = 0.
(b) h2(n) = number of tiles displaced from their destined position.
(c) h3(n) = sum of Manhattan distance of each tiles from the goal position.
(d) h4(n) = Devise a heuristics such that h(n) >h∗(n).
Update:
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 monotone restriction on the heuristics
4. Observe un-reachability and provide a proof.
1. Observe and verify whether monotone restriction is followed for the following two Heuristics:
(a) h2(n) = number of tiles displaced from their destined position. (b) h3(n) = sum of Manhattan distance of each tiles from the goal position.
2. 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 file in the following format. Read the input and store the information in a matrix. Configuration 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.
Start state Goal state
T6 T7 T3
T8 T4 T2 T1 B T5 T1 T2 T3
T4 T5 T6
T7 T8 B
3. Output should have following information: On success
• Success message
• Start state / Goal state
• Total number of states explored.
• 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
a) Total number of states explored.
b) Total number of states on optimal path.
c) Optimal path
d) Optimal Cost of the path.
e) Total time taken for execution
5. Please try to make your code as generic as possible (Preferably in C/C++/Java/Python).
6. Please collaborate with your group members.