algorithm - 三人按给定顺序访问某些图节点的最佳方式

Question

UPD .我解决了这个问题。

让 DP[i][vertex_a][vertex_b]是带有 i 的状态访问的城市和两个站在顶点的玩家 vertex_a, vertex_b (保证其中之一为 list[i] )。 WLOG 假设 vertex_a ≤ vertex_b像这样 DP表不包含有关球员位置的信息。从 DP[i][vertex_a][vertex_b] 只能到达三个状态，即 DP[i + 1][vertex_a][vertex_b] , DP[i + 1][list[i]][vertex_b] , DP[i + 1][vertex_a][list[i]] .我们也只需要存储两层DP ，所以只有 sizeof(int) * 2 * 200 * 200计算最佳路径成本所需的字节数。要获得路径，将有 last_move_id[i][vertex_a][vertex_b]携带有关在状态下移动的玩家的信息 DP[i][vertex_a][vertex_b]和 last_move_positions[i][vertex_a][vertex_b]存储玩家到达的顶点数量list[i] .由于顶点数不超过 200，因此可以将它们存储为 byte ，所以 sizeof(byte) * 1000 * 200 * 200每个数组的字节数。为了维护这些数组，必须有另一个数组 positions[i][vertex_a][vertex_b][3]携带每个玩家的位置信息，只需要最后两层，所以sizeof(byte) * 2 * 200 * 200 * 3这个字节。时间复杂度 O(N * L * L) .

我的 C++实现使用 76Mb和 320 ms .

我正在努力解决来自俄罗斯在线法官的以下竞争性编程问题 http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 .根据规则，必须提供我记得的问题的来源

不幸的是，没有英文版的网站，所以我会尝试描述问题。

Input consists of the complete digraph G with L vertices and some list of vertices (length at most N). Three people start at vertices 1, 2, 3 respectively. They have to visit each vertex from the input list, order matters, vertex i + 1 is necessarily visited after i. At one point of time only one person can make a move (if one person goes from some previous vertex to vertex i others stand still, they can't move in parallel). If person/player stands at vertex i and has to move to vertex j he must take an edge (i, j) instead of some shortest path to vertex j (Floyd–Warshall algorithm can't used to speed up computations here). It is sufficent for a vertex to be visited by a single person which means that all of them can be visited by person 1 while other would stand still. The cost of edge (i, i) is always 0, there are no multi-edges, all edge weights are non-negative and G is represented as L x L adjacency matrix. Output the cost of shortest possible path for these three people to visit vertices from list amd output what person visited each vertex. Input list of vertices to be visited is a multiset (N may be bigger than L)

我发现这个问题有点类似于城市序列的两人遍历问题，除了这是一个三人版本，它们从不同的位置开始，主要区别是人们必须重复访问特定的顶点序列允许。我研究了这个问题的解决方案，时间复杂度是 O(L^3) 对于城市序列的两人遍历，它将是 O(N^4)对于我的问题，即使 O(N^3) 也太慢了算法不会满足时间限制，我认为类似 O(LN^2)虽然可以工作。

约束:

3 ≤ L ≤ 200, 1 ≤ N ≤ 1000

0 ≤ edge weight ≤ 2000

Time limit: 1s, memory limit is 256 Mb

我也确信可以使用 64 Mb 解决此问题。

这个问题被标记为 2D dynamic programming .

我真的想不出这个确切的 2D动力学。我想到了一个非常简单的方法来解决这个问题:

三人初始状态为 (1, 2, 3) .在处理第一个顶点时，我们计算:
1:(list[1], 2, 3) = (1, 2, 3) + weight(1, list[1]) 1:(1, list[1], 3) = (1, 2, 3) + weight(2, list[1]) 1:(1, 2, list[1]) = (1, 2, 3) + weight(3, list[1]) .

如您所见，这是一个 4D动态表，但我认为保持当前迭代次数是不必要的，使其成为 3D一。此外，可以注意到，对于计算第 (i+1) 层，第一层只需要有关第 i 层的信息，这使其成为一种很好的内存优化。尽管如此，如果我们忘记图中最多只有 200 个顶点并将状态视为元组 (i, j, k) , 其中 i, j, k 是最后阶段 1, 2, 3 移动的人数，这意味着在第 m 阶段 i, j, k 中的一个等于 m。按照这个逻辑并考虑所有可能的重复，第 m 个阶段的不同元组的数量是:
Number_at_stage(m) = Number_at_stage(m - 1) + 6 * (m - 1) , Number_at_stage(1) = 3, Number_at_stage(2) = 9, Number_at_stage(1000) = 2991009. Number_at_stage(1)我从以下想法中得到:
(0, 0, 0) -> (1, 0, 0), (0, 1, 0), (0, 0, 1)
我已经汇总了各个阶段的不同元组的数量 1..1000并得到了一个可怕的数字 997004997这几乎是十亿。这意味着代表这种移动的不同元组的数量是渐近三次的(并不奇怪，但很明显)。我不明白如何改进这个想法。以这种方式思考，我不知道如何处理诸如 (i, j, k) 和 (k, j, i) 之类的状态，因为它们实际上是等效的，因为可以基于相同的步骤集在这些上。我只是不知道如何处理这些状态并保留信息哪些人访问了哪个城市(简单的多维数组？)。

我的下一个想法是使用二维 DP(i, j) 存储从 i 到 j 的元素的子列表的最佳距离总和。如果索引从 1 开始，答案将存储在 DP(1, N) 中。我可以计算长度为 1, 2, ... N 的所有子集。这个想法有一个主要问题，我不知道如何在不知道玩家可以站立的所有潜在位置的情况下处理 DP(i, j)(列表中的所有元素都在 i 和初始位置 1、2、3 之前)。我也不知道如何通过这种方法确定哪个玩家采取了行动。

你能帮我找到 2D 动力学吗？

Answer 1

给出 list[i] 时 3 个玩家的可能状态被访问，以及到目前为止与每个这样的状态相关的成本，计算 list[i+1] 的可能状态和成本.当您到达 list[N-1] ，选择最低成本。保留前导链接，以便您可以遍历整个序列回到开头并输出它。

我很确定你已经得到了这么多......这是你错过的部分:

当list[i]时有多少个可区分的状态被访问了？嗯，还不到 L^3 ，因为哪个玩家在哪个顶点上并不重要。也小于 L^3/3! ，因为显然至少有一名玩家在 list[i] 上!

因此，一名玩家在 list[i] 上并且只有 L(L+1)/2 其他球员可区分的位置。这意味着最多有 20100 每个 list[i] 的可能状态，以及每个列表索引的整个可能性数组中大约 20M 可能的状态。如果您对存储状态和链接的方式稍加小心，则可以满足 256MB 的内存限制。