def astar_search(problem, h, pdb):
#F function: determines the next heuristic value based on the maximal
#admissiable heuristic from the depth, heuristic, and pdb
def f(n):
oneMax = max(n.path_cost + h(n) , pdb.find(n.state))
return max(getattr(n, 'f', -infinity), oneMax)
#f = memoize(f, 'f') THIS DOES NOT WORK
fringe = PriorityQueue(min,f) #astar is Best-first w/ a priority ordering
closed = {}
fringe.append(Node(problem.initial)) #start off with the inital state
#while there are nodes to be expanded, check them out.
while fringe:
node = fringe.pop()
#if the present node contains a goal state, then return that node.
if problem.goal_test(node.state):
return node
if node.state not in closed: #this line prevents the repeated checking
#of nodes, simplifing the runtime
closed[node.state] = True
successor = node.expand(problem)
for i in successor:
i.f = f(i)
fringe.append(i)
return None