需要针对飞行路线的算法建议

Question

我正在思考一次涉及访问印度每个商业机场的疯狂旅行的早期阶段.一项小小的研究表明,国家航空公司 - 印度航空公司有一张名为Silver Pass的特殊机票,可以在国内网络上无限制地旅行15天.我想用它作为我的首选武器!

有关印度航空所服务的所有机场的地图,请参阅此页

我在Excel中可以获得以下信息:

• 所有国内航线(出发地机​​场和国际航空运输协会代码的到达机场)
• 每条航线的持续时间
• 每个航班的每周频率(例如,并非所有航班都在一周中的所有日期运行)

根据这些信息,我如何确定使用Silver Pass机票在15天内可以达到的最大机场数量是多少？在线查看显示这是一个旅行推销员问题或图形遍历问题.你们会建议我解决这个问题.

关于我自己的一些背景 - 我刚刚开始学习Python,并希望找到一种方法来解决这个问题.鉴于此,我应该关注哪些基于python的算法/库将帮助我构建解决此问题的方法？

Answer 1

你的问题与汉密尔顿路径问题和旅行推销员问题密切相关,它们是NP-Hard.

给定哈密顿路径问题的实例 - 建立飞行数据:

1. 每个顶点都是一个机场
2. 每个边缘都是一个航班
3. 所有航班都在同一时间离开,并且需要同一时间.(*)

(*)应计算飞行持续时间和出发时间[对所有人来说都是共同的],这样只有当您每次访问每个终端时,您才能访问所有终端.它可以在多项式时间内轻松完成.假设我们有一个固定的时间k给票小时,我们构建的飞行表使得每个飞行恰恰k/(n-1)小时,且有每飞行k/(n-1)小时以及¹ [记住所有航班在同一时间.

很容易看出,当且仅当图表有汉密尔顿路径时,您可以使用机票访问机场,因为如果我们在路径中访问某个机场两次,我们至少需要n航班,总时间将是至少(k/(n-1)) * n > k,我们没有时间限制.[其他方式类似].

因此,你的问题[一般情况]是NP-Hard,并且没有已知的多项式解决方案.

1:我们假设没有时间在航班之间通过,这可以通过简单地减少航班长度到在两个航班之间"跳跃"所需的时间来轻松修复.