需要对飞行路线提出算法建议

Question

我正处在一次疯狂旅行的早期阶段，这趟旅行涉及到访问印度的每一个商业机场。一项小小的研究表明，印度航空公司( Air )有一张名为银道的特价机票，允许他们在国内网络上进行15天的无限制旅行。我想用这个作为我选择的武器！

印度航空公司提供的所有机场的地图见此

我在Excel中有以下信息：

• 所有国内航线(国际航空运输协会代码中的起飞机场和抵达机场)
• 每条航线的飞行时间
• 每班航班的每周班次(例如，并非所有航班都在一周的所有天运行)

考虑到这些信息，我如何才能计算出使用银证票在15天内可以到达的机场的最大数量？在线观察表明，这要么是旅行商问题，要么是图遍历问题。你们建议我找什么来解决这个问题。

关于我自己的一些背景-我刚刚开始学习Python，我想找出一个方法来解决这个问题，使用它。既然如此，我应该看的基于python的算法/库是什么，它将帮助我构造一种解决这个问题的方法？

Answer 1

将问题表示为图绝对是最好的选择。由于持续时间、航班数目和机场数目都相对有限，而且(想必)你对近似的解决办法感到满意，所以用武力攻击这个问题应该是可行的，而且可能是你最好的选择。我大概会这样做：

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

根据航班数量，您可能能够详尽地运行此过程。当然，随着飞行次数的增加，解决方案的数量也会成倍增长，因此这将很快变得不切实际。这就是评分函数变得有用的地方--它优先考虑解决方案，更有可能产生有用的答案。只要您愿意，您可以运行该过程，并在它产生您满意的解决方案时停止运行。

评分函数的性质将对解的好坏有很大的影响。如果您的优先事项是探索独特的地方，您希望对未访问的机场给予很大的重视，并且由于您希望尽可能多地探索，您需要优先考虑短的转机时间。我对起点的建议是，对你已经与从那里飞到其他地方所需的时间成正比的地方进行惩罚。这样的话，我们仍然会把它当作中途停留，但在可能的情况下尽量避免。另外，请注意，您的评分函数将需要上下文，即由当前候选路径访问的机场集。

还可以使用评分函数应用其他约束。假设你不想在晚上旅行(一个合理的假设)；你可以惩罚那些涉及夜间航班的边缘。