gpt4 book ai didi

python - 为什么 A star 比 Dijkstra 更快,即使启发式在网络中设置为 Nonex

转载 作者:太空宇宙 更新时间:2023-11-03 14:51:16 25 4
gpt4 key购买 nike

这是我之前问题的更新版本。我在 Jupyter notebook 的两点之间运行 NetworkX 中的两种算法(你可以在你现在的任何网络上尝试)。结果显示 astar 更快,即使启发式为 None。我想“无”意味着它是 Dijkstra。我错了吗?

import osmnx as ox
import networkx as nx
G = ox.graph_from_place('Manhattan, New York, USA', network_type='drive')
#change to a simple network in order to run Astar
G_simple=nx.Graph(G)

迪杰斯特拉:

%%time
nx.dijkstra_path(G_simple, 42434910, 595314027, weight='length') #the node is random selected from nodes in the graph

计算时间为:

CPU times: user 15.4 ms, sys: 1.86 ms, total: 17.2 ms
Wall time: 17.1 ms

阿斯塔:

%%time
nx.astar_path(G_simple, 42434910, 595314027, heuristic=None, weight='length')

计算时间为:

CPU times: user 8.8 ms, sys: 313 µs, total: 9.12 ms
Wall time: 9.18 ms

最佳答案

Dijkstra implementation NetworkX 正在使用,到达目标节点时不会停止。 A* 实现。

关于python - 为什么 A star 比 Dijkstra 更快,即使启发式在网络中设置为 Nonex,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45684425/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com