问题纯手打：
比如有个二维数组a[5][5]是：
  1 5 9 8 5
  9 3 8 2 7
  3 7 9 1 6
  4 3 8 0 7
  0 8 3 9 4
假如第一个选择a[0][0]，记录b[0]=a[0][0],除去a[0][0]所在的行和列的所有数字（为表示方便，我用*补空位），只剩下了：
 * * * * *
 * 3 8 2 7
 * 7 9 1 6
 * 3 8 0 7
 * 8 3 9 4
继续上述操作，假如选择a[1][3],记录b[1]=a[1][3]后，除去它所在的行和列的所有数字（为表示方便，我用#补空位），即剩下：
 * * * * *
 * # # # #  
 * 7 9 # 6
 * 3 8 # 7
 * 8 3 # 4
以此类推，最后计算sum=b[0]+b[1]+b[2]+......+b[n];
求sum的最小和；   

我最开始是打算用两层循环的方式求解，把 * ，#这些的用数值 -1 替换，通过if（a[i][j]>=0）实现对这些*，#的忽略。
后来逻辑乱了。我又想用大量的伪随机数来实现，最后自己乱了也没做出来。

请问有人可以写一下这个程序的筛选和求和部分吗,比较急。

n的值？

这个举例里边n是4，就是sum从b[0]加到b[4]

这是一个关于哈密顿回路的问题~

一个行(列)代表一个顶点,两个顶点之间的距离等于该数字~


例如举个例子

A B C
1 2 3
4 5 6
7 8 9

这样


有三个顶点ABC

A->A 1
A->B 2
A->C 3

B->A 4
B->B 5
B->C 6

C->A 7
C->B 8
C->C 9

现在要求就是要在这里找若干个环,使得每个顶点都不多不少遍历一次~
正常来说这是一个TSP问题,也是一个NPC问题,说直接点就是没有什么有效算法可以在多项式的时间复杂度内有解,但是由于这个图每两个顶点任意相连,可以看出这是一个完全图,当然还是一个类似于TSP的NPC问题~

https://bbs.bccn.net/thread-476191-1-1.html

记得当时除了穷举然后啥都不知道,但现在嘛,里面的很多都有参考价值的(当然至于能不能看懂就是个问题了)~

PS:上面的算法不完善,然后删减了一下,基本结论出来了(这是一个类似于TSP的问题)用状态压缩dp看上去是o((n^2)*2^n),或者有更高效的算法,这里简单了解一下就可以了~

[此贴子已经被作者于2018-4-30 18:54编辑过]

收到的鲜花

• nosnoy 于 2018-04-30 16:00 送鲜花  1朵  

感谢提供思路

不用,因为表面看或者没啥问题,但仔细看的还有很多说不透彻或者有问题的地方,就当是一种思路就可以了~

我觉得楼主的问题。俺可以提供一种思路：
在最初是个a[5][5]的数组，可以另外提供四个数组，分别是a[4][4],a[3][3],a[2][2],a[1][1].
然后就开始计算：
第一次选择一个数后，把剩下的数就存入a[4][4]中，
第二次选择一个数后，把剩下的数就存入a[3][3]中，
第三次选择一个数后，把剩下的数就存入a[2][2]中，
第四次选择一个数后，把剩下的数就存入a[1][1]中，
设a[1][1]=K，最后统计所选择的这四个数和K之和就是sum,当然sum还不是最小的，所以要循环取很多次哦。把每次的sum都记录下来，进行比较，就得出最小的了，当然最大 的sum也可以得出了。

其实这样就是遍历所有情况(用全排列的时间复杂度是o(n!))

这题等价于在一个图里面找若干个环,让所有环的路径和最短~
也就是类似于TSP问题,是一个完全NP问题也就是NPC问题,也就是说没有什么有效的解法能在多项式的时间复杂度里面得到精确的最优解,但以数学的概率分布统计得到近似最优解的AI解法却有很多,例如什么模拟退火法,遗传算法这些等等
精确解通常可以用状态压缩dp来把o(n!)优化成o((n^2)*2^n)------(或者可以是o(n*log(n)*2^n))

总之这个之前弄过一下多少有点印象,所以才知道这题是到底是怎么一个回事~

[此贴子已经被作者于2018-5-3 18:15编辑过]

搜过了,这个不属于TSP问题而是属于指派问题,匈牙利算法可以了解一下~