algorithm - 航类票价的 TSP

Question

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

举个例子:从洛杉矶国际机场出发访问 LV、CA、NY结束 LAX。

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

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

01 - LAX - LV；
04 - 低压 - CA；
08 - 加利福尼亚 - 纽约；
15 - 纽约 - 洛杉矶国际机场

所以我明白我可以在边上放置额外的属性，但问题是算法将如何区分如何遍历图，例如不选择过去已经具有最小权重的边。

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

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

希望我说到点子上了，任何建议表示赞赏

提前致谢。

Answer 1

我理解你的问题的方式，你需要在特定时间之前到达的最便宜的路径。如果是这样的话，一个可能的答案是你仍然只根据航类的价格来解决它，同时针对队列中的每个可能的答案(我假设像 Dijkstra 这样的方法)你会保留已经过了多少时间(用于与截止日期进行比较)。

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

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