将Dijkstra转换为Python中的星级算法

Question

我正在尝试将Dijkstra Min Heap（优先队列）算法转换为具有启发式方法的A* - 我适应的Dijkstra算法在这里： =“ https://bradfieldcs.com/algos/graphs/dijkstras-algorithm/”

a_star ？ 它对我有用

如果 f = g + h ， ，然后 我已经修改了存储元组的优先级队列：（f，g，vertex） per @btilly在下面注释 - 因此，它将在每个上拉出最低 f_distance heappop（） 我还添加了访问的集合。

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)

Answer 1

我建议阅读 。这是一个非常有用的API，实施了所谓的Dijkstraheap ，并基于以下方式计算成本启发式：

1. 达到当前点的当前成本。
2. 从当前点到邻居的成本。
3. 邻居到我们正在寻找的终点的距离。

为什么要这3个费用？因为我们想首先探索
在最终目的地附近，在点数中花费更少的时间
离它很远。因此，如果我们人为地给出这一点，如果
该点离目的地将远远持续到以后访问的目的地。

我们计算了这一新成本时，我们将其插入成本
队列。

Answer 2

这是生成路径的完整代码。该图基于此

路径=＆gt; a-＆gt; b-＆gt; d-＆gt; k-＆gt; 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))