主题：[讨论]求算法思想！！！
joulejcc
[专家分：310] 发布于 2007-09-08 21:08:00
0 786 650 0 321
689 900 0 0 0
0 0 476 378 0
0 178 0 802 0
0 0 0 0 0
现有一个5x5的方阵(为了简化问题，用5x5的方阵代替)，从第一行选出一个数d1(后面选数时不能选d1所在列的数字，比如第一行选786，则第二行不能选900，第四行不能选178，后同),从第二行选出一个数d2......依此类推，最后使得d1 + d2 + ... + d5的值最大。麻烦大家看一下，这个算法该怎么写。
最后更新于：2007-09-08 21:09:00
回复列表 （共12个回复）
沙发
FancyMouse [专家分：13680] 发布于 2007-09-08 22:25:00
只想到硬搜，加的剪枝也需要2^n的空间
数据范围多少？
板凳
joulejcc [专家分：310] 发布于 2007-09-08 22:43:00
20x20的方阵，麻烦你说具体一点，谢谢！
3 楼
joulejcc [专家分：310] 发布于 2007-09-09 23:41:00
用回溯法可以解决问题，但是运行的时间太长了，13*13的矩阵就要9分多钟。
别人说可以用匈牙利算法解，但是我对这个算法一点都不懂，麻烦高手站出来指点一下撒。我的QQ：115108703
4 楼
lucifel [专家分：60] 发布于 2007-09-12 12:06:00
昏，直接取每列最大的数不就结了
5 楼
lucifel [专家分：60] 发布于 2007-09-12 12:07:00
当然，要先判断下该行有没被取过值
6 楼
joulejcc [专家分：310] 发布于 2007-09-12 16:02:00
[quote]昏，直接取每列最大的数不就结了[/quote]
晕，要是是这样我就不会提这个问题了，局部最优不代表整体最优。举个例子给你看看，
1 3 0
2 8 0
0 0 4
照你这么说，应该是第一行选3，第二行选2，第三行选4，就是3 + 2 + 4 = 9
但是最优解应该是 1 + 8 + 4 = 13，所以局部最优不代表整体也是最优的。
7 楼
ailyanlu [专家分：0] 发布于 2007-09-19 09:27:00
这个不是最大权匹配么？
8 楼
ailyanlu [专家分：0] 发布于 2007-09-19 09:29:00
准确来说，这个不是叫匈牙利算法，这个是Kuhn和Munkras提出的KM算法
9 楼
joulejcc [专家分：310] 发布于 2007-09-19 23:34:00
就是这个,你能不能说一下具体怎么做,谢谢!
10 楼
FancyMouse [专家分：13680] 发布于 2007-09-20 22:42:00
[quote]这个不是最大权匹配么？[/quote]
我呆了……最近对二分图网络流这类东西超没感觉的。。。
我来回复
您所在位置：