我正在编写一个应用程序来建议 OpenStreetMap 上的环形路线数据受到某些约束(定向问题)。在我正在试验的算法的最内层循环中，需要找到两个给定点之间成本最低的路径。给定图表的布局(基本上是 Euclidean )， A star算法似乎很可能在给定图表的最快时间内产生结果。然而，除了边缘上的距离(代表 map 上的实际距离)，我还有一系列权重(目前从 0.0 缩放，最不理想到 1.0，最理想)指示特定边缘(道路/路径/等)的理想程度) 是根据我为我的应用程序设计的一些指标计算得出的。
我想根据这些权重修改我的距离。我知道标准的 A 星启发式依赖于路径的真实成本至少与估计值一样大(基于点之间的欧氏距离)。所以我的第一个想法是想出一个方案，其中最小边缘距离是实际距离(对于权重 1.0)并且距离随着权重减小而增加(例如，对于权重 0.0，距离增加四倍)。这似乎是一种明智的方法，或者在这些情况下是否有更好的快速路由标准技术？
最佳答案
我相信您的方法是最明智的。显然我正在处理类似的问题，并且我决定使用完全相同的策略。
A* 算法不一定依赖于“真实距离”。它甚至与距离无关，您实际上可以最小化其他物理量 - 启发式函数应该具有相同的物理单位。
例如，我的问题是最小化路径时间，而任何给定点的速度取决于位置、时间和所选方向。我的启发式函数是粗略距离(我的问题是在地球表面，计算大圆距离有点昂贵)除以最大允许速度。也就是说，它有时间单位，它被解释为从给定位置到达终点的最乐观时间。
关于algorithm - 修改具有边权重和距离的欧几里德图的星形路由，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11299790/