三个人以给定顺序访问某些图节点的最佳方式

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,因此将其存储为as 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的以下竞争性编程问题.根据规则,就我记忆而言,必须提供问题的根源

不幸的是,没有英文版的网站,所以我会试着描述这个问题.

输入包含G带L顶点的完整有向图和一些顶点列表(最多长度N).三个人1, 2, 3分别从顶点开始.他们必须从输入列表访问每个顶点,顺序重要,i + 1之后必须访问顶点i.在某个时间点,只有一个人可以进行移动(如果一个人从某个先前的顶点移动到顶点,i则其他人站立不动,他们不能并行移动).如果人/玩家站在顶点i并且必须移动到顶点,j他必须采用边缘(i, j)而不是到顶点j的一些最短路径(Floyd-Warshall算法不能用于加速计算).一个人可以访问一个顶点就足够了,这意味着所有人都可以被人1访问,而其他人则会静止不动.边缘的成本(i, i)总是0,没有多边缘,所有边缘权重都是非负的并且G表示为L x L邻接矩阵.输出这三个人访问顶点的最短可能路径的成本从列表amd输出访问每个顶点的人.要访问的顶点的输入列表是多重集(N可能大于L)

我发现这个问题有点类似于城市序列的双人遍历问题,除了这是一个三人版本,他们从不同的位置开始,并且人们必须通过重复访问特定的顶点序列的主要区别允许.我已经研究了这个问题的解决方案,时间复杂度将O(L^3) 用于城市序列的双人遍历,这将是O(N^4)我的问题,这太慢,因为即使O(N^3)算法也不会达到时间限制,我认为是喜欢O(LN^2)可以工作.

约束:

3≤L≤200,1≤N≤1000

0≤边缘重量≤2000

时间限制:1s,内存限制为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阶段的不同元组的数量是:

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内存限制.