Even informed search algorithms like Greedy Search and A* can be slow on problems that require a large number of moves. This is especially true if the heuristic function used by the algorithm doesnt do a good enough job of estimating the remaining cost to the goal.

Our h1 heuristic functionwhich uses the number of misplaced tiles as the estimate of the remaining costis one example of a less than ideal heuristic. For example, consider the following two puzzles:

Both of them have 4 misplaced tiles (the ones displayed in red), but the puzzle on the left can be solved in 4 moves, whereas the puzzle on the right requires 24 moves! Clearly, it would be better if our heuristic could do a better job of distinguishing between these two puzzles.

Come up with at least one alternate heuristic, and implement it as part of your classes for informed searchers (GreedySearcher and AStarSearcher). To do so, you should take the following steps:

As needed, add one or more methods to the Board class that will be used by your new heuristic function. (Adding a new method to the Board class is notrequired, but it can be helpful to add one so that the heuristic function can obtain the information needed for its estimate.)

Add your new heuristic function(s) to searcher.py, and follow these guidelines:

Continue the numbering scheme that we established for the earlier heuristic functions. Call your first alternate heuristic function h2, your next heuristic function (if any) h3, etc.

Make sure that each heuristic function is a regular function, not a method. In addition, make sure that it takes a single State object and returns an integer.

When conducting tests using a new heuristic function, use its name in the same ways that you would use h0 or h1. For example:

>>> g = GreedySearcher(h2) >>> eight_puzzle('142358607', 'Greedy', h2) >>> process_file('15_moves.txt', 'A*', h2) 

You are welcome to design more than one new heuristic function, although only one is required.

When testing and refining your heuristic(s), you can use the files that we provided above, as well as the following files:

18_moves.txt - puzzles that can be solved in 18 moves

21_moves.txt - puzzles that can be solved in 21 moves

24_moves.txt - puzzles that can be solved in 24 moves

27_moves.txt - puzzles that can be solved in 27 moves

Compare the performance of Greedy and A* using the h1 heuristic to their performance using your new heuristic(s). Keep revising your heuristic(s) as needed until you are satisfied. Ideally, you should see the following when using your new heuristic(s):

Both Greedy and A* are able to solve puzzles more quickly testing fewer states on average and requiring fewer searches to be terminated.

Greedy Search is able to find solutions requiring fewer moves.

A* continues to find optimal solutions. (If it starts finding solutions with more than the optimal number of moves, that probably means that your heuristic is overestimating the remaining cost for at least some states.)

12|118 12|118