分享兴趣，传播快乐，增长见闻，留下美好！
亲爱的您，这里是LearningYard新学苑。
今天小编为大家带来
“学越千山（四二）：指派问题及匈牙利算法”，
欢迎您的访问。
Share interest, spread happiness, increase knowledge, and leave beautiful.
Dear, this is the LearingYard Academy!
Today, the editor brings the
Learning over a thousand mountains(42):Assignment Problem and Hungarian Algorithm，
Welcome to visit!
思维导图
Mind mapping
指派问题
Assignment Problem
指派问题是整数规划中的一种特殊类型，主要用于解决资源分配问题。其典型应用场景是：有n项任务需要分配给n个人去完成，每个人完成每项任务的时间和成本可能不同，目标是找到一种分配方案，使得总时间或总成本最小。指派问题虽然可以通过单纯形法、图解法等方法求解，但通常使用0-1整数规划模型进行建模和求解。
The assignment problem is a special type of integer programming, mainly used to solve resource allocation problems. Its typical application scenario is: there are n tasks that need to be assigned to n people to complete, and the time and cost of each person completing each task may vary. The goal is to find an allocation scheme that minimizes the total time or total cost. Although the assignment problem can be solved using methods such as the simplex method and graphical method, it is usually modeled and solved using a 0-1 integer programming model.
匈牙利算法
Hungarian Algorithm
匈牙利算法是一种求解指派问题的多项式时间算法，它基于“行（列）最小覆盖”和“划零”两个基本操作，通过不断迭代找到最优解。
The Hungarian algorithm is a polynomial-time algorithm for solving assignment problems. It is based on two basic operations: "row and column minimum coverage" and "zeroing", and finds the optimal solution through continuous iteration.
操作步骤：
Operation steps:
1、减去行最小值
1.Subtract the minimum value of each row
对于每一行，找到该行的最小值，并从该行中的每个元素中减去这个最小值。
For each row, find the minimum value and subtract it from each element in the row.
2、减去列最小值
2.Subtract the minimum value of each column.
对于每一列，找到该列的最小值，并从该列中的每个元素中减去这个最小值。这一步是为了使得系数矩阵中包含更多的0元素。
For each column, find the minimum value and subtract it from each element in the column. This step is to make the coefficient matrix contain more 0 elements.
3、若已无法用更少的线覆盖所有0元素，则当前匹配即为最大匹配。
If it is impossible to cover all 0 elements with fewer lines, the current matching is the maximum matching.
如果需要的线数少于矩阵的阶，则进入下一步:
If the number of lines required is less than the order of the matrix, proceed to the next step:
4、覆盖所有0元素，用最少的水平线和垂直线覆盖掉矩阵的所有0元素。
Cover all 0 elements, using the minimum number of horizontal and vertical lines to cover all 0 elements in the matrix.
1）画圈
1)Circle
选择单零列,首先寻找只包含一个0的列，给这个0画一个圈，划去该行其他0元素。保持行列上只含一个0元素。
Select a single zero column,First, find a column that contains only one zero, draw a circle around this zero, and remove all other zero elements in the row. Keep only one zero element in the row and column.
2）打勾
2)Ticks
对没有画圈的行打勾；
对打勾行中含有划去的0元素的列打勾；
对打勾列中含有画圈的列打勾；
Tick the lines without circles;
Tick the columns with crossed 0 elements in the ticked rows;
Tick the columns with circles in the ticked columns;
3）划线
3)Dashes
对没有打勾的行画横线；
对打勾的列画竖线；
使所有画圈的零元素都被覆盖。
Draw a horizontal line through the unchecked rows;
Draw vertical lines for the checked columns;
Make all the zero elements in the circle be covered.
5、创建额外的0元素
5.Create additional 0 elements
在未被线覆盖的行和列中，找到最小的元素，记作k。
Find the smallest element in the rows and columns not covered by the line, and record it as k.
将所有未被线覆盖的行中的元素减去k，将所有被线覆盖的列中的元素加上k。
Subtract k from all elements in rows not covered by the line, and add k to all elements in columns covered by the line.
重复步骤4和5，直到找到最大匹配或确定无法找到更大的匹配为止。
Repeat steps 4 and 5 until you find the maximum match or determine that you cannot find a larger match.
今天的分享就到这里了，
如果您对文章有独特的想法，
欢迎给我们留言。
让我们相约明天，
祝您今天过得开心快乐！
That's all for today's sharing.
If you have a unique idea about the article,
please leave us a message,
and let us meet tomorrow.
I wish you a nice day!
翻译：百度翻译
参考资料：百度百科，
《管理运筹学》
本文由LearningYard新学苑整理并发出，如有侵权请后台留言沟通
