algorithm - 时间表在有限时间内的最低成本？

Question

我有这样的时间表:

+-----------+-------------+------------+------------+------------+------------+-------+----+
| transport | trainnumber | departcity | arrivecity | departtime | arrivetime | price | id |
+-----------+-------------+------------+------------+------------+------------+-------+----+
| Q         | Q00         | BJ         | TJ         | 13:00:00   | 15:00:00   |    10 |  1 |
| Q         | Q01         | BJ         | TJ         | 18:00:00   | 20:00:00   |    10 |  2 |
| Q         | Q02         | TJ         | BJ         | 16:00:00   | 18:00:00   |    10 |  3 |
| Q         | Q03         | TJ         | BJ         | 21:00:00   | 23:00:00   |    10 |  4 |
| Q         | Q04         | HA         | DL         | 06:00:00   | 11:00:00   |    50 |  5 |
| Q         | Q05         | HA         | DL         | 14:00:00   | 19:00:00   |    50 |  6 |
| Q         | Q06         | HA         | DL         | 18:00:00   | 23:00:00   |    50 |  7 |
| Q         | Q07         | DL         | HA         | 07:00:00   | 12:00:00   |    50 |  8 |
| Q         | Q08         | DL         | HA         | 15:00:00   | 20:00:00   |    50 |  9 |    
| ...       | ...         | ...        | ...        | ...        | ...        |   ... | ...|
+-----------+-------------+------------+------------+------------+------------+-------+----+

这张表中共有13个城市，116条线路，最小的时间单位是半小时。 有不同的运输方式，这无关紧要。如您所见，可以有多个具有相同出发城市和到达城市但不同时间和不同价格的边缘。时间每天都是固定的。

现在，这里出现了一个问题。

一个用户想知道他如何从城市 A 到城市 B(A 和 B 可能是一个城市)，通过零或一些城市 C，D ...(他们是否应该是顺序取决于用户是否希望它是，即有两个问题)，在 X 小时内并且成本最低在上述条件下。

在这个问题之前，我已经解决了另一个更简单的问题。

一个用户想知道他如何从城市 A 到城市 B(A 和 B 可能是一个城市)，通过零或一些城市 C，D ...(他们是否应该是按顺序取决于)，在上述条件下成本最低。

我是这样解决的(以排序不对为例):

1. 对必须经过的城市进行排序:C1、C2、C3...Cn。令 C0 = A, C(n+1) = B, minCost.cost = INFINITE;
2. i = 0，j = 1，W = {}；
3. 使用 Dijkstra 算法以价格作为边的权重找到从 Ci 到 Cj 的最小成本路径 S。 W=W∪S;
4. i = i + 1, j = j + 1;
5. 如果 j <= n + 1，转到 3；
6. 如果 W.cost < minCost.cost, minCost = W;
7. 如果 C1...Cn 的下一个排列存在，则按照 C1...Cn 的下一个排列的顺序重新排列列表 C1...Cn 并转到 2；
8. 返回最小成本；

但是，我无法对第一个问题提出有效的解决方案，请帮助我，谢谢。

如果有人能解决另一个问题，我将不胜感激:

一个用户想知道他如何从城市 A 到城市 B(A 和 B 可能是一个城市)，通过零或一些城市 C，D ...(他们是否应该是按顺序取决于)，在最短时间内在上述条件下。

Answer 1

这是一个很大的问题，所以我只是勾勒出一个解决方案。

首先，按如下方式改造您的图表。让一个顶点代表一个 (city, time) 的元组，而不是每个顶点代表一个城市。 .这是可行的，因为只有 13 个城市并且只有 (time_limit - current_time) * 2可能的时间段为最小的时间单位是半小时。现在根据给定的时间表连接顶点，价格像以前一样作为它们的权重。不要忘记，用户可以免费在任何城市停留任何时间。城市的所有节点 A是起始节点，所有带有 city B 的节点是目标节点。取所有(B, time)的最小值顶点以最少的成本获得解决方案。如果有多个，取时间最短的那个。

现在开始强制用户按顺序通过某些城市。如果有n要经过的城市(加上起点和目标城市)，你需要n+2充当不同级别的同一图形的副本。该级别表示您已经通过了列表中的多少个城市。因此，您从顶点 A 的级别 0 开始.一旦你到达 C1在 0 级你移动到顶点 C1在图的第 1 层(通过 0 权重边连接顶点)。这意味着当你在k级时，你已经通过了城市C1至 Ck只有通过C(k+1)才能进入下一个级别.城市的顶点B最后一层是您的目标节点。

注意:我说的是同一张图的副本，但这并不完全正确。您不能让用户访问 C(k+2), ..., B在级别 k ，这将违反所需的顺序。

为了强制以任何顺序经过城市，需要一种不同的连接级别(并在运行时修改它们)的方案。我会把这个留给你。