匈牙利算法以及在分配问题中的使用

分手后的思念是犯贱 2022-05-23 03:24 96阅读 0赞

前部分算法解释引自[https://blog.csdn.net/dark\_scope/article/details/8880547][https_blog.csdn.net_dark_scope_article_details_8880547]感谢大神的讲解

【书本上的算法往往讲得非常复杂，我和我的朋友计划用一些简单通俗的例子来描述算法的流程】

匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

\-------等等，看得头大？那么请看下面的版本：

通过数代人的努力，你终于赶上了剩男剩女的大潮，假设你是一位光荣的新世纪媒人，在你的手上有N个剩男，M个剩女，每个人都可能对多名异性有好感（![惊讶][ohmy.gif]\-\_-||暂时不考虑特殊的性取向），如果一对男女互有好感，那么你就可以把这一对撮合在一起，现在让我们无视掉所有的单相思（好忧伤的感觉![快哭了][fastcry.gif]），你拥有的大概就是下面这样一张关系图，每一条连线都表示互有好感。

![20130503155150538][]

本着救人一命，胜造七级浮屠的原则，你想要尽可能地撮合更多的情侣，匈牙利算法的工作模式会教你这样做：

===============================================================================

**一：** 先试着给1号男生找妹子，发现第一个和他相连的1号女生还名花无主，got it，连上一条蓝线

![20130503155256629][]

===============================================================================

**二**：接着给2号男生找妹子，发现第一个和他相连的2号女生名花无主，got it

![20130503155344972][]

===============================================================================

**三**：接下来是3号男生，很遗憾1号女生已经有主了，怎么办呢？

我们试着给之前1号女生匹配的男生（也就是1号男生）另外分配一个妹子。

(黄色表示这条边被临时拆掉)

![20130503155428908][]

与1号男生相连的第二个女生是2号女生，但是2号女生也有主了，怎么办呢？我们再试着给2号女生的原配(![发火][angry.gif]![发火][angry.gif])重新找个妹子(注意这个步骤和上面是一样的，这是一个递归的过程)

![20130503155441032][]

此时发现2号男生还能找到3号女生，那么之前的问题迎刃而解了，回溯回去

2号男生可以找3号妹子~~~                  1号男生可以找2号妹子了~~~                3号男生可以找1号妹子

![20130503155453501][]![20130503155626560][]![20130503162147840][]

所以第三步最后的结果就是：

![20130503160156253][]

===============================================================================

**四**： 接下来是4号男生，很遗憾，按照第三步的节奏我们没法给4号男生腾出来一个妹子，我们实在是无能为力了……香吉士同学走好。

===============================================================================

这就是匈牙利算法的流程，其中找妹子是个递归的过程，最最关键的字就是“腾”字

其原则大概是：有机会上，没机会创造机会也要上

【code】

\[cpp\] [view plain][] [copy][view plain]

1. **bool** find(**int** x)\{  
2.     **int** i,j;  
3.     **for** (j=1;j<=m;j++)\{    //扫描每个妹子  
4.         **if** (line\[x\]\[j\]==**true** && used\[j\]==**false**)        
5.         //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了）  
6.         \{  
7.             used\[j\]=1;  
8.             **if** (girl\[j\]==0 || find(girl\[j\])) \{   
9.                 //名花无主或者能腾出个位置来，这里使用递归  
10.                 girl\[j\]=x;  
11.                 **return** **true**;  
12.             \}  
13.         \}  
14.     \}  
15.     **return** **false**;  
16. \}

在主程序我们这样做：每一步相当于我们上面描述的一二三四中的一步

\[cpp\] [view plain][] [copy][view plain]

1. **for** (i=1;i<=n;i++)  
2. \{  
3.     memset(used,0,**sizeof**(used));    //这个在每一步中清空  
4.     **if** find(i) all+=1;  
5. \}  
6.

接下来让我们来看看在考试分配问题中的运用

某校经预赛选出A、B、C、D四名学生，将派他们去参加该地区各学校之间的竞赛。此次竞赛的四门功课考试在同一时间进行，因而每人只能参加一门，比赛结果将以团体总分计名次（不计个人名次）。设下表是四名学生选拔时的成绩，问应如何组队较好？。

第一步：每一行减去每一行的最小值，每一列减去每一列最小值

第1行减去-95，第2行减去-89，第3行减去-93，第4行减去-87。

第1列减去0，第2列减去0，第3列减去3，第4列减去0

第二步：利用最少的水平线或垂直线覆盖所有的0

第三步：由于水平线和垂直线的总数是3，少于阶数4，进入第四步。

第四步.没有被覆盖的最小值是2，没有被覆盖的每行减去最小值2，被覆盖的每列加上最小值2，然后跳转到第二步。

第五步：当覆盖的线覆盖所有的0时，线总数为4时，算法结束，可得矩阵

0 1 0 0

1 0 0 0

0 0 1 0

0 0 0 1

即A参加物理、B参加数学、C参加化学、D参加英语。总分为355分

java代码实现

package qty; 
 public class ayu{ 
 public static void appoint(double[][] m){ 
 int N = m.length; 
 //行规约 
 for(int i = 0;i < N;i ++){ 
 double min = Double.MAX_VALUE; 
 for(int j = 0;j < N;j ++){ 
 if(m[i][j] < min) 
 min = m[i][j]; 
 } 
 for(int j = 0;j < N;j ++) 
 m[i][j] -= min; 
 } 
 //列规约 
 for(int j = 0;j < N;j ++){ 
 double min = Double.MAX_VALUE; 
 for(int i = 0;i < N;i ++){ 
 if(m[i][j] < min) 
 min = m[i][j]; 
 } 
 if(min == 0) 
 continue; 
 for(int i = 0;i < N;i ++) 
 m[i][j] -=min; 
 } 
 
 printM(m); 
 
 //进行试分配 
 while(true){ 
 boolean zeroExist = true; 
 while(zeroExist){ 
 zeroExist = false; 
 if(rowAppoint(m)) 
 zeroExist = true; 
 if(colAppoint(m)) 
 zeroExist = true; 
 printM(m); 
 } 
 //判断是否达到最优分配 
 if(isOptimal(m)) 
 break; 
 
 //变换矩阵 
 updataM(m); 
 
 //将0元素恢复 
 for(int i = 0;i < N;i ++){ 
 for(int j = 0;j < N;j ++) 
 if(m[i][j]<0) 
 m[i][j] = 0; 
 } 
 
 printM(m); 
 } 
 } 
 
 public static void updataM(double[][] m){ 
 int N = m.length; 
 //记录行、列是否打钩 
 boolean[] rowIsChecked = new boolean[N]; 
 boolean[] colIsChecked = new boolean[N]; 
 //给没有被圈的行打钩 
 for(int i = 0;i < N;i ++){ 
 for(int j = 0;j < N;j ++){ 
 if(m[i][j] == -1){ 
 rowIsChecked[i] = false; 
 break; 
 }else{ 
 rowIsChecked[i] = true; 
 } 
 } 
 } 
 
 boolean isChecked = true; 
 
 while(isChecked){ 
 isChecked = false; 
 
 //对所有打钩行的0元素所在列打钩 
 for(int i = 0;i < N;i ++){ 
 if(rowIsChecked[i]){ 
 for(int j = 0;j < N;j ++){ 
 if(m[i][j]==-2 && !colIsChecked[j]){ 
 colIsChecked[j] = true; 
 isChecked = true; 
 } 
 } 
 } 
 } 
 //对打钩列上的独立零元素行打钩 
 for(int j = 0;j < N;j ++){ 
 if(colIsChecked[j]){ 
 for(int i = 0;i < N;i ++){ 
 if(m[i][j] == -1 && !rowIsChecked[i]){ 
 rowIsChecked[i] = true; 
 isChecked = true; 
 } 
 } 
 } 
 } 
 } 
 
 //寻找盖零线以外最小的数 
 double min = Double.MAX_VALUE; 
 for(int i = 0;i < N;i ++){ 
 if(rowIsChecked[i]){ 
 for(int j = 0;j < N;j ++){ 
 if(!colIsChecked[j]){ 
 if(m[i][j] < min) 
 min = m[i][j]; 
 } 
 } 
 } 
 } 
 
 //打钩各行减去min 
 for(int i=0;i < N;i ++){ 
 if(rowIsChecked[i]){ 
 for(int j = 0;j < N;j ++){ 
 if(m[i][j] > 0) 
 m[i][j] -= min; 
 } 
 } 
 } 
 
 //打钩各列加上min 
 for(int j=0;j < N;j ++){ 
 if(colIsChecked[j]){ 
 for(int i = 0;i < N;i ++){ 
 if(m[i][j] > 0) 
 m[i][j] += min; 
 } 
 } 
 } 
 
 } 
 
 //统计被圈起来的0数量,判断是否找到最优解 
 public static boolean isOptimal(double[][] m){ 
 int count = 0; 
 for(int i = 0;i < m.length;i ++){ 
 for(int j = 0;j < m.length;j ++) 
 if(m[i][j] == -1) 
 count ++; 
 } 
 return count==m.length; 
 } 
 
 //寻找只有一个0元素的行，将其标记为独立0元素（-1），对其所在列的0元素画叉（-2） 
 //若存在独立0元素返回true 
 public static boolean rowAppoint(double[][] m){ 
 boolean zeroExist = false; 
 int N = m.length; 
 //寻找只有一个0元素的行（列） 
 for(int i = 0;i < N;i ++){ 
 int zeroCount = 0; 
 int colIndex = -1; 
 for(int j = 0;j < N;j ++){ 
 if(m[i][j]==0){ 
 zeroCount ++; 
 colIndex = j; 
 zeroExist = true; 
 } 
 } 
 //将独立0元素标记为-1(被圈起来)，对应的列上的零标记为-2(被划去) 
 if(zeroCount == 1){ 
 m[i][colIndex] = -1; 
 for(int k = 0;k < N;k ++){ 
 if(k == i) 
 continue; 
 else if(m[k][colIndex] == 0) 
 m[k][colIndex] = -2; 
 } 
 }else if(zeroCount == 2){//如果存在2组解，随机选择其一标记，解决多解问题 
 if(Math.random()>0.95){ 
 m[i][colIndex] = -1; 
 for(int k = 0;k < N;k ++){ 
 if(k == i) 
 continue; 
 else if(m[k][colIndex] == 0) 
 m[k][colIndex] = -2; 
 } 
 for(int j = 0;j < N;j ++){ 
 if(j == colIndex) 
 continue; 
 else if(m[i][j] == 0) 
 m[i][j] = -2; 
 } 
 } 
 } 
 } 
 return zeroExist; 
 } 
 //寻找只有一个0元素的列，将其标记为独立0元素（-1），对其所在行的0元素画叉（-2） 
 //若存在独立0元素返回true 
 public static boolean colAppoint(double[][] m){ 
 boolean zeroExist = false; 
 int N = m.length; 
 for(int j = 0;j < N;j ++){ 
 int zeroCount = 0; 
 int rowIndex = -1; 
 for(int i = 0;i < N;i ++){ 
 if(m[i][j]==0){ 
 zeroCount ++; 
 rowIndex = i; 
 zeroExist = true; 
 } 
 } 
 if(zeroCount == 1){ 
 m[rowIndex][j] = -1; 
 for(int k = 0;k < N;k ++){ 
 if(k == j) 
 continue; 
 else if(m[rowIndex][k] == 0) 
 m[rowIndex][k] = -2; 
 } 
 } 
 } 
 return zeroExist; 
 } 
 
 public static void main(String[] args) { 
 
 double[][] m = new double[][]{
 {-90,-95,-78,-83}, 
 {-85,-89,-73,-80}, 
 {-93,-91,-88,-79}, 
 {-79,-85,-84,-87}, }; 
 appoint(m); 
 
 printResult(m); 
 } 
 
 public static void printM(double[][] m){ 
 System.out.println("---------------"); 
 for(int i = 0;i < m.length;i ++){ 
 for(int j = 0;j < m.length;j ++) 
 System.out.print(m[i][j] + " "); 
 System.out.println(); 
 } 
 } 
 
 public static void printResult(double[][] m){ 
 System.out.println("-----Result------"); 
 for(int i = 0;i < m.length;i ++){ 
 for(int j = 0;j < m.length;j ++) 
 if(m[i][j] == -1) 
 System.out.print(i+"--"+j+", "); 
 } 
 } 
 }

![70][]

[https_blog.csdn.net_dark_scope_article_details_8880547]: http://https//blog.csdn.net/dark_scope/article/details/8880547
[ohmy.gif]: http://static.blog.csdn.net/xheditor/xheditor_emot/default/ohmy.gif
[fastcry.gif]: /images/20220523/7720a12dc0314846ae5777e8386760f9.png
[20130503155150538]: /images/20220523/1bf20e4e69874fd3806367637c4fbf9c.png
[20130503155256629]: /images/20220523/dd9958d113894412ac11ec1cbdae38c5.png
[20130503155344972]: /images/20220523/4da21856f7e0406580bb4a96130aae22.png
[20130503155428908]: /images/20220523/a9f07fdeb3734413afbb060198adc1e4.png
[angry.gif]: /images/20220523/2f7c2e7015df48049ef86773a0031863.png
[20130503155441032]: /images/20220523/8060ffe6c45243b2b8f53aec014f8991.png
[20130503155453501]: https://img-blog.csdn.net/20130503155453501
[20130503155626560]: https://img-blog.csdn.net/20130503155626560
[20130503162147840]: /images/20220523/9aeeb8e3954f492e87a068fcd278518b.png
[20130503160156253]: /images/20220523/20650e2cb8214903920d52f10661166f.png
[view plain]: https://blog.csdn.net/dark_scope/article/details/8880547#
[70]: /images/20220523/d52aae6192634e58a454647ca055fba2.png