algorithm - 机票票价的 TSP

Question

我正在尝试用机票解决旅行推销员问题，所以主要想法是从一个机场开始，只访问所有机场一次，然后返回原点。

例如：从 LAX 出发访问 LV、CA、NY 结束 LAX。

这是一个经典的图问题，我们可以将机场表示为节点，将路线表示为边，价格作为边权重。

所以这是最简单的部分，真正让我困惑的是用户希望旅行的日期。例如，我想让用户选择他/她希望旅行的日期，比如从 01 开始到 15 结束。所以我想找到一种最便宜的方式来做到这一点。例如输出将是这样的：

01 - LAX - LV; 04 - LV - CA; 08 - CA - NY; 15 - NY - LAX

所以我知道我可以在边上添加额外的属性，但问题是算法将如何区分如何遍历图形，例如不选择过去权重最小的边。

所以你可以看到我有两条边从 CA 出来（注意边的格式是 DD - 价格，01 - 20 表示日期的第一个和成本 20），以及当多个边相同时如何处理这种情况节点存在。

它也可以被视为三维图，其中第三维是用户旅行的日期。所以主要问题是如何处理这些日期？

希望我明白了，任何建议表示赞赏

提前感谢。

Answer 1

我理解您的问题的方式是，您需要在特定时间之前到达的最便宜的路径。如果是这种情况，一个可能的答案可能是你仍然只根据航班的价格来解决它，同时对于队列中的每个可能的答案（我假设像 Dijkstra 这样的方法）你保持多少时间已经过去（用于与截止日期比较）。

每当您想添加可能答案的邻居时，您可以检查它是否在截止日期之前，如果不是，则忽略该实例。

在夏季，您仍然会按顺序找到从最便宜到最昂贵的所有可能路径，然后选择第一个与您的截止日期不矛盾的路径。