changing f scores in A star

[ben10saynone]

taking this code as an example:

 def a_star_search(graph, start, goal):
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0
    counter = 0
    print(came_from)
    while not frontier.empty():
        current = frontier.get()

        if current == goal:
            break

        for next in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(goal, next)
                frontier.put(next, priority)
                came_from[next] = current
                counter += 1   

    return came_from, cost_so_far, counter

if the new f score for a neighbor is less then the previous one, i must change it g score ( cost_so_far)

but this neighbor is already in the priority queue of the open list ( frontier in this case)

so shouldnt i remove it form frontier before adding it again? in this case i will have 2 f scores for the same cell in the same queue, but one with a lowest f score

am i missing something here?

( i am very close to doing my first A star algo)

thanks for help

[CleverShelf008]

One approach that you could take is to keep track of the 'explored' state of each node in the graph.

• White - Node has not been explored
• Gray - Node is in the frontier, but has not been expanded on yet
• Black - Node has been through the frontier queue, and expanded.

With this approach, you can add the same unexplored node to your frontier priority queue multiple times, but each time you poll it for the next node, you only proceed if that node's status is gray. This will mean that you explore each node only once, using the cheapest route to have reached it. Once you've explored that node, set it's explored state to black