Algorithms For Dummies

 Challenging Difficult Problems

# A*

open_list = set(graph.nodes())

closed_list = {start: manhattan_dist(

        start, goal, coordinates)}

visited = {start: 0}

path = {}

while open_list:

    candidates = open_list&closed_list.keys()

    if len(candidates)==0:

        print ("Cannot find a way to the goal %s" % goal)

        break

    frontier = [(closed_list[node],

                 node) for node in candidates]

    score, min_node =sorted(frontier)[0]

    if min_node==goal:

        print ("Arrived at final vertex %s" % goal)

        print ('Unvisited vertices: %i' % (len(

                open_list)-1))

        break

    else:

        print("Processing vertex %s, " % min_node, end="")

    open_list = open_list.difference(min_node)

    current_weight = visited[min_node]

    neighbors = node_neighbors(graph, min_node)

    to_be_visited = list(neighbors-visited.keys())

    for node in neighbors:

        new_weight = current_weight 

+ graph_weight(

                     graph, min_node, node)

        if node not in visited or \

        new_weight < visited[node]:

            visited[node] = new_weight

            closed_list[node] = manhattan_dist(node, goal,

                        coordinates) 

+ new_weight

            path[node] = min_node

    if to_be_visited:

        print ("discovered %s" % to_be_visited)

    else:

        print ("getting back to open list")

---

CHAPTER 20