需要航班路线的算法建议吗

Question

我正处于一次疯狂旅行的早期阶段，这次旅行包括参观印度的每一个商业机场。一项小调查显示，印度国家航空公司有一张名为Silver Pass的特价机票，可以在其国内网络上无限旅行15天。我想用这个作为我选择的武器！在

See this for a map of all the airports served by Air India

我在Excel中有以下信息：

• 所有国内航线（IATA代码中的出发机场和到达机场）
• 每条航线的持续时间
• 每个航班的每周频率（例如，并非所有航班都在一周中的所有日期运行）

有了这些信息，我如何计算出使用银票在15天内最多可以到达多少个机场？在网上看，这要么是一个旅行推销员问题，要么是一个图遍历问题。你们建议我看些什么来解决这个问题。在

关于我自己的一些背景知识-我刚刚开始学习Python，我想用它来解决这个问题。鉴于此，我应该研究哪些基于python的算法/库来帮助我构建解决这个问题的方法？在

Answer 1

把你的问题用图表来表示绝对是最好的选择。由于持续时间、航班数量和机场数量相对有限，而且（大概）您对近似解决方案很满意，所以用暴力手段来攻击应该是切实可行的，而且可能是您的最佳选择。我大概会这样做：

• 将每个机场表示为图中的一个节点，将每个航班表示为一条边。在
• 给定起始机场和当前时间，选择当前时间之后离开该机场的所有航班。使用某种评分功能对它们进行排序，例如，飞往你没有去过的机场的航班比你没有去过的机场的航班排名要高，航班的排名越早排名就越高。在
• 按得分顺序递归地探索每个出站边缘，并对到达的机场重复此过程。在
• 任何时候，当你到达一个没有输出有效边的节点时，把它与最好的解决方案进行比较。如果是改进，输出它并将其设置为新的最佳解决方案。在

这取决于你的航班数量。当然，随着航班数量的增加，解决方案的数量呈指数级增长，因此这将很快变得不切实际。这就是评分功能变得有用的地方——它优先考虑解决方案，更有可能产生有用的答案。您可以根据需要运行该过程多长时间，并在它产生您满意的解决方案时停止运行。在

评分函数的性质对解的好坏有很大的影响。如果你的首要任务是探索独特的地方，你就要把重点放在无人参观的机场上，而且既然你想探索尽可能多的地方，你就需要优先考虑较短的中转时间。我的建议是，对你已经去了某个地方的惩罚与从那里飞到另一个地方的时间成正比。这样的话，我们还是会把它作为中途停留地，但尽可能避免。另外，请注意，您的评分功能需要上下文，即当前候选路径访问过的机场集。在

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

Answer 2

您的问题与Hamiltonian Path problem和{a2}密切相关，它们是{a3}。在

给出一个哈密顿路径问题的例子-建立一个飞行数据：

1. 每个顶点都是一个机场
2. 每一条边都是一段距离
3. 所有航班在同一时间起飞，所用时间相同。（*）

（*）应计算航班持续时间和起飞时间[这对所有人来说都是常见的]，这样，只有在每个航站楼只访问一次时，您才能访问所有航站楼。它可以很容易地在多项式时间内完成。假设我们有一个固定的时间k小时，我们构建航班表，使每个航班正好占用k/(n-1)小时，并且每k/(n-1)小时有一个航班，¹[记住所有航班都在同一时间]。在

很容易看出，当且仅当图有哈密顿路径时，你可以使用机票访问al机场，因为如果我们在路径中访问某个机场两次，则至少需要n个航班，总时间至少为(k/(n-1)) * n > k，而我们的时间限制失败了。[另一方面也是相似的]。在

因此，[一般情况下]您的问题是NP难的，没有已知的多项式解。

---

我们可以简单地假设两个航班之间不需要时间间隔。在