高效编写航线算法

Question

给定：

• 一个航班数据库（出发城市，到达城市，出发时间，到达时间）。

问题：

• 如果不考虑出发时间，列出两个城市之间的服务最高效的算法是什么？考虑到我们想要最小化转机时间（但仍要保持在名义最低限度以上，即20分钟），并最小化停靠次数（如果有直达路线，这很简单，但如果没有，找到一条连接路线超过两个连接等，有合理的停靠时间，就不那么简单了）。
• 如果可能的话，我不想特别标记任何机场作为枢纽，以便留下点对点路线网络的可能性。
• 应该有一个选项来指定所需的（大致）出发时间。如果这有自己独立于第一个算法的算法，那就没关系。

此项目的代码语言尚未选择（可能是.NET语言，因为快速表单会派上用场），因此首选伪代码算法。如果添加信息可能有帮助，我会留意后续问题。

- alexwood

---

@Ben Hughes，正是我所想的...:-D - LB40

这个算法的速度很重要，因为它可能会被连续调用数千次。这是我在空闲时间编写的游戏。 - alexwood

在这个问题上，如果有一个可以胜任的库，那就太好了 :) - alexwood

Answer 1

在基础层面上，您将把城市网络视为一棵树，以出发城市为根，每个出发航班都是指向子节点的指针。您将通过递归深度优先搜索树来查找到目的地的所有路径，但在进行搜索时要检查是否存在循环，并放弃任何导致循环的路径。

在找到可行路径时，您可以仅将已找到的最短路径保留为单个解决方案；或者根据出发时间等标准保留更大的路径子集，如果您想根据此选择。

根据数据库和节点的具体情况，您还可以添加其他规则来缩短路径搜索时间，例如，如果您知道出发地和目的地相距1000英里，而迄今为止您所追踪的路径让您飞行了3000英里但还未到达目的地，则放弃该路径，继续下一次路径搜索。

- user447688

---

这听起来不错（而且作为额外奖励，很容易修改以添加一次停靠，有限停靠等一些额外功能）。虽然我希望能够单独模拟网络中的每个乘客（可能模拟到数百万人），但看来现在我也需要找到估计算法了。-_- - alexwood

是的，我已经编写了一个出色的圆形映射器函数，用于为每个城市对创建固定时间内的距离，并使用负责服务该航班的飞机来计算估计飞行时间，所以“逻辑”飞行路径是我忘记在 OP 中添加的要求。但是正如您所说，您的算法可以轻松覆盖这一点。 - alexwood

我还没有针对任何大规模问题实现过这个，但我想选择明智的剪枝启发式方法将对性能产生巨大影响。 - user447688

看了一下，我想我必须让“枢纽和重点”机场标记起来。如果这样做，我可以为1个连接和2个连接的行程实现非常好的运行时间，在枢纽和辐射模型中覆盖95%以上的所有情况，在国内枢纽和辐射路线网络中覆盖100%的情况。然后当我对边缘情况运行“蛮力”算法时，应该会有可接受的结果。 - alexwood

最小生成树的解决方案能比这个更好吗？ - Vaibhav

Answer 2

Dijkstra或A*，权重是对长时间等待和多次停靠的某种惩罚。

- Georg Schölly

Answer 3

在分解响应后，我正在尝试一种基于手动标记“连接”机场的算法。这样可以避免查找可能无法连接任何地方的数百个机场（你上次是什么时候通过锡达拉皮兹从纽约连接到东京的？）。这覆盖了最多2次转机，超过2次转机后，我将使用特殊情况算法、完整的树搜索或将路线标记为“未服务”（许多真实航空公司都这样做，但对于游戏来说，这应该是可定制的）。

当前模型如下：

寻找直飞航班！

• 是否有从起点机场到终点机场的直达航班？太棒了！返回非停止列表（请求算法可以决定如何处理它）。

没有非停止连接吗？

• 汇总所有从起始机场到“连接”机场（所有枢纽和重点城市）的航班。
• 汇总所有从这些“连接”机场（所有枢纽和重点城市）到达目的地机场的航班。
• 创建所有可能的路径（起点-连接-目的地）
• 将此列表修剪为所有“可能”的路径（消除不连续的连接，消除所有停留时间少于20分钟的路径）。
• 按总旅行时间（飞行时间+停留时间）对此列表进行排序。

没有一站式连接？

• 汇总所有从起始机场到“连接”机场（所有枢纽和重点城市）的航班。
• 汇总所有从任何“连接”机场（所有枢纽和重点城市）到达目的地机场的航班。
• 汇总所有在起始机场飞往的“连接”机场之间以及飞往目的地的“连接”机场之间的航班。（枢纽到枢纽）
• 创建所有可能的路径（起点-连接-连接-目的地）
• 将此列表修剪为所有“可能”的路径（消除不连续的连接，消除所有停留时间少于20分钟的路径）。
• 按总旅行时间对此列表进行排序。

- alexwood