视频字幕
指派问题是运筹学中的一个经典优化问题。假设我们有4个人和4个任务，每个人完成每个任务都有不同的成本。我们的目标是将每个人分配给一个任务，使得总成本最小。这就是一个典型的指派问题。匈牙利法是解决这类问题的高效算法，它通过矩阵变换找到最优解。
现在我们开始第一步：行约简。行约简的原理是从每行中减去该行的最小值，这样做不会改变最优解的位置。首先找出每行的最小值：第一行最小值是2，第二行是3，第三行是1，第四行是4。然后每行的所有元素都减去对应的最小值。经过行约简后，我们可以看到每行都至少有一个零元素，这为后续寻找最优解奠定了基础。
接下来进行列约简。对行约简后的矩阵，我们需要找出每列的最小值。第一列最小值是3，第二列是0，第三列是0，第四列是0。然后每列的所有元素都减去对应的最小值。经过列约简后，我们得到了完全约简矩阵，可以看到矩阵中有更多的零元素。这个完全约简的矩阵为我们下一步寻找独立零提供了良好的基础。
现在我们在完全约简矩阵中寻找独立零。独立零是指每行每列最多只能选择一个零，且选中的零互不在同行同列。我们从零元素较少的行开始选择。第一行选择位置(0,1)的零，用绿色圆圈标记。第二行选择位置(1,0)的零，同时划掉同列的其他零。第三行选择位置(2,2)的零，第四行选择位置(3,3)的零。最终我们找到了4个独立零，这意味着我们找到了最优解！
当我们无法直接找到n个独立零时，需要使用最小覆盖线法。首先用最少的水平线和垂直线覆盖所有零元素。在这个例子中，我们用3条线就能覆盖所有零：两条水平线覆盖第2行和第3行，一条垂直线覆盖第2列。由于覆盖线数量3小于矩阵阶数4，说明需要继续约简。找出未被覆盖元素中的最小值1，未被覆盖的元素减去1，被双重覆盖的元素加上1，得到新的矩阵继续寻找独立零。