为什么这个 a* 算法比 Djikstra 的算法慢？

Question

我需要使用下图展示 a* 如何比 Djikstra 更快。我编写了 a* 搜索函数，然后使用一组启发式调用它，然后将所有启发式设置为 0（相当于 Djikstra 的）。虽然使用 a* 的实际搜索效率更高，比 Djikstras 七步长五步，但记录到运行所需的时间总是更长，甚至是许多运行秒的平均值。具有实际启发式值的 a* 运行做得更少所以它不应该更快吗？（也许我的代码不可靠？）

import heapq as heap

#Create graph

graph =    {
    'A': {'B':5},
    'B': {'C':8,'D':9,'E':3},
    'C': {'B':8,'G':2},
    'D': {'B':9,'F':2},
    'E': {'B':3,'I':4},
    'F': {'D':2,'I':3},
    'G': {'C':2,'H':3,'I':6},
    'H': {'G':3,'J':4},
    'I': {'E':4,'F':3,'G':6,'J':2},
    'J': {'H':4,'I':2},
    }

hcost =    {
    'A': 875.008571,
    'B': 717.54094,
    'C': 720.151373,
    'D': 685.286801,
    'E': 596.030201,
    'F': 434.165867,
    'G': 420.107129,
    'H': 190.779978,
    'I': 179.744263,
    'J': 0,
    }

hcost1 =    {
    'A': 0,
    'B': 0,
    'C': 0,
    'D': 0,
    'E': 0,
    'F': 0,
    'G': 0,
    'H': 0,
    'I': 0,
    'J': 0,
    }

def astar_algo(graph, start, target, hc):

    #We set the cost for all nodes from the source
    cost =  {vertex: float('infinity') for vertex in graph}
    #The distance from the source to itself is 0
    cost[start]=0
    
    #We create 
    fcost={vertex: float('infinity') for vertex in graph}
    fcost[start]=hc[start]
    
    #We create a list of nodes to record the path i.e. the solution to the problem
    path=set()
    
    #We create a set to hold visited nodes
    visited=set()

    #We create a priority queue which contains distance to node,node,path and add our start node
    priorityq = [(fcost[start], start, [])]

    #While our priority queue isn't empty
    while priorityq:
        
        #pq0 =  [priorityq[idx][0] for idx in range(0, len(priorityq), 1)] 
        #pq1 =  [priorityq[idx][1] for idx in range(0, len(priorityq), 1)]
        #print(f"Priority Queue: {list(zip(pq0,pq1))}\n")
        #We pop out the highest priority element of the queue i.e. the shortest distance entry
        (dist,current_node,path) = heap.heappop(priorityq)
        
        #print(f"dist {dist} current node {current_node} \tpath {path}\n")

        #Add it to the path list and record it as being visisted
        path = path+[current_node]
        visited.add(current_node)

        #We check if its our target, if it is we break the while loop with a return value
        if current_node==target:
            #We return a tuple with the target node and the cost to it as well as the path to it
            return (current_node,cost[current_node]), path
            
        #If it isnt our target node then we check all its adjacent nodes
        for adj_node, weight in graph[current_node].items():
            
            #If we've visited the node we move on to the nest
            if adj_node in visited:
                continue
            
            #If the node is new we calculate the cost to it by adding the weight to it to
            #the cost for the current node
            new_cost = cost[current_node]+weight
            
            #calculate fcost = graph cost + heuristic cost
            new_fcost = new_cost+hc[adj_node]
            
            #If the cost to the adjacent node is shorter than its recorded cost
            if cost[adj_node] > new_cost:
                #We update its recorded cost
                cost[adj_node]=new_cost
            
            #If the fcost to the adjacent node is shorter than its recorded fcost
            if fcost[adj_node] > new_fcost:
                #We update its recorded cost
                fcost[adj_node]=new_fcost
                #And it to the priority queue
                heap.heappush(priorityq, (new_fcost,adj_node,path))

    return (0,0),'none'
                              
start='A'
target='J'

st =  perf_counter_ns()
cost,path = astar_algo(graph,start,target,hcost)
print('Time elapsed in nanoseconds {}\n'.format(perf_counter_ns() - st))

st =  perf_counter_ns()
cost,path = astar_algo(graph,start,target,hcost1)
print('Time elapsed in nanoseconds {}\n'.format(perf_counter_ns() - st))

if path=='none':
    print("There is no solution available.")
else:
    print(f"The distance to {cost[0]} is {cost[1]}.")
    print (f"The shortest path from {start} to {target} is",end=" ")
    print(*path, sep="->")

Answer 1

您不能只运行一次微小的代码片段并读取纳秒级读数，即使您的计算机具有准确的纳秒级计时器（它可能没有）。内存缓存和计算机中发生的其他事情的随机机会将主导测量（如果它是准确的，则不是）。

幸运的是，python 提供了一个 timeit 模块，可以自动执行运行一遍又一遍地编码并记录时间的过程。为了清楚起见，我更改了一些变量名称，但这里有一个使用 timeit 获取时间的片段：

# I renamed some variables for clarity
from timeit import timeit

astar_time = timeit('cost, path = astar_algo(graph, start, target, hcost_astar)', globals=globals(), number=10000)
print ('astar time    {}'.format(astar_time))

djikstra_time = timeit('cost, path = astar_algo(graph, start, target, hcost_djikstra)', globals=globals(), number=10000)
print ('djikstra time {}'.format(djikstra_time))

astar time 0.4517704
djikstra time 0.5962602

为什么这个 a* 算法比 Djikstra 的算法慢？

Why is this a* algorithm is slower than Djikstra's?

python

search

a-star