A*算法的新方法

Question

我编写了一个Python脚本来实现A*算法。给出了地图、起点和目标。

就我测试的情况而言，代码运行良好，但我也想从最好的人那里得到反馈。所以我在这里分享代码。地图是给你的泡菜文件。

在代码M中是：

class Map:
    def __init__(self, G):
        self._graph = G
        self.intersections = networkx.get_node_attributes(G, "pos")
        self.roads = [list(G[node]) for node in G.nodes()]

Graph = pickle.load(pickleFile)    
M = Map(Graph)

开始/目标是两个表示节点的整数。

def shortest_path(M, start, goal):
    explored = set([start])
    frontier = dict([(i,[start]) for i in M.roads[start]]) if start!=goal else {start:[]}
    while frontier:
        explore = g_h(frontier,goal,M)
        for i in [i for i in M.roads[explore] if i not in frontier.keys()|explored]:
            frontier[i]=frontier[explore]+[explore]
        frontier = cleanse_frontier(frontier,M)
        if explore==goal:return frontier[explore]+[explore]#break when goal is explored.               
        explored.add(explore)
        del frontier[explore]#once explored remove it from frontier. 

def g_h(frontier,goal,M):
    g_h = dict([(path_cost(frontier[node]+[node],M)+heuristic(node,goal,M),node) for node in frontier])  
    return g_h[min(g_h)]

def heuristic(p1,p2,M):#Euclidean Heuristic from the node to the goal node
    M=M.intersections 
    return ((M[p1][0]-M[p2][0])**2+(M[p1][1]-M[p2][1])**2)**0.5

def path_cost(path,M,cost=0):#Euclidean distance for the path
    M=M.intersections 
    for i in range(len(path)-1):
        cost += ((M[path[i]][0]-M[path[i+1]][0])**2+(M[path[i]][1]-M[path[i+1]][1])**2)**0.5
    return cost

def cleanse_frontier(frontier,M):
    """If any node can be removed from the frontier if that can be reached 
    through a shorter path from another node of the frontier, remove it 
    from frontier"""
    for node in list(frontier):
        for i in [i for i in frontier if i!=node]:
            if node not in frontier:continue                
            if frontier[i]==frontier[node]:continue
            if i not in M.roads[node]:continue
            if path_cost(frontier[node]+[node]+[i],M)<path_cost(frontier[i]+[i],M):
                del frontier[i]
    return frontier

Answer 1

我的一个建议是使用堆数据结构来存储成本，这样就可以在对数时间内计算min。