Assignment 1: A-star algorithm

• 8 puzzle
• Missionaries and Cannibals

• Try different heuristics and compare with baseline case, i.e., the breadth first search (h=0).
• Violate the condition h <= h*. See if the optimal path is still found. Observe the speedup.
• Verify the effect of parent pointer
  1. First convince yourself that h1(displaced tiles) and h2(manhattan distance) are monotonic. Then verify that this situation obxiates need for parent pointer redirection.
  2. Violate monotonicity by includeing the cost of empty cell in the heuristic. Now verify that parent pointer redirection is needed.
  3. Also observe f values of node expanded increases if MR is satisfied
• Have as general a program as possible; when a problem is change only a few things should change (say few classes).
• Present the results in an understandable way, say through graphs and tables.
• Have enough comments in the code; your marks will be affected by not having enough of this.