二分图匹配 |
您所在的位置：网站首页 › 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是 › 二分图匹配 |
二分图匹配
|
在任务指派问题（如n项工作由n个人承担，每个人完成不同工作所花时间不同，那如何分配使得花费的时间最少）以及一些多目标检测任务中的数据关联部分（如一个目标有多个特征点，有多个目标时检测到的特征点属于哪一个目标的问题）常常会看到Munkres算法，这里从原理及实现上简单介绍一下Munkres算法。 一、Munkres算法介绍Munkres算法也称为匈牙利算法，匈牙利算法起源于1955年 Kuhn 提出的指派问题解法，kuhn引用匈牙利数学家康尼格关于矩阵中0元素的定理:系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数，该解法称为匈牙利方法（Hungarian Method），1956年MERRILL M.FLOOD 给出了匈牙利方法的算法实现步骤，1957年James Munkres针对该方法做了改进，后来大家习惯叫匈牙利算法或Kuhn-Munkres(KM)算法或者Munkres算法，后续一些改进都沿用了这个名称，其主要用来解决分配问题。
如下图a,b,c,d四个工人完成p,q,r,s四项工作，矩阵C(i, j)表示每个工人完成对应一项工作所需的时间，经过求解后工人a对应工作q，b对应s，c对应r，d对应p，最少是23个单位的时间。
接下来以实际例子来展开Munkres算法基本步骤。公司接到EJGR四项任务，如何给甲乙丙丁四名员工分配可以使得总花费时间最少？
那上述例子系数矩阵就变为：
经过第一步变换后，系数矩阵中出现了0元素，如果能找到n个独立的0元素，那系数矩阵将这些独立零元素所在位置记为1，其余设为0，即可得到问题的最优解。试指派可以分为以下几步： 步骤1：从只有一个0元素的行开始，给这个0元素加圈\(\bigcirc\) （表示该行所代表的人只有一种任务可指派），然后划去该零元素所在列的其他0元素(表明该任务已指派)，标记为\(\Phi\) 步骤2：对只有一个0元素的列加圈 \(\bigcirc\) ，然后划去该行其他0元素，记为\(\Phi\) 步骤3：反复进行步骤1和步骤2，直到所有的0元素都被加圈或者划去为止 步骤4：如果经过步骤3之后还有未被加圈的0元素，且同一行至少有两个0元素（表明这个人可以指派多项任务），此时可以比较这些0元素对应列0元素较少的0元素加圈，然后划掉此列的0元素（表明选择性多的礼让选择性少的）进行试探，反复进行直到所有0元素都被加圈或者划掉 步骤5：如果加圈的0元素个数m刚好等于系数矩阵的阶数n，则问题得到求解。如果m < n，则继续下一大步骤。上面的例子经过试指派前面三个步骤得到：
现在公司接到新的任务ABCDE,且新来了一个员工，其系数矩阵如下：
这一步利用了前面提到的0元素的定理，其大体可以分为以下几步： 步骤1： 对没有加圈\(\bigcirc\)零元素的行打上\(\surd\) 步骤2： 对打\(\surd\)的行中含有标记为\(\Phi\)的列打上\(\surd\) 步骤3： 再对打\(\surd\)的列中含有加圈\(\bigcirc\)零元素的行打上\(\surd\) 步骤4： 重复步骤2和步骤3，直到不能新增\(\surd\)的行和列为止 步骤5： 对没有打\(\surd\)的行画一横线，对打\(\surd\)的列画上一竖线，这就得到了覆盖所有零元素的最少直线数L 如果Lc, 同理a把任务让给b，最后就变为了r>a, q>b, p>c。 这中间就出现了一条增广路径c>p>b>q>r。
C++ Code
参照后自己用C++实现了下，这里给出具体的代码放在本文最后附录。 五、衍生问题前面提到了采用Munkres算法需要满足3个条件，但实际情况下可能并不满足，这里参考：https://blog.csdn.net/Wonz5130/article/details/80678410，给出了几种衍生问题。 5.1 如果不是求最小值，是求最大值Max如何处理？找出系数矩阵中的最大值max，然后令系数矩阵变为max-系数矩阵各元素值，得到新系数矩阵，再按照正常匈牙利法即可求到。
5.3 一个人可以做几件事
如果一个人可以做k件事，那就把这个人的系数复制k份，相当于增加了虚拟人数，如果不是方阵，再构建虚拟工作 5.4 某个人不能做某项工作将问题转换为求最小值后，如果第i个人不能做第j项工作，则将系数\(C_{ij}\)设置为一个比系数矩阵中最大值大一些的数。 六、其他扩展二分图最小分配问题还可以采用分枝定界法 分支: 将一个问题不断细分为若干子问题, 之后逐个讨论子问题; 定界: 分支很多的情况下, 需要讨论的情况也随之增多, 这里就需要定界, 决定在什么时候不在进行分支;定界的作用是剪掉没有讨论意义的分支, 只讨论有意义的分支 具体内容可参考： https://www.geeksforgeeks.org/job-assignment-problem-using-branch-and-bound/ http://www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bb.pdf. 七、参考链接https://brc2.com/the-algorithm-workshop/ https://software.clapper.org/munkres/ https://blog.csdn.net/Wonz5130/article/details/80678410 https://zhuanlan.zhihu.com/p/62981901 https://www.geeksforgeeks.org/hungarian-algorithm-assignment-problem-set-1-introduction/ https://www.geeksforgeeks.org/hungarian-algorithm-for-assignment-problem-set-2-implementation/. 钱颂迪 《运筹学》第四版第6章 八、附录 C++代码 class Munkres { public: Munkres(int nRow, int nCol); ~Munkres(); bool Build(const std::vector& costs); float Compute(const std::vector& costs, std::vector& pairs); private: void StepOne(int& step); void StepTwo(int& step); void StepThree(int& step); void StepFour(int& step); void StepFive(int& step); void StepSix(int& step); void StepSeven(std::vector& pairs); void FindAZero(int& row, int& col); bool StarInRow(int row); void FindStarInRow(int row, int& col); void FindStarInCol(int col, int& row); void FindPrimeInRow(int row, int& col); void AugmentPath(); void ClearCovers(); void ErasePrimes(); void FindSmallest(float& minVal); void ShowCostMatrix(); void ShowMaskMatrix(); private: int nRow_; int nCol_; std::vector costs_; // nRow_ * nCol_ std::vector augPaths_; // nRow_ * 2 std::vector rowCover_; // 1 * nRow_ std::vector colCover_; // 1 * nCol_ std::vector marks_; // nRow_ * nCol_ int pathRow0; int pathCol0; int pathCount; }; /* * Ref: https://brc2.com/the-algorithm-workshop/ * * The following 6-step algorithm is a modified form of the original Munkres’ Assignment Algorithm (sometimes referred to as the Hungarian Algorithm). This algorithm describes to the manual manipulation of a two-dimensional matrix by starring and priming zeros and by covering and uncovering rows and columns. This is because, at the time of publication (1957), few people had access to a computer and the algorithm was exercised by hand. Step 0: Create an nxm matrix called the cost matrix in which each element represents the cost of assigning one of n workers to one of m jobs. Rotate the matrix so that there are at least as many columns as rows and let k=min(n,m). Step 1: For each row of the matrix, find the smallest element and subtract it from every element in its row. Go to Step 2. Step 2: Find a zero (Z) in the resulting matrix. If there is no starred zero in its row or column, star Z. Repeat for each element in the matrix. Go to Step 3. Step 3: Cover each column containing a starred zero. If K columns are covered, the starred zeros describe a complete set of unique assignments. In this case, Go to DONE, otherwise, Go to Step 4. Step 4: Find a noncovered zero and prime it. If there is no starred zero in the row containing this primed zero, Go to Step 5. Otherwise, cover this row and uncover the column containing the starred zero. Continue in this manner until there are no uncovered zeros left. Save the smallest uncovered value and Go to Step 6. Step 5: Construct a series of alternating primed and starred zeros as follows. Let Z0 represent the uncovered primed zero found in Step 4. Let Z1 denote the starred zero in the column of Z0 (if any). Let Z2 denote the primed zero in the row of Z1 (there will always be one). Continue until the series terminates at a primed zero that has no starred zero in its column. Unstar each starred zero of the series, star each primed zero of the series, erase all primes and uncover every line in the matrix. Return to Step 3. Step 6: Add the value found in Step 4 to every element of each covered row, and subtract it from every element of each uncovered column. Return to Step 4 without altering any stars, primes, or covered lines. DONE: Assignment pairs are indicated by the positions of the starred zeros in the cost matrix. If C(i,j) is a starred zero, then the element associated with row i is assigned to the element associated with column j. Some of these descriptions require careful interpretation. In Step 4, for example, the possible situations are, that there is a noncovered zero which get primed and if there is no starred zero in its row the program goes onto Step 5. The other possible way out of Step 4 is that there are no noncovered zeros at all, in which case the program goes to Step 6. */ Munkres::Munkres(int nRow, int nCol): nRow_(nRow), nCol_(nCol), pathRow0(0), pathCol0(0), pathCount(0) { costs_.resize(nRow_); for (int r = 0; r < nRow_; ++r) { costs_[r].resize(nCol_, 0); } marks_.resize(nRow_); for (int r = 0; r < nRow_; ++r) { marks_[r].resize(nCol_); // 1 is star zero, 2 is prime zero } rowCover_.resize(nRow_); // record the row whether be convered colCover_.resize(nCol_); // record the col whether be convered augPaths_.resize(nRow_ * 2); // max save 2 in one row for (int r = 0; r < nRow_ * 2; ++r) { augPaths_[r].resize(2); // record the augment path } } Munkres::~Munkres() { costs_.clear(); augPaths_.clear(); marks_.clear(); rowCover_.clear(); colCover_.clear(); } bool Munkres::Build(const std::vector& costs) { costs_ = costs; return true; } float Munkres::Compute(const std::vector& costs, std::vector& pairs) { costs_ = costs; bool done = false; int step = 1; while (!done) { ShowCostMatrix(); ShowMaskMatrix(); std::cout = nRow_) { done = true; } } } bool Munkres::StarInRow(int row) { bool tmp = false; for (int c = 0; c < nCol_; ++c) { if (marks_[row][c] == 1) { tmp = true; break; } } return tmp; } void Munkres::FindStarInRow(int row, int& col) { col = -1; for (int c = 0; c < nCol_; ++c) { if (marks_[row][c] == 1) { col = c; break; } } } void Munkres::FindStarInCol(int col, int& row) { row = -1; for (int r = 0; r < nRow_; ++r) { if (marks_[r][col] == 1) { row = r; break; } } } void Munkres::FindPrimeInRow(int row, int& col) { for (int c = 0; c < nCol_; ++c) { if (marks_[row][c] == 2) { col = c; break; } } } void Munkres::AugmentPath() { for (int p = 0; p < pathCount; ++p) { if (marks_[augPaths_[p][0]][augPaths_[p][1]] == 1) { marks_[augPaths_[p][0]][augPaths_[p][1]] = 0; } else { marks_[augPaths_[p][0]][augPaths_[p][1]] = 1; } } } void Munkres::ClearCovers() { for (int r = 0; r < nRow_; ++r) { rowCover_[r] = 0; } for (int c = 0; c < nCol_; ++c) { colCover_[c] = 0; } } void Munkres::ErasePrimes() { for (int r = 0; r < nRow_; ++r) { for (int c = 0; c < nCol_; ++c) { if (marks_[r][c] == 2) { marks_[r][c] = 0; } } } } void Munkres::FindSmallest(float& minVal) { for (int r = 0; r < nRow_; ++r) { for (int c = 0; c < nCol_; ++c) { if (rowCover_[r] == 0 && colCover_[c] == 0) { if (minVal > costs_[r][c]) { minVal = costs_[r][c]; } } } } } void Munkres::ShowCostMatrix() { std::cout |
构建成数学模型如下：
此时加圈的0元素个数刚好也为4，所以
也就是说甲分配任务R，乙分配任务J，丙分配任务E，丁分配任务G，共花费28小时。
经过步骤3.1和3.2后得到如下情况：
这时加圈的0元素个数为4 < 5(矩阵的阶数)，此时就是试分配的步骤5，需要按3.3 作最少的直线覆盖所有零元素
【本文地址】
今日新闻 |
推荐新闻 |