algorithm - 高效地编写航空公司路由算法

Question

给定:

• 航类数据库(出发城市、到达城市、出发时间、到达时间)。

问题:

• 如果出发时间不重要，列出两个城市之间服务的最有效算法是什么？考虑到我们想要最小化中转时间(但仍高于标称的最小值，即 20 分钟)，并最小化中途停留的次数(如果有直达路线，这是微不足道的，但如果没有，则在两个以上找到一个连接路线-连接等，合理的中途停留时间，不那么琐碎)。
• 如果可能的话，我不想专门将任何机场标记为枢纽，从而留下点对点航线网络的可能性。
• 应该有一个选项来指定所需的(大约)出发时间。如果它有自己的独立于第一个的算法就可以了。

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

Answer 1

在基础上，您将把您的城市网络视为一棵树，以出发城市为根，每个出发航类都是指向子项的指针。您将在树中执行递归深度优先搜索以找到到达目的地的所有路径，但在您进行时检查循环并中止导致循环的任何路径。

当您找到可行路径时，您可以只保留已找到的最短路径作为单一解决方案；或保留找到的更大路径子集，如果您想在此基础上进行选择，则根据出发时间的某些标准进行分层。

根据数据库和节点的具体情况，您还可以加入其他规则来缩短路径搜索，例如，如果您碰巧知道出发地和目的地相距 1000 英里，并且到目前为止您追踪的路径有你飞了 3000 英里，你仍然不在那里，去他的，继续下一个路径搜索。