如何计算A*星与自定义启发式在networkx？

Question

我试图用一个自定义的启发式算法计算两个节点之间的最短路径长度。启发式方法测量两个节点之间的加权最短路径长度加上最短路径内的节点数。考虑一个交通问题，我需要在城市网络中找到两个城市之间的最短路径。最短路径是具有最小总距离（以天为单位）和城市中最小公交次数（以天为单位）的路径。

我试图使用networkxa_star_path_length功能。以下是我已经尝试过的：

def distance(a,b):
    return ( nx.dijkstra_path_length(G,a,b, 'day') + len(nx.dijkstra_path(G, a, b)) )

nx.astar_path_length(G, 'A', 'F', heuristic=distance, weight='day')

假设具有六个节点的图中每条边的权重如下所示：

A,B --> 1 day
B,C --> 1 day
C,D --> 1 day
D,F --> 1 day
A,E --> 4 day
E,F --> 1 day

对于每个访问的节点，我需要花费1天的时间。

因此，城市A和城市F之间的最短路径如下：A--

结果应该是（41）（11）=7。

路径A-B-C-D-F的距离可能最短。但是由于有很多次的过境，它们不再是最短的路径。

我用a_star函数尝试了我的函数，但是算法仍然更喜欢路由A-B-C-D-F，而不是A-E-F。

请帮忙。

Answer 1

这里的问题是您试图修改启发式，而不是实际的图权重。实际上，A*算法返回的最小权重路径与Djikstra算法返回的路径相同，它的速度要比Djikstra快得多，因为它没有进行随机的广度优先搜索，但有一个启发式算法可以帮助它在图中的正确方向上进行引导。重要的是，不管启发式是什么，它仍然会找到最小权重路径†。

解决此问题的方法是将运输编号合并到重量中。我认为这应该等于在图表中的每一个权重上加1（或者你想怎么加一跳的权重）。

通常，我认为某些启发式属性有例外。