問題來源:
我司對(duì)外推出的是一個(gè)社交產(chǎn)品，其中有一個(gè)模塊，是男女之間進(jìn)行匹配的港柜。假設(shè)一群男和一群女中螃诅，N對(duì)N產(chǎn)生好感，但是最終只能是1男配1女劫灶，如何尋找最大結(jié)果集？
問題描述:
該問題可以采用匈牙利算法, 該算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出，因而得名和泌。匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法祠肥，該算法的核心就是尋找增廣路徑武氓，它是一種用增廣路徑求二分圖最大匹配的算法。
解決方案:
關(guān)于匈牙利算法，網(wǎng)上有很多县恕，但是都是C++的东羹，少量用JAVA，但是經(jīng)過作者核實(shí)忠烛，網(wǎng)上的匈牙利JAVA算法都有誤属提。
下圖的匈牙利卡通解釋圖來自網(wǎng)絡(luò)，JAVA算法來自本文作者改造
算法流程 (該流程來自網(wǎng)絡(luò))
通過數(shù)代人的努力美尸，你終于趕上了剩男剩女的大潮冤议，假設(shè)你是一位光榮的新世紀(jì)媒人，在你的手上有N個(gè)剩男师坎，M個(gè)剩女恕酸，每個(gè)人都可能對(duì)多名異性有好感（驚訝-_-||暫時(shí)不考慮特殊的性取向），如果一對(duì)男女互有好感胯陋，那么你就可以把這一對(duì)撮合在一起蕊温，現(xiàn)在讓我們無視掉所有的單相思（好憂傷的感覺快哭了），你擁有的大概就是下面這樣一張關(guān)系圖遏乔，每一條連線都表示互有好感义矛。
本著救人一命，勝造七級(jí)浮屠的原則按灶，你想要盡可能地撮合更多的情侶症革，匈牙利算法的工作模式會(huì)教你這樣做：
一： 先試著給1號(hào)男生找妹子，發(fā)現(xiàn)第一個(gè)和他相連的1號(hào)女生還名花無主鸯旁，got it噪矛，連上一條藍(lán)線
二：接著給2號(hào)男生找妹子，發(fā)現(xiàn)第一個(gè)和他相連的2號(hào)女生名花無主铺罢，got it
三：接下來是3號(hào)男生艇挨，很遺憾1號(hào)女生已經(jīng)有主了，怎么辦呢韭赘？
我們?cè)囍o之前1號(hào)女生匹配的男生（也就是1號(hào)男生）另外分配一個(gè)妹子缩滨。
(黃色表示這條邊被臨時(shí)拆掉)
與1號(hào)男生相連的第二個(gè)女生是2號(hào)女生，但是2號(hào)女生也有主了泉瞻，怎么辦呢脉漏？我們?cè)僭囍o2號(hào)女生的原配(發(fā)火發(fā)火)重新找個(gè)妹子(注意這個(gè)步驟和上面是一樣的，這是一個(gè)遞歸的過程)
此時(shí)發(fā)現(xiàn)2號(hào)男生還能找到3號(hào)女生袖牙，那么之前的問題迎刃而解了侧巨，回溯回去
2號(hào)男生可以找3號(hào)妹子~~~ 1號(hào)男生可以找2號(hào)妹子了~~~ 3號(hào)男生可以找1號(hào)妹子
所以第三步最后的結(jié)果就是：
四： 接下來是4號(hào)男生，很遺憾鞭达，按照第三步的節(jié)奏我們沒法給4號(hào)男生騰出來一個(gè)妹子司忱，我們實(shí)在是無能為力了……香吉士同學(xué)走好皇忿。
算法
public class HungaryAlgorithm {
public static void main(String[] args) {
// boyNumber為男生數(shù)量
int boyNumber = 4;
//girlNumber為女生數(shù)量
int girlNumber = 4;
//男生和女生互相匹配的線路圖,true為互相匹配
boolean[][] boyMatchGirlLine = new boolean[boyNumber][girlNumber];
boyMatchGirlLine[0][0] = true;
boyMatchGirlLine[0][1] = true;
boyMatchGirlLine[1][1] = true;
boyMatchGirlLine[1][2] = true;
boyMatchGirlLine[2][0] = true;
boyMatchGirlLine[2][1] = true;
boyMatchGirlLine[3][2] = true;
int[] girlMatchBoy = new HungaryAlgorithm().begin(boyMatchGirlLine);
for (int m = 0;m < girlNumber; m++) {
System.out.println(m+"女生配對(duì)男生： "+girlMatchBoy[m] );
}
}
public int[] begin(boolean[][] boyMatchGirlLine) {
// 最大適配數(shù)
int sum = 0;
// boyNumber為男生數(shù)量
int boyNumber = boyMatchGirlLine.length;
//girlNumber為女生數(shù)量
int girlNumber = boyMatchGirlLine[0].length;
//最終女生匹配男生的結(jié)果,girl[boyNumber]中的值為女生當(dāng)前的對(duì)象索引 -1為無對(duì)象
int[] girlMatchBoy=new int[boyNumber];
Arrays.fill(girlMatchBoy, -1);
//代表臨時(shí)性的女生是否暫時(shí)有匹配男生
boolean[] used=new boolean[boyNumber];
//開始匹配
for (int boyIndex = 0; boyIndex < boyNumber; boyIndex++) {
Arrays.fill(used, false);
if(match(boyIndex,girlNumber,boyMatchGirlLine,used,girlMatchBoy)) {
sum += 1;
}
}
System.out.println("最大匹配數(shù)"+sum);
return girlMatchBoy;
}
//匹配
public boolean match(int boyIndex,int girlNumber,boolean[][] boyMatchGirlLine,boolean[] used,int[]girlMatchBoy) {
for(int girlIndex=0;girlIndex<girlNumber;girlIndex++)
{
if(boyMatchGirlLine[boyIndex][girlIndex]&&used[girlIndex]==false)
{
used[girlIndex]=true;
if(girlMatchBoy[girlIndex]==-1||match(girlMatchBoy[girlIndex],girlNumber,boyMatchGirlLine,used,girlMatchBoy))
{
girlMatchBoy[girlIndex]=boyIndex;
return true;
}
}
}
return false;
}
}
