In searcher.py, define a class called AStarSearcher for searcher objects that perform A* search. Like greedy search, A* is aninformed search algorithm that assigns a priority to each state based on a heuristic function, and that selects the next state based on those priorities. However, when A* assigns a priority to a state, it also takes into account the cost that has already been expended to get to that state (i.e. the number of moves to that state). More specifically, the priority of a state is computed using the following pseudocode:

priority(state) = -1 * (heuristic(state) + num_moves) 

where heuristic(state) is the value that the searchers heuristic function assigns to the state, and num_moves is the number of moves that it took to get to that state from the initial state.

Once again, you should take full advantage of inheritance. However, were leaving it up to you decide which class to inherit from and how much new, non-inherited code is needed!

Heres one thing you need to know: When constructing an AStarSearcher object, you will need to pass in the heuristic function, just as you do when constructing a GreedySearcherobject. See below for an example of constructing one.

Examples:

>>> a = AStarSearcher(h1) >>> a AStarSearcher: 0 untested, 0 tested, heuristic h1 >>> s = State(Board('142358607'), None, 'init') >>> a.add_state(s) >>> a.states # init state has same priority as in greedy [[-5, 142358607-init-0]] >>> succ = s.generate_successors() >>> a.add_state(succ[1]) >>> a.states # succ[1] has a priority of -1*(6 + 1) = -7 [[-5, 142358607-init-0], [-7, 142358067-left-1]] >>> a.next_state() # -5 is the higher priority, so that state is chosen 142358607-init-0 >>> a.states [[-7, 142358067-left-1]]