做多目標跟蹤的時候會碰到這個算法筐钟，每個人都有自己的說法講清楚這個算法是干什么的？我的老師就跟我說過是什么給工人分配活干（即理解為指派問題）疹鳄，網(wǎng)上還看到有說紅娘盡可能匹配多的情侶等拧略，透過這些感性理解，基本上就能理解大概是最大匹配的問題了瘪弓。
然后加了限制：后來者優(yōu)先垫蛆。即后匹配的能搶掉前人已匹配的對象，這個是有數(shù)學依據(jù)還是只是一種實現(xiàn)思路我就沒深究了腺怯。
我的理解不會比別人更高級袱饭，之所以能用一張圖說清楚，只不過是我作圖的時候發(fā)現(xiàn)可以把過程畫在一張圖里呛占，只需要把圖示標清楚就好了虑乖，這樣就不需要每一步畫一張圖了，一旦理解了晾虑，哪怕忘了疹味，一瞅這張圖也能立刻回憶起來仅叫。
先上數(shù)據(jù)：
import numpy as np
relationship_matrix = np.array([
[1,1,0,1,0,0,0],
[0,1,0,0,1,0,0],
[1,0,0,1,0,0,1],
[0,0,1,0,0,1,0],
[0,0,0,1,0,0,0],
[0,0,0,1,0,0,0]
], dtype=bool)
你可以理解為6個工人，7個工作糙捺，6個男孩诫咱，7個女孩等，當然洪灯，6行7列坎缭，這么直觀理解也是一點問題都沒有的。
算法匹配過程如下：
hungarian_algorithm.png
- 灰藍線就是被搶掉的
- 綠線就是搶奪失敗的
-
紫線是被搶了后找候選成功的 -
紅線是一次性成功的
其中被搶的和搶奪失敗的還加了刪除線婴渡，這是為了強調(diào)幻锁。匹配成功的就是紅線和紫線，也就是說边臼，我們匹配出來的是：
[0,1], [1,4], [2,0], [3,2], [4,3]
甚至可以這么表示這個過程：
x0,y0
x1,y1
x2,y0 -> x0,y1 -> x1->y4 (x2搶x0的,x0搶x1的)
x3,y2
x4,y3
x5,y3 -> x4匹配不到新的哄尔，搶奪失敗，-> x5,null
有沒有說清楚柠并？就兩步：
- 根據(jù)關聯(lián)表直接建立關系
- 如果當前
C匹配的對象已經(jīng)被B匹配過了岭接，那么嘗試把它搶過來：
-
B去找別的匹配- 找到了(
A)就建立新的匹配- 如果新的匹配(
A)也已經(jīng)被別人(D)匹配了，那么那個“別人(D)”也放棄當前匹配去找別的（遞歸警告）
- 如果新的匹配(
- 如果找不到新的匹配臼予，那么
C搶奪失敗鸣戴，遞歸中的D也同理，失敗向上冒泡
- 找到了(
注意遞歸怎么寫代碼就能寫出來了：
nx, ny = relationship_matrix.shape # 6個x粘拾，7個y
# 如果x0與y0關聯(lián)窄锅，x3也與y0關聯(lián)，那么x0去找新的匹配時缰雇，需要把y0過濾掉
# 同理x0如果找到下一個y2入偷，y2已被x2關聯(lián)，那么x2找新的匹配時[y0, y2]都需要過濾掉
# 我們把這個數(shù)組存為y_used
y_used = np.zeros((ny,), dtype=bool) # 存y是否連接上
path = np.full((ny,), -1, dtype=int) # 存x連接的對象械哟，沒有為-1
def find_other_path_and_used(x):
for y in range(ny):
if relationship_matrix[x, y] and not y_used[y]:
y_used[y] = True # 處于爭奪中的y疏之，需要打標，在后續(xù)的遞歸時要過濾掉
if path[y] == -1 or find_other_path_and_used(path[y]):
path[y] = x # 直接連接 和 搶奪成功
return True
return False # 搶奪失敗 和 默認失敗
for x in range(nx):
y_used[:] = False # empty
find_other_path_and_used(x)
for y, x in enumerate(path):
if x != -1:
print(x, y)
真的寫代碼實現(xiàn)的時候暇咆，難點反而是y_used這個锋爪，第一遍代碼沒考慮這一點，導致遞歸的時候每次都從開始而出現(xiàn)死循環(huán)爸业，意識到后把處于爭搶狀態(tài)中的
y打個標就好了其骄。
scipy中有一個算法實現(xiàn)了Hungarian algorithm：
from scipy.optimize import linear_sum_assignment
# relationship_matrix是代價矩陣
# 所以我們要代價越小越好，就用1來減
rows, cols = linear_sum_assignment(1-relationship_matrix)
list(zip(rows, cols))
[(0, 0), (1, 1), (2, 6), (3, 2), (4, 3), (5, 4)]
為什么與上面不一樣呢扯旷？
- （0年栓，0），（1薄霜，1）的匹配顯然不是我們實現(xiàn)的后來者優(yōu)先
- 他把行看成是工人某抓，列看成是任務纸兔，每個工人總要分配個任務，所以(5,4)這種代價矩陣里沒有的關聯(lián)它也做出來了否副，目的只是讓“總代價”最小
(1-relationship_matrix)[rows, cols] # 總代價為1
array([0, 0, 0, 0, 0, 1])
從它的名字也能看出來汉矿，它是理解為指派問題的(assignment)
