匈牙利算法寻找最大匹配

他独居我心

成绩布景

给定一个x取y对应的毗连图，请求每一个xi取yi最多只能婚配一次，供最年夜的婚配次数

供解思路

 （1）将x取y的毗连转换成矩阵，可互相毗连标识表记标帜为1，此外为0

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1
x4	0	0	1	1	0	1	0
x5	0	0	0	1	0	0	0
x6	0	0	0	1	0	0	0

（2）最中层轮回x1到x6，即第一止到第六止，每止别离从y1到y7遍历
（3）此中used_b = [0, 0, 0, 0, 0, 0, 0]为某一止中被利用的y1
（4）conection_b = [-1,-1,-1,-1,-1,-1,-1]此中每一个元素的与值范畴为0-5，代表了y对应的第几止x
（5）从第一止开端，选中了y1，conection_b发作变革[0, -1, -1, -1, -1, -1, -1]

1. i: 0
2. find: 0
3. _index: 0
4. _used_b: [1, 0, 0, 0, 0, 0, 0]
5. _conection_b: [-1, -1, -1, -1, -1, -1, -1]
6. index: 0
7. conection_b: [0, -1, -1, -1, -1, -1, -1]
8. count

复造代码

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0

（6）第两止，选中了y2，conection_b发作变革[0, 1, -1, -1, -1, -1, -1]

1. i: 1
2. find: 1
3. _index: 1
4. _used_b: [0, 1, 0, 0, 0, 0, 0]
5. _conection_b: [0, -1, -1, -1, -1, -1, -1]
6. index: 1
7. conection_b: [0, 1, -1, -1, -1, -1, -1]
8. count

复造代码

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0

（7）第三止，选中了y1，因为第一止也选中了y1，因而进进递回

1. i: 2
2. find: 2
3. _index: 0
4. _used_b: [1, 0, 0, 0, 0, 0, 0]
5. _conection_b: [0, 1, -1, -1, -1, -1, -1]
6. find: 0
7. _index: 1
8. _used_b: [1, 1, 0, 0, 0, 0, 0]
9. _conection_b: [0, 1, -1, -1, -1, -1, -1]
10. find: 1
11. _index: 4
12. _used_b: [1, 1, 0, 0, 1, 0, 0]
13. _conection_b: [0, 1, -1, -1, -1, -1, -1]
14. index: 4
15. conection_b: [0, 1, -1, -1, 1, -1, -1]
16. index: 1
17. conection_b: [0, 0, -1, -1, 1, -1, -1]
18. index: 0
19. conection_b: [2, 0, -1, -1, 1, -1, -1]
20. count

复造代码

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1

（8）获得抵触止的index为0，因而开端find(0)，发明y2也被利用，因而持续递回find(1)

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1

（9）最初x2找到了y5，因而递回完毕，conection_b: [2, 0, -1, -1, 1, -1, -1]

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1

（10）第四止，选中了y3，因为出有抵触，所以conection_b: [2, 0, 3, -1, 1, -1, -1]

1. i: 3
2. find: 3
3. _index: 2
4. _used_b: [0, 0, 1, 0, 0, 0, 0]
5. _conection_b: [2, 0, -1, -1, 1, -1, -1]
6. index: 2
7. conection_b: [2, 0, 3, -1, 1, -1, -1]
8. count

复造代码

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1
x4	0	0	1	1	0	1	0

（11）第五止，选中了y4，因为出有抵触，所以conection_b: [2, 0, 3, 4, 1, -1, -1]

1. i: 4
2. find: 4
3. _index: 3
4. _used_b: [0, 0, 0, 1, 0, 0, 0]
5. _conection_b: [2, 0, 3, -1, 1, -1, -1]
6. index: 3
7. conection_b: [2, 0, 3, 4, 1, -1, -1]
8. count

复造代码

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1
x4	0	0	1	1	0	1	0
x5	0	0	0	1	0	0	0

（12）第六止，选中了y4，因为取第五止发作了抵触，所以进进递回find(4)

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1
x4	0	0	1	1	0	1	0
x5	0	0	0	1	0	0	0
x6	0	0	0	1	0	0	0

1. i: 5
2. find: 5
3. _index: 3
4. _used_b: [0, 0, 0, 1, 0, 0, 0]
5. _conection_b: [2, 0, 3, 4, 1, -1, -1]
6. find: 4
7. used_b: [0, 0, 0, 1, 0, 0, 0]
8. conection_b: [2, 0, 3, 4, 1, -1, -1]
9. 5

复造代码

（13）因为第五止中除y4，出有其他可选线项，因而 find(4) = 0，conection_b出有被改动，因而：conection_b: [2, 0, 3, 4, 1, -1, -1]

	y1	y2	y3	y4	y5	y6	y7
x1	1	1	0	1	0	0	0
x2	0	1	0	0	1	0	0
x3	1	0	0	1	0	0	1
x4	0	0	1	1	0	1	0
x5	0	0	0	1	0	0	0
x6	0	0	0	1	0	0	0

代码

1. >>>def find(x):...    print("find:", x)...    for index in range(7):...        if matrix[x][index] == 1 and used_b[index] == 0:...            used_b[index] = 1...            print("_index:", index)...            print("_used_b:", str(used_b))...            print("_conection_b:", str(conection_b))...            if conection_b[index] == -1 or find(conection_b[index]) != 0:...                print("index:", index)...                conection_b[index] = x...                print("conection_b:", str(conection_b))...                return 1...    return 0>>>matrix = [...    [1,1,0,1,0,0,0],...    [0,1,0,0,1,0,0],...    [1,0,0,1,0,0,1],...    [0,0,1,1,0,1,0],...    [0,0,0,1,0,0,0],...    [0,0,0,1,0,0,0]...    ]>>>conection_b = [-1 for _ in range(7)]>>>count = 0>>>for i in range(6):...    used_b = [0 for _ in range(7)]...    print("i:",i)...    if find(i):...        print("count")...        count += 1>>>print("used_b:", str(used_b))>>>print("conection_b:", str(conection_b))>>>print(count)i: 0
2. find: 0
3. _index: 0
4. _used_b: [1, 0, 0, 0, 0, 0, 0]
5. _conection_b: [-1, -1, -1, -1, -1, -1, -1]
6. index: 0
7. conection_b: [0, -1, -1, -1, -1, -1, -1]
8. counti: 1
9. find: 1
10. _index: 1
11. _used_b: [0, 1, 0, 0, 0, 0, 0]
12. _conection_b: [0, -1, -1, -1, -1, -1, -1]
13. index: 1
14. conection_b: [0, 1, -1, -1, -1, -1, -1]
15. counti: 2
16. find: 2
17. _index: 0
18. _used_b: [1, 0, 0, 0, 0, 0, 0]
19. _conection_b: [0, 1, -1, -1, -1, -1, -1]
20. find: 0
21. _index: 1
22. _used_b: [1, 1, 0, 0, 0, 0, 0]
23. _conection_b: [0, 1, -1, -1, -1, -1, -1]
24. find: 1
25. _index: 4
26. _used_b: [1, 1, 0, 0, 1, 0, 0]
27. _conection_b: [0, 1, -1, -1, -1, -1, -1]
28. index: 4
29. conection_b: [0, 1, -1, -1, 1, -1, -1]
30. index: 1
31. conection_b: [0, 0, -1, -1, 1, -1, -1]
32. index: 0
33. conection_b: [2, 0, -1, -1, 1, -1, -1]
34. counti: 3
35. find: 3
36. _index: 2
37. _used_b: [0, 0, 1, 0, 0, 0, 0]
38. _conection_b: [2, 0, -1, -1, 1, -1, -1]
39. index: 2
40. conection_b: [2, 0, 3, -1, 1, -1, -1]
41. counti: 4
42. find: 4
43. _index: 3
44. _used_b: [0, 0, 0, 1, 0, 0, 0]
45. _conection_b: [2, 0, 3, -1, 1, -1, -1]
46. index: 3
47. conection_b: [2, 0, 3, 4, 1, -1, -1]
48. counti: 5
49. find: 5
50. _index: 3
51. _used_b: [0, 0, 0, 1, 0, 0, 0]
52. _conection_b: [2, 0, 3, 4, 1, -1, -1]
53. find: 4
54. used_b: [0, 0, 0, 1, 0, 0, 0]
55. conection_b: [2, 0, 3, 4, 1, -1, -1]
56. 5

复造代码

 总结

匈牙利算法的中心思维为：劣先思索最初一止，假如发作抵触，则寻觅抵触止可替换项，假如出有可替换项，抛弃最初一止，假如有可替换项，则利用其替换，假如替换以后发作抵触则进进递回，发明抵触不成消除，则抛弃最初一止，抵触能够消除，则利用该计划。
find递回函数的意义正在于回溯上一阶段计划能否找到可替换项，使得全部婚配计划之间两两没有发作抵触。

免责声明：假如进犯了您的权益，请联络站少，我们会实时删除侵权内乱容，感谢协作！