1. In a Best First Search algorithm each state (n) maintains a function
a. f(n) = h(n)
In an A* search algorithm each state (n) maintains a function
b. 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 Best First Search and A* search algorithm for solving the 8-puzzle problem with the following assumptions.
A. g(n) = least cost from source state to current state so far.
B. Heuristics
a. h1(n) = number of tiles displaced from their destined position.
b. h2(n) = sum of Manhattan distance of each tile from the goal position.
2. A local search algorithm tries to find the optimal solution by exploring the states in the local region. Hill climbing is a local search technique which always looks for a better solution in its neighbourhood.
a. Implement the Hill Climbing Search Algorithm for solving the 8-puzzle problem.
b. Check the algorithm for the following heuristics:
i. h1(n) = number of tiles displaced from their destined position.
ii. h2(n) = sum of Manhattan distance of each tile from the goal position.
Instructions:
1. Input is given in a file in the following format. Read the input and store the information in a matrix. Configuration of the start state and the goal state can be anything. For example given below T1, T2, …,T8 are tile numbers and B is blank space.
2. Output should have the following information:
a. On success:
i. Success Message
ii. Start State / Goal State iii. Total number of states explored iv. Total number of states to optimal path
v. Optimal Path
vi. Optimal Path Cost
vii. Time taken for execution
b. On failure:
i. Failure Message
ii. Start State / Goal State
iii. Total number of states explored before termination
3. Compare and contrast between the results of the three algorithms for the different heuristics
