匈牙利算法的MATLAB代码

程序文件 fenpei m function z ans fenpei marix 输入效率矩阵 marix 为方阵 若效率矩阵中有 M 则用一充分大的数代替 输出 z 为最优解 ans 为 最优分配矩阵 a marix b a 确定矩阵维数 s length a 确定矩阵行最小值 进行行减 ml min a for i 1 s a i a i ml i end 确定矩阵列最小值 进行列减 mr min a for j 1 s a j a j mr j end start working num 0 while num s 终止条件是 0 的个数与矩阵的维数相同 index 用以标记矩阵中的零元素 若 a i j 0 则 index i j 1 否则 index i j 0 index ones s index a index index flag 用以标记划线位 flag 0 表示未被划线 flag 1 表示有划线过 flag 2 表示为两直线交点 ans 用以记录 a 中 0 的位置 循环后重新初始化 flag ans flag zeros s ans zeros s 一次循环划线全过程 终止条件是所有的零元素均被直线覆盖 即在 flag 0 位 index 0 while sum sum index 按行找出 0 所在位置 并对 0 所在列划线 即设置 flag 同时修改 index 将结果填入 ans for i 1 s t 0 l 0 for j 1 s if flag i j 0 t j end end if l 1 flag t flag t 1 index t 0 ans i t 1 end end 按列找出 0 所在位置 并对 0 所在行划线 即设置 flag 同时修改 index 将结果填入 ans for j 1 s t 0 r 0 for i 1 s if flag i j 0 t i end end if r 1 flag t flag t 1 index t 0 ans t j 1 end end end 对 while sum sum index 处理过程 计数器 计算 ans 中 1 的个数 用 num 表示 num sum sum ans 判断是否可以终止 若可以则跳出循环 if s num break end 否则 进行下一步处理 确定未被划线的最小元素 用 m 表示 m max max a for i 1 s for j 1 s if flag i j 0 if a i j a 37 7 32 9 38 8 37 35 4 43 4 33 1 42 2 34 7 41 8 33 3 28 5 38 9 30 4 33 6 29 2 26 4 29 6 28 5 31 1 0 0 0 0 0 z ans fenpei a z 127 8000 ans 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 2 2 2 2 0 2 4 4 3 3 1 1 0 7 2 2 4 4 7 7 0 3 5 5 7 7 5 5 0 4