匈牙利算法原理指派问题

### 匈牙利算法解决指派问题的原理

#### 指派问题概述
指派问题是组合优化领域的一个经典问题，其目的是在一个给定的成本矩阵中寻找一种分配方式使得总成本最小化。具体来说，在一个 \(n \times n\) 的效率矩阵 \(C=[c_{ij}]\) 中，\(i=1,2,\ldots,n\), \(j=1,2,\ldots,n\) 表示第 i 个人完成第 j 项工作的代价或时间，则指派问题就是找出一组互不相同的列下标 \(p_j(j)\)，使总的费用达到最低。

#### 匈牙利算法的核心思想
匈牙利算法通过一系列变换操作来逐步减少原有效益矩阵中的数值，直到能够找到一个零元素构成的最大匹配为止。该过程基于以下两个重要性质：

- 如果从效益矩阵的一行(或一列)各元素分别减去同一个数得到新的效益矩阵，则新旧两矩阵对应的最优解相同。
- 若某效益矩阵中存在覆盖所有0元至少需要k条直线的情况，则此矩阵中独立0元数目不超过k个[^2]。

#### 算法步骤解析
1. **初始化阶段**
- 对于原始的任务—工人对应的时间消耗矩阵 C 进行处理，对于每一行和每一列都做相应的调整，使其内部含有尽可能多的零值。

2. **构建初始可行解**
- 尝试为每一个任务指定一名员工执行，即尝试建立最大数量的独立零位置连线（可以理解成二分图里的完美匹配）。

3. **改进当前解决方案**
- 当无法再增加更多的独立零时，计算未被划线经过的所有单元格内的最小值，并对该部分区域实施特定变化以创造更多可能的选择路径。

4. **重复上述过程直至获得满意的结果**

最终当所有的人都有了各自的工作安排且不存在交叉冲突的时候就找到了全局最优解。

function [y,fval,flag]=Hungary(C)
[m,n]=size(C);
if m~=n
    flag=-1;
    y=[];
    fval=[];
else
    % 初始化标记数组
    row_mark=zeros(m,1); col_mark=zeros(n,1);
    while true
        % 寻找未标记行列中的最小值并更新相应位置...
        ...
        break; % 条件满足则跳出循环
    end
end