2024年2月9日发(作者：威图手机是诺基亚旗下的吗)

俄罗斯套娃奖品

1. 问题描述：

伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。现在，路口放着纯金打造的俄罗斯娃娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的娃娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。”

请你为伊万洛夫规划路线，使得他能够有最大的收获。

Input:

输入包括多组测试用例；

每个测试用例开始是一对整数，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数（或0）W[r,c]，分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量（或表示没有放置娃娃）。

Output:

输出能有最大收获的路径规划。

假设1：

2 7

1 2 13 6 7 12 11

14 3 4 5 8 9 10

输出：

1 2 3 4 5 6 7 8 9 10 11 12

假设2：

5 5

1 16 15 14 13

2 17 24 23 12

3 18 25 22 11

4 19 20 21 10

5 6 7 8 9

输出：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

注释:

1)从<0,0>出发;

2)路线不能重复;

3)不要求最后回到出发点。

2．问题分析及算法思想

2.1 问题分析

俄罗斯套娃问题是一个复杂的最优化问题，如果将道路矩阵上的道路交叉口抽象为有向图上的一个顶点，那么俄罗斯套娃问题可以抽象为一个这样的问题：

（1）在该有向图图上只有这样的顶点之间有弧：a）两个顶点必须处于这样的位置：处于同一列并且行相邻或是处于同一行并且列相邻；b）当弧尾处的套娃的重量不为0时，

弧头处套娃的重量必须大于弧尾处套娃的重量或是弧头处套娃的重量为0；当弧尾处套娃重量为0时，弧头处套娃的重量必须大于到达该弧尾的最后一个套娃不为0的套娃的重量或是弧头处套娃的重量为0。例如1 0 0 3 从1到3是连通的，但是3 0 0 1 从3到1不是连通的。

（2）弧的权为弧尾处套娃的重量。

（3）所求的问题即转化为求出发点开始的权值最大的路径。

从上面的分析可以看出，俄罗斯套娃问题的难点在与怎么样处理套娃重量为0的时候路径的连通问题和怎么样用求最大权值路径的问题。

2.2 解决办法

1、套娃重量为0问题的处理方法。

对于顶点a，如果它的下一个顶点b处的套娃重量为0，则将a至b的路径连通，弧的权为0，并且将顶点b处的套娃重量置为顶点a处套娃的重量。多个顶点套娃重量为0的情况依次例推。

例如：

2 0 0 3

0 1 4 5

按上面的算法的处理，从<0,0>点到<0,1>即20时 弧的权值为0，但是此时将<0,1>点处的套娃重量设置为<0,0>点套娃的重量2，这样使得<0,1>点到<1,1>点之间是不连通的，因而保证了算法运行的结果符合题目的要求。

2、求最大权值路径的问题。

有了上面对套娃重量为0问题的处理方法后，最大权值路径的问题就变的相对简单了，我们采用图的深度优先遍历思想，设置变量maxweigh保存当前深度遍历中路径的最大权值，sumweight保存从出发顶点到当前顶点的路径的权值，数组mlp保存当前深度遍历中最大权值并且路径长度最短的路径，数组path保存正在遍历的路径，二维数组visited为访问过的顶点做标记，经过一次深度优先遍历即可得到符合题意的最优路径。同时我们还设置了变量maxlen来保存当前深度遍历中最大权值的路径的长度，利用在遍历时进行判断，我们可以得到最大权值路径集合中长度最短的一个路径，从而使得所得结果为符合题意并且长度最短的路径，即为最佳路径。

2.3 算法思想

采用图的深度优先遍历思想，从出发顶点开始，对与出发顶点有弧的每一个顶点同样深度优先遍历，依次例推，直到遍历完所有的顶点。在遍历的过程中，对每一个顶点做如下的四个记录：从出发顶点到当前顶点的路径的权值和sumweight；从出发顶点到当前顶点的路径的长度len；当前顶点套娃的重量currentweight（如果当前顶点套娃的重量为0，按上文的方法处理）；访问标记visited。

递归终止的条件是以当前顶点为弧尾的弧都遍历过，或是没有以当前顶点为弧尾的弧。在每一次递归终止的时候，如果sumweight大于maxweigh或是sumweight等于maxweigh并且maxlen大于len时，将当前路径保存为当前深度遍历中最大权值的路径。

由上面的算法思路可知，在深度优先遍历完成后，数组mlp里面保存的路径即为俄罗斯套娃问题的最优路径。

3．实现方法

（1）程序中几个重要变量的介绍：

mlp[MAXSIZE]：保存当前深度遍历中最大权值并且路径长度最短的路径；

path[MAXSIZE]：保存正在遍历的路径；

maxlen：保存当前深度遍历中最大权值的路径的长度；

maxweigh：保存当前深度遍历中路径的最大权值；

row：保存套娃矩阵的行的大小；

line：保存套娃矩阵的列的大小；

data[MAXSIZE][MAXSIZE]：保存套娃矩阵的重量；

visited[MAXSIZE][MAXSIZE]：保存访问过的顶点做标记。

（2）深度优先遍历方法的实现：这是本程序的核心和关键，用void DSF(int x,int y,int

sumweight,int len,int currentweight)函数实现，其中x，y表示当前顶点在套娃矩阵中的位置；sumweight表示从出发顶点到当前顶点的路径的权值和；len表示从出发顶点到当前顶点的路径的长度；currentweight表示当前顶点套娃的重量，当前顶点的套娃重量为0时，按前面对套娃重量为0的方法处理。具体执行流程如下：

1、没有以当前顶点为弧尾的弧或所有弧头顶点都已经访问过时：

a、如果sumweight大于maxweigh时，将当前路径path里面的路径保存到最大权值mlp里面（保存最大路径）；

b、如果sumweight等于maxweigh并且maxlen大于len时，当前路径path里面的路径保存到最大权值mlp里面（保存最大路径中的最短路径）；

c、将该顶点的访问标记清除。

2、有以当前顶点为弧尾的弧并且该弧头顶点没有被访问过时：

a、如果弧头顶点为0时：

DSF(x, y, sumweight,len+1, currentweight)，其中x，y为该弧头顶点的坐标，sumweight，len，currentweight均为弧尾顶点时的sumweight，len，currentweight。

b．如果弧头顶点不为0时：

DSF(x,y,sumweight+data[x][y],len+1,data[x][y])，其中x，y为该弧头顶点的坐标，sumweight，len均为弧尾顶点时的sumweight，len，,data[x][y]为该弧头顶点处的套娃重量。

按上面的算法依次递归，待递归结束后，数组mlp里面保存的路径即为该俄罗斯套娃问题的最短路径的解。

4．复杂度分析

本程序采用递归的方法来求解的，而递归算法的复杂度通常很难衡量，一般都认为是每次递归分支数的递归深度次方，那么复杂度就是O（n4），但是在本程序中远远没有这么大，当且仅当套娃矩阵中套娃重量全为0时，才会出现O（n4），而实际的套娃矩阵中套娃的重量为0的比例为多少我们无法准确判断。通过对测试用例观察，发现套娃矩阵中套娃重量不为0的为大多数，所以复杂度远远小于O（n4），平均来说，每一次递归分支数为2个左右，因此平均的复杂度为O（n2）。

5．程序使用及测试用例

5.1 程序使用

本程序采用C++语言编写，运行环境为visual C++ 6.0。输入文件为，文件开始是一对整数，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数（或0）W[r,c]，分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量（或表示没有放置娃娃）。输出文件为，里面存放的是有最大收获的路径规划。另外该程序里面定义了一个const整型，如果总的路口数大于该const整型，则需改变此const的值。

5.2 测试用例

为测试本程序的正确性，采用了五组测试用例，各组的输入数据和输出结果分别如下所示：

第一组：输入数据为

2 7

1 2 13 6 7 12 11

14 3 4 5 8 9 10

输出结果为

1 2 3 4 5 6 7 8 9 10 11 12

第二组：输入数据为

5 5

1 16 15 14 13

2 17 24 23 12

3 18 25 22 11

4 19 20 21 10

5 6 7 8 9

输出结果为

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

21 22 23 24 25

第三组：输入数据为

6 6

1 0 0 0 0 0

14 0 3 0 0 0

13 0 0 4 0 0

12 0 0 0 5 0

11 10 9 8 7 6

输出数据为

1 0 0 3 0 4 0 5 0 6 7 8 9 10 11 12 13 14

第四组：输入数据为

7 7

1 2 0 4 0 0 0

0 2 0 0 0 2 0

13 0 3 0 0 0 7

0 0 0 4 0 0 0

12 0 10 0 5 0 0

0 0 10 0 5 6 0

11 0 9 0 8 0 7

18 19 20

输出数据为

1 0 2 0 3 0 4 0 0 5 6 0 7 0 8 0 9 10

0 0 11 0 12 0 13

第五组：输入数据为

10 10

1 2 0 4 0 0 0 0 12 13

10 2 0 0 0 2 0 17 19 0

33 0 3 0 0 0 7 17 16 15

0 32 0 4 0 0 0 0 0 19

30 0 10 0 5 0 0 3 21 20

0 28 10 0 5 6 0 5 22 20

29 0 27 0 25 0 24 23 0 0

31 0 27 27 20 12 0 21 25 0

0 33 34 0 19 0 32 35 36 37

31 32 36 0 38 39 40 41 42 43

输出数据为

1 2 0 0 3 0 4 0 0 5 6 0 0 0 7 0 0 0 12

13 0 15 16 17 0 0 19 20 21 22 0 23 24 0 25

0 27 0 28 0 29 31 0 33 34 36 0 38 39 40 41

42 43

6 总结

本程序实现了一个在给定东西和南北路的条数和各个路口套娃的质量的情况下，求得到最大收获的问题。在该程序中，首先将此问题抽象为一个带有权值路径的有向图问题，然后通过有向图的深度遍历来求最大权值路径。经过五组不同的测试用例测试表明该程序运行正确，达到了预期的结果，而且还能够保证在很多零的情况下，得到的路径最短。在实现该程序的过程中，我们小组也遇到了一些问题，比如当套娃的权重为零时该如何处理等等，但经过我们小组成员的共同探讨，最终问题得到了解决。