匈牙利演算法是一種在多項式時間內求解任務分配問題的組合優化演算法，換句話說就是，在可以接受的時間內去做匹配，
1. 描述問題
給定2個集合A和B，然后將AB中的元素完成一個連線，（這不就是小時候的連線題么-_-）
匈牙利演算法就是要找到兩個集合促成最多的匹配對！最佳媒婆，這里最適合舉的例子就是相親會，集合A代表所有男嘉賓，集合B代表所有女嘉賓，每個男女嘉賓都有自己的心動嘉賓，此為重要前提，通過一個演算法，完成最多的牽線，
借用https://blog.csdn.net/dark_scope/article/details/8880547的圖：
互相有紅線的代表互相心動，但不代表最終連線，這里的前提是，Hungarian演算法只會匹配互相心動的物件，
最侄訓得的匹配是：
具體步驟可以看https://blog.csdn.net/dark_scope/article/details/8880547
上面這篇博客完美解釋的Hungarian演算法的操作步驟：用遞回回溯的方式更改匹配，但沒從數學原理上解釋，
這里完成最大匹配的邏輯是，先找一個小匹配（至少完成2對牽手的，并且有兩對一的關系存在），然后通過M型交錯路徑的方法擴大匹配，
什么是M型交錯路徑？
如上圖，紅色粗線部分為小匹配，構成了一個M型的基本樣子，通過M形狀延申就可以獲得更大的匹配，更新如下，粗線為更新后的匹配：
與上一步完全不一樣，那么這么更新的邏輯是什么呢？答：M型
咱們展開來看，把右下角的點移動到左下角，就可以看得更清楚了：
匹配一直更新的邏輯是：M字母的陰面和陽面的交替！就是這樣，粗線代表連接，細線代表
上面這個就是Hungarian演算法的精髓了，這個步驟有個專業的名詞：M交錯路徑的增廣，
以上，
參考：https://blog.csdn.net/u013384984/article/details/90718287
https://blog.csdn.net/dark_scope/article/details/8880547
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/196276.html
標籤：其他
上一篇：求其上者得其中 雙非碩士學編程