我正在思考一次涉及访问印度每个商业机场的疯狂旅行的早期阶段 . 一项小小的研究表明，国家航空公司 - 印度航空公司有一张名为_1678063的特殊机票，允许在国内网络上无限制地旅行15天 . 我想用它作为我的首选武器！
See this for a map of all the airports served by Air India
我在Excel中可以获得以下信息：
-
所有国内航线（出发地机场和国际航空运输协会代码到达机场）
-
每条航线的持续时间
-
每个航班的每周频率（例如，并非所有航班都在一周中的所有日期运行）
根据这些信息，我如何确定使用Silver Pass机票在15天内可以达到的最大机场数量是多少？在线查看显示这是一个旅行推销员问题或图形遍历问题 . 你们会建议我解决这个问题 .
关于我自己的一些背景 - 我刚刚开始学习Python，并希望找到一种方法来解决这个问题 . 鉴于此，我应该关注哪些基于python的算法/库将帮助我构建解决此问题的方法？
2 回答
您的问题与Hamiltonian Path problem和Traveling Salesman Problem密切相关，它们是NP-Hard .
给定哈密顿路径问题的实例 - Build 飞行数据：
每个顶点都是机场
每条边都是一个航班
所有航班同时离开并需要同一时间 . （*）
（*）应计算飞行持续时间和出发时间[对所有人来说都是共同的]，这样只有当您每次访问每个终端时，您才能访问所有终端 . 它可以在多项式时间内轻松完成 . 假设我们有一个固定时间为
k小时的机票，我们构建了航班表，每个航班的时间恰好为k/(n-1)小时，每隔_1678070小时也有一班航班[记住所有航班都在同一时间] .很容易看出，当且仅当图表有哈密尔顿路径时，您可以使用机票访问机场，因为如果我们在路径中两次访问某个机场，我们至少需要
n个航班，总时间将会至少(k/(n-1)) * n > k，我们没有时间限制 . [其他方式类似] .因此你的问题[一般情况]是NP-Hard， there is no known polynomial solution for it.
1：我们假设没有时间在航班之间通过，这可以通过简单地减少航班长度到在两个航班之间“跳跃”所需的时间来轻松修复 .
将您的问题表示为图表绝对是最佳选择 . 由于持续时间，航班数量和机场数量相对有限，并且由于您（大概）对近似解决方案感到满意，因此通过强力攻击应该是实用的，并且可能是您的最佳选择 . 这大致是我要做的：
将每个机场表示为图表上的节点，并将每个航班表示为边缘 .
如果是起始机场和当前时间，请选择当前时间之后离开该机场的所有航班 . 使用某种评分功能对它们进行排名，这样就可以飞往您所访问过的机场，并且航班的排名越高越好 .
以分数的顺序递归探索每个传出边缘，并重复到达机场的程序 .
每次到达没有传出有效边的节点时，请将其与最佳解决方案进行比较 . 如果它是一个改进，输出它并将其设置为新的最佳解决方案 .
根据航班的数量，您可以详尽地执行此程序 . 当然，解决方案的数量随着航班的数量呈指数增长，因此这将很快变得不切实际 . 这是评分功能变得有用的地方 - 它优先考虑更有可能产生有用答案的解决方案 . 您可以根据需要运行该过程，并在产生您满意的解决方案时停止 .
评分功能的属性将对解决方案的好坏产生重大影响 . 如果您的首要任务是探索独特的地方，那么您希望对未访问的机场投入大量资金，并且由于您希望尽可能多地探索，因此您需要优先考虑短的转移时间 . 我对起点的建议是对你已经与它的时间成正比的地方进行惩罚从那里飞到其他地方 . 这样，它仍将作为中途停留进行探索，但尽可能避免 . 另请注意，您的评分功能将需要上下文，即当前候选路径已访问过的一组机场 .
您还可以使用评分功能来应用其他约束 . 假设您不想在夜间旅行（合理的假设）;你可以惩罚涉及夜间飞行的边缘得分 .