IDA

def best_first_graph_search(problem, f, limit, new_limit):
    """Search the nodes with the lowest f scores first.
    You specify the function f(node) that you want to minimize; for example,
if f is a heuristic estimate to the goal, then we have greedy best
first search; if f is node.depth then we have breadth-first search.
    There is a subtlety: the line "f = memoize(f, 'f')" means that the f
values will be cached on the nodes as they are computed. So after doing
a best first search you can examine the f values of the path returned."""

    f = memoize(f, 'f')

node = Node(problem.initial)
ifproblem.goal_test(node.state):
return node
frontier = PriorityQueue(min, f)
frontier.append(node)
explored = set()
while frontier:
limits = set()
node = frontier.pop()
ifproblem.goal_test(node.state):
return node
explored.add(node.state)
print(node.state, node.path_cost)
for child in node.expand(problem):
limits.add(child.path_cost)
ifproblem.goal_test(node.state):
return node
ifchild.state not in explored and child not in frontier:
frontier.append(child)
print(child, child.path_cost)

elif child in frontier:
incumbent = frontier[child]
if f(child) < f(incumbent):
del frontier[incumbent]
frontier.append(child)
new_limit=min(limits)
if limit <new_limit:
limit = new_limit
new_limit = infinity
best_first_graph_search(problem, f, limit, new_limit)




return None


def idaastar_search(problem, h=None):
    "A* search is best-first graph search with f(n) = g(n)+h(n)."
    h = memoize(h or problem.h, 'h')
    limit = 0
    new_limit = infinity
    return best_first_graph_search(problem, lambda n: n.path_cost + h(n),limit, new_limit)