用Octave计算指派问题（匈牙利算法）
广告
{{v.name}}
匈牙利法是指派问题的专用最优解法，核心逻辑为：通过对成本矩阵做行、列消去（减去最小值），得到含尽可能多0元素的矩阵，0元素表示“最优潜在指派”，当能选出n个独立的0元素（每行每列仅1个）时，即为最优指派方案。
该方法仅需对矩阵做行/列变换、画盖0线、调整矩阵三步循环，手工计算简单，适用于\(n≤10\)的中小规模问题，且仅适用于n阶方阵的平衡指派问题（非平衡需先转化为平衡）。
适用前提
1. 成本矩阵为n阶方阵（执行者数=任务数）；
2. 目标为最小化总成本（最大化需先转化）；
3. 所有\(c_{ij}≥0\)（消去后自然满足）。
完整计算步骤（最小化成本）
以4阶成本矩阵为例，演示匈牙利法的全流程，核心分为初始化矩阵→找独立0元素→画盖0线→调整矩阵，循环至找到n个独立0元素。
步骤1：初始化成本矩阵——行消去+列消去
目的：让矩阵的每行、每列至少有1个0元素，且所有元素非负。
1. 行消去：对成本矩阵的每一行，减去该行的最小元素；
2. 列消去：对行消去后的矩阵的每一列，减去该列的最小元素。
步骤2：寻找独立0元素，判定是否为最优解
独立0元素：每行、每列仅能选1个的0元素，若能选出n个，则直接得到最优指派方案；若不足n个，进入步骤3。
手工找独立0元素的贪心方法：
1. 从含0元素最少的行/列开始，选定1个0元素，标记为独立0（如圈出\(\bigcirc\)）；
2. 划去该0元素所在的行和列，在剩余矩阵中重复步骤1；
3. 若最终圈出的独立0元素数=\(n\)，停止；否则需画盖0线。
步骤3：画最少的盖0线，覆盖矩阵中所有0元素
盖0线为水平或垂直线，要求线的数量最少，且覆盖所有0元素，手工画法：
1. 对无独立0元素的行打√；
2. 对打√行中的0元素所在列打√；
3. 对打√列中的独立0元素所在行打√；
4. 重复2-3，直到无新的行/列可打√；
5. 对未打√的行画水平线，对打√的列画垂直线，得到的即为最少盖0线。
盖0线的数量 = 当前找到的独立0元素数，若盖0线数=\(n\)，则已找到最优解。
步骤4：调整成本矩阵，增加0元素数量
目的：在未被盖0线覆盖的区域生成新的0元素，同时保持已有的0元素不变，调整方法：
1. 找到未被盖0线覆盖的所有元素中的最小值，记为\(\theta\)；
2. 对未被覆盖的区域的所有元素，减去\(\theta\)；
3. 对两条盖0线的交点处的元素，加上\(\theta\)；
4. 仅被1条盖0线覆盖的元素，保持不变。
步骤5：循环判定
调整后得到新的成本矩阵，返回步骤2，重新寻找独立0元素，直到选出n个独立0元素，得到最优解。
例子：
4个工人（\(A_1,A_2,A_3,A_4\)）分配4个任务（\(B_1,B_2,B_3,B_4\)），单位成本矩阵如下（单位：元），求总成本最小的指派方案。
\(
C = \begin{bmatrix}
8 & 5 & 9 & 7 \\
6 & 7 & 8 & 9 \\
5 & 8 & 4 & 6 \\
7 & 6 & 8 & 5
\end{bmatrix}
\)
步骤1：行消去+列消去
1. 行消去：每行减该行最小值
- 行1：min=5 → [3,0,4,2]
- 行2：min=6 → [0,1,2,3]
- 行3：min=4 → [1,4,0,2]
- 行4：min=5 → [2,1,3,0]
行消去后矩阵：\(\begin{bmatrix}3&0&4&2\\0&1&2&3\\1&4&0&2\\2&1&3&0\end{bmatrix}\)
2. 列消去：每列最小值均为0，无需消去，矩阵不变。
步骤2：寻找独立0元素
- 行2仅有1个0（列1），圈出\(\bigcirc\)，划去行2、列1；
- 行1仅有1个0（列2），圈出\(\bigcirc\)，划去行1、列2；
- 行3仅有1个0（列3），圈出\(\bigcirc\)，划去行3、列3；
- 行4仅有1个0（列4），圈出\(\bigcirc\)，划去行4、列4；
最终圈出4个独立0元素（等于n=4），直接得到最优指派方案。
步骤3：确定最优指派方案与总成本
独立0元素的位置为：
- \(A_1→B_2\)（\(c_{12}=5\)）、\(A_2→B_1\)（\(c_{21}=6\)）、\(A_3→B_3\)（\(c_{33}=4\)）、\(A_4→B_4\)（\(c_{44}=5\)）；
总最小成本：\(5+6+4+5=20\)元。
代码如下：
function [assign, opt_val] = hungarian_assign(C, type)
% 匈牙利法求解指派问题（n阶方阵）
% 输入：
% C: n×n矩阵，成本矩阵（type='min'）或利润矩阵（type='max'）
% type: 求解类型，'min'=最小化成本，'max'=最大化利润
% 输出：
% assign: 1×n向量，assign(i)=j表示将第i个执行者指派给第j个任务
% opt_val: 最优值（最小成本/最大利润）
% 输入校验
[n, m] = size(C);
if n ~= m
error('成本/利润矩阵必须为n阶方阵！');
end
if ~ismember(type, {'min', 'max'})
error('type必须为''min''或''max''！');
end
% 保存原始矩阵，用于最终计算最优值
origC = C;
% 最大化利润转化为最小化成本（用cost变量，不覆盖origC）
if strcmp(type, 'max')
M = max(origC(:));
cost = M - origC;
else
cost = origC;
end
% 匈牙利法核心步骤（行消去+列消去+找独立0+调整矩阵）
row_mask = false(1, n);
col_mask = false(1, n);
assign = zeros(1, n);
row_assign = zeros(1, n); % row_assign(j)=i 列j指派给行i
% 行消去
for i = 1:n
cost(i,:) = cost(i,:) - min(cost(i,:));
end
% 列消去
for j = 1:n
cost(:,j) = cost(:,j) - min(cost(:,j));
end
% 寻找独立0元素并重复调整（核心循环）
while true
% 标记独立0并获得列->行的指派（row_assign）
[row_mask, col_mask, row_assign] = mark_zero(cost, n);
% 画盖0线：线穿过所有未标记的行和所有已标记的列
line_num = (n - sum(row_mask)) + sum(col_mask);
if line_num == n
break;
end
% 调整矩阵：找到未被任何线覆盖的最小值并调整
% 未被覆盖的元素位于被标记的行且列未被标记
uncovered = row_mask' & ~col_mask;
vals = cost(uncovered);
if isempty(vals)
break;
end
theta = min(vals);
cost(uncovered) = cost(uncovered) - theta;
% 将theta加到被两条线覆盖的元素（即未被标记的行与已标记的列的交点）
cost(~row_mask', col_mask) = cost(~row_mask', col_mask) + theta;
end
% 确定指派方案
for j = 1:n
assign(row_assign(j)) = j;
end
% 计算最优值（直接使用原始矩阵origC）
opt_val = sum(origC(sub2ind([n,n], 1:n, assign)));
end
% 辅助函数：标记独立0元素
function [row_mask, col_mask, row_assign] = mark_zero(cost, n)
% 使用标准匈牙利流程：先贪婪找独立0（starred zeros），然后标记行/列
row_star = zeros(1, n); % row_star(i) = j 表示行i的star列
col_star = zeros(1, n); % col_star(j) = i 表示列j的star行
for i = 1:n
for j = 1:n
if cost(i,j) == 0 && row_star(i) == 0 && col_star(j) == 0
row_star(i) = j;
col_star(j) = i;
end
end
end
row_assign = col_star; % 返回列->行的指派（col j 指派给 row col_star(j)）
% 标记：先标记所有没有star的行
row_mask = false(1, n);
col_mask = false(1, n);
for i = 1:n
if row_star(i) == 0
row_mask(i) = true;
end
end
% 反复：在被标记的行中标记含0的列；在被标记的列中标记含star的行，直到不再改变
while true
changed = false;
for i = 1:n
if row_mask(i)
for j = 1:n
if cost(i,j) == 0 && ~col_mask(j)
col_mask(j) = true;
changed = true;
end
end
end
end
for j = 1:n
if col_mask(j)
if col_star(j) ~= 0 && ~row_mask(col_star(j))
row_mask(col_star(j)) = true;
changed = true;
end
end
end
if ~changed
break;
end
end
end
结果如下：
>> [assign1, val1] = hungarian_assign([8 5 9 7;6 7 8 9;5 8 4 6;7 6 8 5], 'min')
assign1 =
2 1 3 4
val1 = 20
