腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >匈牙利算法选择0

问匈牙利算法选择0
EN

Stack Overflow用户

提问于 2013-03-01 07:11:55

回答 1查看 328关注 0票数 4

我有一个与这里非常相似的问题：

Hungarian algorithm - assign systematically

他提出了一个可能或不可行的解决方案。但从逻辑上讲，这似乎并不完全合理。

有没有一种可靠的动态算法来确定哪组0将是可行的解决方案？(表示每行和每列只有一个0)

请参阅上的步骤9：http://www.wikihow.com/Use-the-Hungarian-Algorithm

如何实现算法来执行该任务？

谢谢!

algorithm

graph-algorithm

回答 1

Stack Overflow用户

发布于 2013-03-01 08:09:19

从本质上讲，您可以将n*n矩阵视为表示二部图。行表示图左侧的顶点，列表示右侧的顶点。行i，列j中的零表示在左侧的顶点i和右侧的vetex j之间有一条边。

您希望找到一个完全的二部匹配，即没有公共顶点的n条边的集合。为此，您可以使用您喜欢的匹配算法，例如Hopcroft-Karp。

找到匹配后，选择与匹配中的边相对应的零。matching属性保证每行/每列中不超过一个选定的零。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15152476

复制

匈牙利算法

编程算法

二分图：又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B)，则称图G为一个二分图。

五分钟学算法

2019/06/03

1.3K0

匈牙利算法详解_匈牙利算法加上最大值

编程算法

如图所示，其中的三条边即该图的一个匹配。所以，匹配的两个重点：1. 匹配是边的集合；2. 在该集合中，任意两条边不能有共同的顶点。那么，我们自然而然就会有一个想法，一个图会有多少匹配？有没有最大的匹配（即边最多的匹配呢）？

全栈程序员站长

2022/11/09

1.3K0

匈牙利算法

编程算法

今天学习了下匈牙利算法，发现这个早在几个月前学过的知识已经忘记的一干二净了，记得当初学习的时候只是看书，看论文，现在要好好的总结下，防止以后再次忘记。此次总结依据实例进行，hdu2063 不同的女生喜欢的男生不一样，有可能喜欢的是同一个人，也有可能喜欢多个，至于谁和谁在一起男的说了没用，现在要求的是，如何搭配使数目达到最大为了解决这个问题，我们先理解基本的两个概念交替路径（Alternating Path）是指这样一条路径，其中的每一条边交替地属于或不属于匹配 M。比如说，第一、三、五条边属于 M，而

用户1624346

2018/04/17

1.2K0

指派问题匈牙利算法例题_匈牙利算法matlab代码

https java 网络安全对象存储

在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题。

全栈程序员站长

2022/09/20

6280

Plug It In!（匈牙利算法）

dfs

有m个插头，n个电器，每个插座上只能插选定的几个设备，且一次只能插一个设备，你有一个接口转换器，可以使得其中一个插座一次可以插3个设备，问你同一时间最多有多少设备可以供电。

Here_SDUT

2022/08/11

1950

指派问题 —— 匈牙利算法

编程算法 https 网络安全

有A、B、C、D、 E五项任务，需要分配给甲、乙、丙、丁、戊五个人来完成。他们完成任务所需要支付的酬劳如下表所示，问，如何分配任务，可使总费用最少？

为为为什么

2022/08/09

6.4K0

ACM算法竞赛——匈牙利算法（模板）

腾讯微信算法大赛

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。1955年，库恩(W.W.Kuhn)利用匈牙利数学家康尼格(D.Kőnig)的一个定理构造了这个解法，故称为匈牙利法。（百度百科）匈牙利算法用于求二分图的最大匹配问题时间复杂度：O(mn),实际运行时间一般小于O(mn) int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只

战士小小白

2022/05/18

3600

匈牙利算法(Kuhn-Munkres)算法[通俗易懂]

编程算法 https 网络安全

这个算法有点难度，一般比较标准的描述网页上也有相关的描述，我在这里就简单的用十分通俗的语言给大家入个门

全栈程序员站长

2022/09/06

5.9K0

POJ 3041 Asteroids(匈牙利算法)

地图算法

题意就是有一个地图，然后给你几个点的坐标标记为'x'，然后你有一个武器，每次可以消灭一行或一列的'x'，问最少需要几次能把所有的'x'消灭完。然后我们可以构建一个二分图，然后这就是一个最小覆盖集问题，最小覆盖数 = 最大匹配数，根据匈牙利算法就能求了。先上代码，以后再补详细的解释。

Ch_Zaqdt

2019/01/08

5930

分配问题与匈牙利算法

matrix

假如你是个玩具工厂的销售经理，你现在有三个销售人员要去不同城市见买家。你的销售人员分别在在奥斯丁，得克萨斯州；波士顿、马里兰州；和芝加哥，伊利诺伊州。你想让他们飞往其他三个城市：丹佛，埃德蒙顿，法戈。下面的表格显示了这些城市之间飞机票的费用.。

用户1665735

2019/05/26

2.5K1

HDOJ2063过山车匈牙利算法

input output sample

Problem Description RPG girls今天和大家一起去游乐场玩，终于可以坐上梦寐以求的过山车了。可是，过山车的每一排只有两个座位，而且还有条不成文的规矩，就是每个女生必须找个个男生做partner和她同坐。但是，每个女孩都有各自的想法，举个例子把，Rabbit只愿意和XHD或PQK做partner，Grass只愿意和linle或LL做partner，PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题，boss刘决定只让找到partner的人去坐过山车，其他的人，嘿嘿，就站在下面看着吧。聪明的Acmer，你可以帮忙算算最多有多少对组合可以坐上过山车吗？

谙忆

2021/01/19

2990

过山车（匈牙利算法）- HDU 2063

编程算法 ios

输入数据的第一行是三个整数K , M , N，分别表示可能的组合数目，女生的人数，男生的人数。0<K<=1000 1<=N 和M<=500.接下来的K行，每行有两个数，分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

ACM算法日常

2018/09/21

9080

【从0到1学算法】选择排序

编程算法

有一种方法是这样子的，遍历列表，找出播放次数最多的乐队，将这个乐队添加到一个新的列表中。

KEN DO EVERTHING

2020/07/24

3580

【I'm Telling the Truth】【HDU - 3729】【匈牙利算法，DFS】

编程算法

题意：该题主要说几个同学分别说出自己的名次所处区间，最后输出可能存在的未说谎的人数及对应的学生编号，而且要求字典序最大。思路：刚刚接触匈牙利算法，了解的还不太清楚，附一个专门讲解匈牙利算法的博文，个人认为讲的比较清晰。

_DIY

2019/08/23

3170

【运筹学】匈牙利法 ( 匈牙利法步骤 | 第一步 : 使行列出现 0 元素示例 )

博客基础

注意必须先变行 , 然后再变列 , 行列不能同时进行改变 ; 否则矩阵中会出现负数 , 该矩阵中不能出现负数 ;

韩曙亮

2023/03/28

7840

二分图最大匹配 —— 匈牙利算法

编程算法 https 网络安全

在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。

为为为什么

2022/08/09

2.5K0

二分图最大匹配问题（匈牙利算法）

https 网络安全编程算法

如果一个无向图的的顶点可以分为两个互不相交的子集A和B，那么它就是二分图。也就是说，A、B内部不存在连边，所有连边都一头连着A中的顶点，另一头连着B中的顶点。

灯珑LoGin

2022/10/31

9570

详解匈牙利算法与二分图匹配

编程算法

在上一篇文章当中我们介绍了一个有趣的稳定婚姻问题，模拟了男男女女配对的婚恋场景，并且研究了一下让匹配更加稳定的Gale-Shapley算法。如果错过了这篇文章的同学可以从下方的传送门回顾一下婚姻稳定问题的具体内容。

TechFlow-承志

2020/07/30

1.4K0

匈牙利算法（二分图最大匹配问题）

编程算法

匈牙利算法用于求解无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）问题

mathor

2019/12/30

1.4K0

匈牙利命名法[通俗易懂]

https java windows 编程算法网络安全

Windows 编程中用到的变量（还包括宏）的命名规则匈牙利命名法，这种命名技术是由一位能干的 Microsoft 程序员查尔斯·西蒙尼(Charles Simonyi) 提出的。

全栈程序员站长

2022/09/07

9470

相似问题

匈牙利算法-任意选择

匈牙利算法

匈牙利算法- PHP版本

解不出匈牙利算法

匈牙利算法死胡同

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问匈牙利算法选择0
EN