Converting Dijkstra to A star algorithm in python-CodePudding

I am trying to convert a dijkstra min heap (priority queue) algo to an a* with heuristics - the dijkstra algorithm I'm adapting is here: https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/

Is the below algorithm a correct implementation of a_star ? It worked for me on a couple test graphs

If f = g h, then I have modified the priority queue to store the tuple: (f, g, vertex ) per @btilly comment below - so it will pull the lowest f_distance on each heappop() I have also added the visited set.

import heapq

# V ElogE time / E space
def a_star(graph, start, dest, heuristic):
    distances = {vertex: float('inf') for vertex in graph} # V time / V space
    distances[start] = 0

    parent = {vertex: None for vertex in graph} # store path => V time / V space

    visited = set()

    pq = [( 0   heuristic[start], 0 ,  start)] # E space

    while pq: # ElogE time
        curr_f, curr_dist, curr_vert = heapq.heappop(pq) #logE time

        if curr_vert not in visited:
            visited.add(curr_vert)

            for nbor, weight in graph[curr_vert].items():
                distance = curr_dist   weight  # distance from start (g)
                f_distance = distance   heuristic[nbor] # f = g   h

                # Only consider this new path if it's f_distance is better
                if f_distance < distances[nbor]:
                    distances[nbor] = f_distance
                    parent[nbor] = curr_vert


                    if nbor == dest:
                        # we found a path based on heuristic
                        return distances, parent

                    heapq.heappush(pq, (f_distance, distance, nbor)) #logE time

    return distances, parent


graph = {
    'A': {'B':3, 'H':4, 'F': 1},
    'B': {'A': 3, 'C':5  },
    'C': {'B':5, 'D':6, 'I':2},
    'D': {'C':6, 'E':1},
    'E': {'D':1, 'I':2, 'G':20},
    'F': {'A':1, 'G':1},
    'G': {'F':1, 'E':20},
    'H': {'A':4, 'I':8, },
    'I': {'H':8, 'C':2, 'E':2},
}
heuristic = {
    'A': 20,
    'B': 19,
    'C': 16,
    'D': 12,
    'E': 0,
    'F': 13,
    'G': 11,
    'H': 15,
    'I': 10,
}


start = 'A'
dest= 'E'
distances,parent = a_star(graph, start, dest, heuristic)

CodePudding user response：

I'd suggest reading this implementation of the A* Algorithm by Python core dev Pablo Salgado. It's a very Pythonic API implementing a so-called DijkstraHeap and calculating the cost heuristics intuitively based on:

The current cost of reaching the current point.
The cost of going from the current point to the neighbor.
The distance of the neighbor to the end point that we are looking.

Why this 3rd cost? Because we want to explore first the points that are near the end destination and expend less time in the points that are far from it. So if we artificially give the point a higher cost if the point is far from the destination it will be visited later.

When we have calculated this new cost we insert the point in the cost queue.

CodePudding user response：

Here's the full code to generate the path . The graph is based on this youtube:

path => A->B->D->K->P

import heapq

# V ElogE time / E space
def a_star(graph, start, dest, heuristic):
    distances = {vertex: float('inf') for vertex in graph} # V time / V space
    distances[start] = 0

    parent = {vertex: None for vertex in graph} # store path => V time / V space

    visited = set()

    pq = [( 0   heuristic[start], 0 ,  start)] # E space

    while pq: # ElogE time
        curr_f, curr_dist, curr_vert = heapq.heappop(pq) #logE time


        if curr_vert not in visited:
            visited.add(curr_vert)

            for nbor, weight in graph[curr_vert].items():
                distance = curr_dist   weight  # distance from start (g)
                f_distance = distance   heuristic[nbor] # f = g   h

                # Only process new vert if it's f_distance is lower
                if f_distance < distances[nbor]:
                    distances[nbor] = f_distance
                    parent[nbor] = curr_vert


                    if nbor == dest:
                        # we found a path based on heuristic
                        return distances, parent

                    heapq.heappush(pq, (f_distance, distance, nbor)) #logE time

    return distances, parent



def generate_path_from_parents(parent, start, dest):
    path = []
    curr = dest
    while curr:
        path.append(curr)
        curr = parent[curr]

    return '->'.join(path[::-1])



# FROM https://www.youtube.com/watch?v=eSOJ3ARN5FM&list=PLTd6ceoshprfgFGcdiQw9LQ3fXaYC-Zs2&index=3
graph = {
    'A': {'B':5, 'C':5},
    'B': {'A':5, 'C':4, 'D':3  },
    'C': {'A':5, 'B':4, 'D':7, 'E':7, 'H':8},
    'D': {'B':3, 'C':7, 'H':11, 'K':16, 'L':13, 'M':14},
    'E': {'C':7, 'F':4, 'H':5},
    'F': {'E':4, 'G':9},
    'G': {'F':9, 'N':12},
    'H': {'E':5, 'C':8, 'D':11, 'I':3 },
    'I': {'H':3, 'J':4},
    'J': {'I':4, 'N':3},
    'K': {'D':16, 'L':5, 'P':4, 'N':7},
    'L': {'D':13, 'M':9, 'O':4, 'K':5},
    'M': {'D':14, 'L':9, 'O':5},
    'N': {'G':12, 'J':3, 'P':7},
    'O': {'M':5, 'L':4},
    'P': {'K':4, 'J':8, 'N':7},
}


heuristic = {
    'A': 16,
    'B': 17,
    'C': 13,
    'D': 16,
    'E': 16,
    'F': 20,
    'G': 17,
    'H': 11,
    'I': 10,
    'J': 8,
    'K': 4,
    'L': 7,
    'M': 10,
    'N': 7,
    'O': 5,
    'P': 0
}

start = 'A'
dest= 'P'
distances,parent = a_star(graph2, start, dest, heuristic2)
print('distances => ', distances)
print('parent => ', parent)
print('optimal path => ', generate_path_from_parents(parent,start,dest))