(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.
g(n) = least cost from source state to current state so far.
Heuristics
h1(n) = 0.
h2(n) = number of tiles displaced from their destined position.
h3(n) = sum of Manhattan distance of each tiles from the goal position.
h4(n) = Devise a heuristics such that h(n) h (n).
Observe and verify that better heuristics expands lesser state.
Observe and verify that all the states expanded by better heuristics should also be expanded the inferior heuristics.
Observe and verify whether monotone restriction is followed for the following two Heuristics:
h2(n) = number of tiles displaced from their destined position.
h3(n) = sum of Manhattan distance of each tiles from the goal position.
Observe and verify that if cost of the empty tile is added (considering empty tile as another tile) then monotonicity will be violated.
Instructions:
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.
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.
Start state
T6 T7 T3
T8 T4 T2
T1 B T5
Goal state
T1 T2 T3
T4 T5 T6
T7 T8 B
Output should have following information: On success
Success message
Start state / Goal state
Total number of states explored.
2
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.
Please make a table that should list the following for all the heuristics
Total number of states explored.
Total number of states on optimal path.
Optimal path
Optimal Cost of the path.
Total time taken for execution
Please try to make your code as generic as possible (Preferably in C/C++/Java/Python).
Please collaborate with your group members.
Make your submission at https://bit.ly/2YULOL8. The submission
le should be as follows: Group-NUMBER Assignment-NUMBER.zip
3
