–

Questions

–

1. In a Best First Search algorithm each state (n) maintains a function
   1. f(n) = h(n)

In an A* search algorithm each state (n) maintains a function

1. 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.

1. g(n) = least cost from source state to current state so far.
2. Heuristics
   1. h1(n) = number of tiles displaced from their destined position.
   2. 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.
   1. Implement the Hill Climbing Search Algorithm for solving the 8-puzzle problem.
   2. Check the algorithm for the following heuristics:
      1. h1(n) = number of tiles displaced from their destined position.
      2. 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:
   1. On success:
      1. Success Message
      2. Start State / Goal State iii. Total number of states explored iv. Total number of states to optimal path
      3. Optimal Path
      4. Optimal Path Cost

• Time taken for execution

1. On failure:
   1. Failure Message
   2. Start State / Goal State

• Total number of states explored before termination

3. Compare and contrast between the results of the three algorithms for the different heuristics