我正在编写一个应用程序来建议OpenStreetMap数据上的圆形路线，但要受到一些约束（定向问题）。在我正在试验的算法的最内层循环中，需要找到两个给定点之间的最低成本路径。给定图的布局（基本上是欧几里得），A 星算法似乎有可能在给定图的最快时间内产生结果。然而，除了边缘的距离（代表地图上的实际距离）外，我还有一系列权重（目前从 0.0 缩放，最不理想到 1.0，最理想），表明特定边缘（道路/路径/等）的理想程度) 是根据我为我的应用程序设计的一些指标计算的。
我想根据这些权重修改我的距离。我知道标准的 A 星启发式方法依赖于路径的真实成本至少与估计值一样大（基于点之间的欧几里德距离）。所以我的第一个想法是提出一个方案，其中最小边缘距离是实际距离（对于权重 1.0），并且随着权重的减小，距离会增加（例如，对于权重 0.0，距离增加四倍）。这似乎是一种明智的方法，还是在这种情况下有更好的标准快速路由技术？
我相信你的方法是最理智的。显然我正在研究一个类似的问题，我决定使用完全相同的策略。
A* 算法不一定依赖于“真实距离”。它甚至与距离无关，您实际上可以最小化其他物理量 - 启发式函数应该具有相同的物理单位。
例如，我的问题是最小化路径时间，而任何给定点的速度取决于位置、时间和选择的方向。我的启发式函数是粗略距离（我的问题是在地球表面，计算大圆距离有点贵）除以最大允许速度。也就是说，它有时间单位，它被解释为从给定位置到达终点的最乐观时间。
相关问题是：“您实际上想要最小化什么？”。您需要以单个“修改距离”结束，以便您的寻路算法可以选择最小的距离。
A* 算法的持续有用性取决于您如何将“合意性”整合到您的路由距离中。A* 需要一个乐观的“可接受的启发式”：“修改后的距离”的启发式估计不得超过实际的“修改后的距离”（否则，它找到的路径实际上可能不是最优的......）。确保这一点的一种方法是确保修改后的距离始终大于任何给定步骤的原始欧几里得距离；那么，任何可以使欧几里得距离最小化的 A* 启发式算法也可以用于最小化修改后的距离。
例如，如果您计算modified_distance = euclidean_distance / desirability_rating(for 0<desirability_rating<=1)，您modified_distance将永远不会小于euclidean_distance: 无论您用于未加权路径的 A* 启发式仍然是乐观的，因此它可用于 A*。（虽然，在每条路径都不受欢迎的区域，高度过度乐观的 A* 启发式可能不会像您希望的那样提高性能......）
Fast(er) 路由可以用 A* 来完成。在我自己的项目中，我看到了大约的提升。比dijkstra快 4 倍- 所以，甚至比双向 dijkstra还要快。
但是还有很多技术可以提高查询速度——例如引入快捷方式并在该图上运行 A*。这是一个更详细的答案。