Q1. (a). Assignment 15 points
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 neighborhood.
a. Implement Hill Climbing Search Algorithm for solving the 8-puzzle problem. Your start state can be anything and the goal state will be
{123;456;78B}, where B is blank tile.
b. Input: Input should be taken from an input file and processed as a matrix.
c. Output: All the following results should be stored in an output file (for each of the
heuristics as mentioned in d)
i. The success or failure message ii. Heuristics chosen, Start state and Goal state iii. (Sub)Optimal Path (on success) iv. Total number of states explored
v. Total amount of time taken
d. Heuristics to be checked:
i. h1 (n)= Number of displaced titles ii. h2 (n)= Total Manhattan distance
e. Constraints to be checked:
i. Check whether the heuristics are admissible ii. What happens if we make a new heuristics h3(n)= h1 (n) + h2 (n)?
iii. What happens if you consider the blank tile as another tile? (for each heuristics as mentioned in d)
iv. What if the search algorithm got stuck into Local maximum? Is there any way to get out of this?
v. What happens when all the neighbours of the current state have the same value? How to get rid of this situation?
================================================================================= Best of Luck
