需要针对航班路线的算法建议

Question

我正在初步考虑一次疯狂的旅行计划，包括访问印度所有商业机场。初步调查显示，国家航空公司——印度航空公司，有一种特殊的门票叫做银行智能客户端，可以在其国内网络上无限制地旅行15天。我想选择使用它！

查看印度航空服务的所有机场地图

我手头有以下Excel信息：

• 所有国内航班路线（出发机场和到达机场的IATA代码）
• 每个航班路线的飞行时间
• 每个航班每周的频率（例如，并非所有航班每天都运行）

在这些信息下，如何计算使用银票15天内可以到达的最大机场数量？在线搜索显示这是旅行商问题或图遍历问题。你们建议我看什么来解决这个问题。

关于我自己的背景-我刚开始学习Python，并希望找到一种用Python解决此问题的方法。鉴于此，我应该查看哪些基于Python的算法/库，以帮助我构建解决方案？

- Scubed

---

你是在进行一次智力锻炼吗？还是你认真考虑要做这件事情？ - MattH

你为什么要花费15天时间在终端上感到压力呢？ - orlp

@MattH，肯定在考虑这个。需要弄清楚路由，然后再计算成本。显然，除了银级通行证的费用外，还有每次飞行的路线费用，这将根据旅行距离而变化。但是，在确定路由时，我现阶段不考虑这一点，因为我不想让事情变得更加复杂。 - Scubed

@nightcracker 我是一个FlyerTalk的会员 - 这样解释清楚了吗？ :) - Scubed

你有一个固定的起点吗，还是可以从网络上的任何地方开始？ - Nick Johnson

Answer 1

你的问题与哈密顿回路问题和旅行商问题密切相关，它们都是NP难问题。

给定一个哈密顿路径问题实例-构建一个航班数据：

1. 每个顶点是一个机场
2. 每条边是一次航班
3. 所有航班同时起飞并花费相同的时间。（*）

(*) 飞行持续时间和出发时间[对于所有人来说都是相同的]应该被计算，以便您只有在每个终端只访问一次时才能访问所有终端。这可以很容易地在多项式时间内完成。假设我们有一个固定的票务时间k小时，我们构造飞行表格，使得每次飞行正好需要k /（n-1）小时，并且也有每k /（n-1）小时的一次航班¹ [记住所有航班都是同时进行的]。

很容易看出，当且仅当图有哈密顿路径时，您才能使用机票访问所有机场，因为如果我们在路径中两次访问某个机场，则我们需要至少n次航班，并且总时间将至少为(k/(n-1)) * n > k，这样我们就无法通过时间限制。[反之亦然]。

因此，对于一般情况，您的问题是NP-Hard，且目前没有已知的多项式解决方案。

---

1：我们假设在航班之间没有时间消耗，这个问题可以通过将飞行时长减去“跳”两个航班之间所需的时间轻松解决。

- amit

---

此外，本次练习的目的并不是要访问所有机场。以下是一些限制条件：Air India的路线网络、航班时间、每周可用的航班数量、通行证的有效期为15天以及一天的小时数为24小时。在这些限制条件下，从预定义的起点出发，最多能访问多少个机场？ - Scubed

@Scubed：我说目前没有已知的多项式算法可以解决这个问题。如果你想要最优解，可以尝试暴力搜索，但这将需要很长时间[可能是几十年甚至更长时间]。数学方面的注释：当我说“没有已知”的时候，是因为我们对计算的理解仍然有限，我们还没有能够证明是否存在多项式算法来解决这些问题。一般的假设是不存在，但这并没有被证明。 - amit

@Scubed：访问尽可能多的机场是访问所有机场问题的优化问题，这两个问题在理论复杂度方面是相同的。 - amit

@amit - 现在没有已知的算法来解决这个问题，暴力破解是必需的，这很有道理。您是否知道是否有任何基于启发式的方法来解决这个问题？ - Scubed

没有理由认为暴力算法的速度会像你所说的那样慢 - 机场和航班数量是相当有限的。 - Nick Johnson

Answer 2

将问题表示为图形绝对是最佳选择。由于持续时间、航班数量和机场数量相对有限，而且您（大概）满意近似解决方案，通过蛮力攻击这个问题应该是可行的，也可能是您最好的选择。以下是我大致会做的事情：

• 将每个机场表示为图上的一个节点，将每个航班表示为一条边。
• 给定一个起始机场和当前时间，在当前时间之后选择所有离开该机场的航班。使用某种评分函数对它们进行排名，使未访问过的机场的航班优先级高于已访问过的机场的航班，并且航班越早排名越高。
• 按得分顺序递归地探索每个出边，并重复到达机场的过程。
• 每当您到达一个没有有效出边的节点时，请将其与最佳可能解决方案进行比较。如果它是一个改进，输出它并将其设置为新的最佳解决方案。

根据航班数量，您可以彻底运行此过程。当然，解决方案的数量随着航班数量呈指数增长，因此这很快就会变得不切实际。这就是评分函数有用的地方 - 它优先考虑更可能产生有用答案的解决方案。您可以在想要的时间内运行该程序，并在产生满意的解决方案时停止。

评分函数的性质将对解决方案的好坏产生重大影响。如果您的优先级是探索独特的地方，您需要为未访问的机场设定高额溢价，因为您希望尽可能多地探索，所以需要优先考虑短暂的转机时间。我建议您从设定去某个已经去过的地方的惩罚开始，该惩罚与从那里飞到其他地方所需的时间成比例。这样，它仍将被作为中途停留点探索，但在可能的情况下将被避免。此外，请注意，您的评分函数将需要上下文，即当前候选路径访问过的机场集合。

您还可以使用评分函数来应用其他约束条件。假设您不想在夜间旅行（一个合理的假设）；您可以对涉及夜间航班的边缘进行评分惩罚。

- Nick Johnson

---

感谢@Nick Johnson，您推荐的方法听起来不错。您有没有什么Python库或程序可以推荐我用来实现这种方法？我只知道GUESS和NodeBox，但我不确定是否应该使用这些程序？感谢您的帮助。 - Scubed

@Scubed，你不需要任何库——所有这些都可以直接在纯Python中实现，这样做可能是一个很好的练习。 - Nick Johnson