匈牙利算法是一種在多項(xiàng)式時(shí)間內(nèi)求解任務(wù)分配問(wèn)題的組合優(yōu)化算法。換句話說(shuō)就是，在可以接受的時(shí)間內(nèi)去做匹配。

1. 描述問(wèn)題

給定2個(gè)集合A和B，然后將AB中的元素完成一個(gè)連線。(這不就是小時(shí)候的連線題么-_-)

匈牙利算法就是要找到兩個(gè)集合促成最多的匹配對(duì)！最佳媒婆。這里最適合舉的例子就是相親會(huì)。集合A代表所有男嘉賓，集合B代表所有女嘉賓。每個(gè)男女嘉賓都有自己的心動(dòng)嘉賓，此為重要前提。通過(guò)一個(gè)算法，完成最多的牽線。

互相有紅線的代表互相心動(dòng)，但不代表最終連線。這里的前提是，Hungarian算法只會(huì)匹配互相心動(dòng)的對(duì)象。

最終獲得的匹配是：

上面這篇博客完美解釋的Hungarian算法的操作步驟：用遞歸回溯的方式更改匹配。但沒(méi)從數(shù)學(xué)原理上解釋。

這里完成最大匹配的邏輯是，先找一個(gè)小匹配(至少完成2對(duì)牽手的，并且有兩對(duì)一的關(guān)系存在)，然后通過(guò)M型交錯(cuò)路徑的方法擴(kuò)大匹配。

什么是M型交錯(cuò)路徑？

如上圖，紅色粗線部分為小匹配，構(gòu)成了一個(gè)M型的基本樣子，通過(guò)M形狀延申就可以獲得更大的匹配。更新如下，粗線為更新后的匹配：

與上一步完全不一樣，那么這么更新的邏輯是什么呢？答：M型

咱們展開(kāi)來(lái)看，把右下角的點(diǎn)移動(dòng)到左下角，就可以看得更清楚了：

匹配一直更新的邏輯是：M字母的陰面和陽(yáng)面的交替！就是這樣，粗線代表連接，細(xì)線代表

上面這個(gè)就是Hungarian算法的精髓了，這個(gè)步驟有個(gè)專業(yè)的名詞：M交錯(cuò)路徑的增廣。

以上。

總結(jié)

以上是生活随笔為你收集整理的匈牙利算法java实现_匈牙利算法(Hungarian Algorithm)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。