python - 航类路线需要算法建议

我正处于通过野外旅行进行思考的早期阶段，该野外旅行涉及访问印度的每个商业机场。一项小小的研究表明，印度国家航空公司(Air India)拥有一张名为Silver Pass的特价机票，该机票允许在其国内网络上进行15天的无限制旅行。我想以此作为我选择的武器!

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

我在Excel中可以使用以下信息:

国内所有航线(国际航空运输协会代码中的出发机场和到达机场)

每个飞行路线的持续时间

每个航类的每周频率(例如，并非所有航类都在一周的全天运行)

有了这些信息，我如何确定使用银通票可以在15天内到达的最大机场数量是多少？在线查看表明，这要么是旅行商问题，要么是图形遍历问题。你们会建议我考虑些什么来解决这个问题。

我的一些背景知识-我才刚刚开始学习Python，并想找到一种使用它来解决此问题的方法。鉴于此，我应该考虑哪些基于python的算法/库来帮助我构建解决此问题的方法？

最佳答案

您的问题与Hamiltonian Path problem和Traveling Salesman Problem和NP-Hard密切相关。

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

每个顶点都是一个机场

每个边都是一个航类

所有航类都在同一时间起飞和起飞。(*)

(*)应该计算飞行时间和起飞时间(这是所有人共有的)，因此只有在每个候机楼只拜访一次的情况下，您才能够访问所有候机楼。它可以在多项式时间内轻松完成。假设机票的固定时间为k小时，我们构建航类表，以使每个航类正好花费k/(n-1)小时，并且每个k/(n-1)小时也有一个航类1(请记住所有航类都在同一时间)。

很容易看出，当且仅当图形具有哈密尔顿路径时，您才可以使用机票来访问所有机场，因为如果我们在路径中两次访问某个机场，则至少需要n航类，总时间至少为(k/(n-1)) * n > k，我们未能达到时限。 [其他方法类似]。

因此，您的问题(在一般情况下)是NP-Hard，而尚无已知的多项式解。

1:我们假设在两次飞行之间没有时间经过，可以通过简单地将飞行长度减少两个飞行之间的“跳跃”时间来轻松解决此问题。

关于python - 航类路线需要算法建议，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/9905461/