def heuristic_search(graph, start, goal, heuristic):
<EOL>queue = [ (<NUM_LIT:0>, start, <NUM_LIT:0>, None) ]<EOL>g = {}<EOL>explored = {}<EOL>while queue:<EOL><INDENT>_, current, dist, parent = heappop(queue)<EOL>if current == goal:<EOL><INDENT>path = [current] + [ n for n in _reconstruct_path( parent, explored ) ]<EOL>path.reverse()<EOL>return path<EOL><DEDENT>if current in explored:<EOL><INDENT>continue<EOL><DEDENT>explored[current] = parent<EOL>for neighbor in graph[current]:<EOL><INDENT>if neighbor in explored:<EOL><INDENT>continue<EOL><DEDENT>ncost = dist + graph.edge_weight((current, neighbor))<EOL>if neighbor in g:<EOL><INDENT>qcost, h = g[neighbor]<EOL>if qcost <= ncost:<EOL><INDENT>continue<EOL><DEDENT><DEDENT>else:<EOL><INDENT>h = heuristic(neighbor, goal)<EOL><DEDENT>g[neighbor] = ncost, h<EOL>heappush(queue, (ncost + h, neighbor, ncost, current))<EOL><DEDENT><DEDENT>raise NodeUnreachable( start, goal )<EOL>
A* search algorithm.

A set of heuristics is available under C{graph.algorithms.heuristics}. User-created heuristics
are allowed too.

@type graph: graph, digraph
@param graph: Graph

@type start: node
@param start: Start node

@type goal: node
@param goal: Goal node

@type heuristic: function
@param heuristic: Heuristic function

@rtype: list
@return: Optimized path from start to goal node