有没有一种方法可以计算出具有不同旅行类型的多个节点之间的最佳路线

Question

在 EVE Online 游戏中有一张带有系统的地图，这些系统可以通过门或跳跃驱动器穿越，但有一些限制：

• 如果系统在范围内（跳跃驱动器具有基于地理距离的最大范围）
• 在某些系统中不能使用跳跃驱动器
• 特定等级的舰船无法进入特定系统
• 跳跃引擎有一个冷却时间，它会根据你最近使用它的时间而增加。

空间系统位置的数据是可用的，连接系统的门列表也是如此

我正在尝试计算两个系统之间的最佳路线，我希望最理想的解决方案将同时使用门和跳跃驱动器，因为门控风险更大且速度更慢（基于系统的大小也是可用的数据）并且跳跃是即时的，但有冷却时间，冷却时间根据你跳跃的次数而增加。

我知道这个问题可能有很多解决方案，我过去使用过 NetworkX 但我正在努力理解如何表达我在像 NetworkX 这样的库中的局限性，看起来像成本是解决这个问题的方法吗？但我不知道是否足以模拟这个问题？

我不是在找人给我一个完整的解决方案，只是希望得到一些关于 NetworkX 是否正确的方法、同一领域的学术研究等的一些指示

Answer 1

• 用代表“系统”的顶点构造一个图。
• 移除表示您的飞船无法进入的系统的顶点
• 在彼此跳跃范围内的每对顶点之间添加边
• 在每对由“门”连接的顶点之间添加边
• 应用 Dijkstra 算法找到系统之间的路径

这会给你一个可行的路径。它可能不是“理想的”。由于您没有告诉我们是什么让一条道路更理想或更不理想，所以很难多说。您暗示可能涉及成本。也许“门”比“跳跃”更昂贵或更便宜——在这种情况下，你适当地调整边缘权重，Dijkstra 会给你最便宜的路径。