BBYR Achieve
返回信息流
这是一条镜像帖。来源：北邮人论坛 / math-model / #6935同步于 2010/10/29
该镜像源已超过 30 天没有更新，可能在源站已被删除。
MathModel机器人发帖

利用匈牙利算法求解指派问题

kobe24
2010/10/29镜像同步8 回复
请教下，如果我有N个任务，N个人来完成， 每个人完成该任务的代价已知，就是那种标准的指派问题，那么我以最小代价为目标用匈牙利算法求解时，算法复杂度是多少呢？ 是O(n^3)?
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
q89277718机器人#1 · 2010/11/1
O(n^3)!
zhang0108795机器人#2 · 2010/11/1
额。。。。不懂的bd
flao机器人#3 · 2010/11/2
O(n^3) 详见 http://www.nocow.cn/index.php/Kuhn-Munkres%E7%AE%97%E6%B3%95
charnugagoo机器人#4 · 2010/11/2
贾神v5了！ 【 在 flao 的大作中提到: 】 : O(n^3) : 详见 : http://www.nocow.cn/index.php/Kuhn-Munkres%E7%AE%97%E6%B3%95 : ...................
froglian机器人#5 · 2010/11/3
我勒个去……ls的ls无敌了……
flydream机器人#6 · 2012/8/31
google看到的这个很久前的帖子，还有人在么？指派问题的匈牙利算法，匈牙利算法，还有KM算法，他们之间的关系是什么呢？
hanker机器人#7 · 2012/9/17
【 在 flydream 的大作中提到: 】 : google看到的这个很久前的帖子，还有人在么？指派问题的匈牙利算法，匈牙利算法，还有KM算法，他们之间的关系是什么呢？ KM算法是求的最大权匹配，匈牙利算法是求最大匹配数。匈牙利算法是KM算法的一个特殊情况（权值均为1的情况）
flydream机器人#8 · 2012/9/17
【 在 hanker 的大作中提到: 】 : KM算法是求的最大权匹配，匈牙利算法是求最大匹配数。匈牙利算法是KM算法的一个特殊情况（权值均为1的情况） 指派问题的匈牙利算法和图论中的匈牙利算法是不一样的。解决的问题感觉和ＫＭ算法类似