需要配对算法 - 基于匈牙利？ [英] Need pairing algorithm - based on Hungarian?
问题描述
匈牙利或库恩 - Munkres算法（很好的说明这里）对从两组对象（中的 N 和 M 的对象分别的 N> = M 的），这样整体的差异化（或成本配对对象之间的分配）是最小的。该算法中的一个特点不适合我不过：它不仅详尽的配对，在这个意义上，这将配对的所有 M 的对象提供一些n个对象的。取而代之的是，我希望能够建立任意数量的 K对（ K＆LT; = M 的）与总成本最小。例如，有一种50x30输入成本矩阵;库恩 - Munkres将创造最佳的，但所有30个对。虽然我需要创建只是20对这样的最佳状态。
Hungarian or Kuhn-Munkres algorithm (good description here) pairs objects from two sets (of n and m objects respectively, n>=m) so that the overall "difference" (or "cost" of assignment) between paired objects be minimal. One feature of the algo doesn't suit me however: it does only exhaustive pairing, in the sense that it will pair all m objects with some of n objects. Instead of this, I'd want to be able to create arbitrary number k of pairs (k<=m) with overall cost minimal. For example, there is a 50x30 input cost matrix; Kuhn-Munkres will optimally create but all 30 pairs. While I need just 20 pairs to be created such optimally.
还能有匈牙利算法的任何修改，允许这一点，或者完全另一种算法中办呢？我AP preciate你的答案高度。
Can there be any modification of Hungarian algorithm allowing for this, or maybe a totally another algo to do it? I appreciate your answers highly.
推荐答案
下面有一些想法去思考：
Here are a few ideas to think about:
1）假设你写下来与n列和m行的成本矩阵。如果n大于m添加填充行与恒大的成本，使之方。行和列的最小成本分配现在将他们匹配填充行丢弃一些列。假设你现在添加填充柱以很低的成本为普通的行和恒大费用为填充列。该解决方案将现匹配适当的行本栏目之一，采取非常低的成本优势。这减少了匹配的东西明智的行数。如果添加MK这样的列我想你会最终有一个最低的成本匹配，真正分配行只能支持k。
1) Suppose you write down your cost matrix with n columns and m rows. If n is greater than m you add padding rows with constant large cost to make it square. A minimum cost assignment of rows and columns will now discard some columns by matching them to padding rows. Suppose you now add a padding column with very low cost for the ordinary rows and the constant large cost for the padding columns. The solution will now match one of the proper rows to this column, to take advantage of the very low cost. This reduces the number of rows that match to something sensible. I think if you add m-k such columns you will end up with a minimum cost matching that really assigns only k of the rows.
Here is an example of pairing 3 with 3 in 5x5, assuming ?
marks problem-specific values > 0 but < 100 (you may
need more extreme values than 0 and 100 to force the sort of
solution you want depending on what your data values are).
? ? ? ? ? 0 0
? ? ? ? ? 0 0
? ? ? ? ? 0 0
? ? ? ? ? 0 0
? ? ? ? ? 0 0
100 100 100 100 100 100 100
100 100 100 100 100 100 100
我想到的是一个最佳的解决方案将使用 从遥远的两个0 右侧和从底部行x两100秒。剩余的细胞 是的正方形内的3×3的匹配？的
I expect that an optimal solution will use two 0s from the far right and two 100s from the bottom rows. The remaining cells are a 3 x 3 matching within the square of ?s
确定 - 在这里就是一个证明，添加列，然后行作为上述产生的匹配你想要的那种：
OK - here is a proof that adding columns and then rows as above produces the sort of matching you want:
假设你需要使用值0℃的成本矩阵; X - LT; 100加s列和行0和100秒的边界如上，那么解决它作为一个分配问题。画两条线在0和100秒的边界，扩展它们切正方形分成四个区域，其中在左上角的区域是原来的矩阵。如果分配算法没有选择任何的细胞在右下方区域然后它选择氏细胞在右上角区域（接的S最右边的列），所以S在所述orgininal成本矩阵的行中的左上方区域被配对细胞处于零列。在顶部区域的其他行必须与非零柱进行配对，所以你必须在原始区域留下s行的匹配，因此小号列，不成对（即，成对的具有零小区）。
Suppose you take a cost matrix with values 0 < x < 100 and add a border of s columns and rows of 0s and 100s as above, then solve it as an assignment problem. Draw two lines at the border of the 0s and 100s, extending them to cut the square into four regions, where the region at the top left is the original matrix. If the assignment algorithm didn't choose any of the cells in the bottom right region then it chose s cells in the top right region (to pick the s rightmost columns), so s rows in the orgininal cost matrix in the top left region are paired with cells in a zero column. The other rows in the top region must be paired with a non-zero column, so you have a matching in the original region that leaves s rows, and so s columns, unpaired (that is, paired with a zero cell).
是否有可能在assigment解决方案有任何单元格右下角区域选择的的SxS？考虑任何此类转让。为了证明在上部左侧区域中的至少一个小区必须选择，假定没有被选中。然后我们必须以某种方式选择从每个顶端n行，$ P $的小区psumably通过从右上方区域采摘细胞。每个这样的单元必须在一个单独的列，但也有在右上角区域，这是不够的，因为我们只需要一个列我们要跳过每个匹配仅s列，我们已经在此使用的一列区域已经填补在右下区域的细胞。因此，假设该解决方案选择在原始左上区域的至少一个小区和所述右下区域中的至少一个细胞。选择其他两个单元格，使这四个边角的正方形。这些细胞不能选择。如果我们选择这些细胞，而不是当前选择的二，我们得到了不同的解决方案。这两个新的细胞是一个0细胞从顶部右侧和从左下方100细胞。他们会从右下方的值大于零，在主基质的细胞替换100细胞。因此，这将使我们假定溶液更好，从而使包含在右下方区域中的细胞中的任何解决方案不是最佳的解决方案，并且分配算法将不退还给我们。
Is it possible that the assigment solution has any cells in the s x s lower right region chosen? Consider any such assignment. To prove that at least one cell in the upper left region must be chosen, suppose none are chosen. Then we must somehow choose a cell from each of the top n rows, presumably by picking cells from the top right region. Each such cell must be in a separate column, but there are only s columns in the top right region, which won't be enough because we need only one column for each matching we want to skip, and we have used one column in this region already to fill in a cell in the lower right region. So suppose the solution chooses at least one cell in the original upper left region and at least one cell in the lower right region. Pick the two other cells that make this into four corners of a square. These cells cannot be chosen. If we choose those cells instead of the two that are currently chosen, we get a different solution. The two new cells are a 0 cell from the top right and a 100 cell from the bottom left. They would replace a 100 cell from the bottom right and a cell of value greater than zero in the main matrix. So this would make our supposed solution better, so any solution that contains a cell in the bottom right region is not a best solution, and the assignment algorithm will not return it to us.
所以这一招加0的列，然后行较大的值会产生分配算法解决方案，它的省略了一个匹配的每个（行，列）原溶液。
So this trick of adding columns of 0s and then rows of large values will produce an assignment algorithm solution that does omits one matching from the original solution for each (row, column) added.
2）的分配问题是
2) The assignment problem is a special case of the http://en.wikipedia.org/wiki/Minimum-cost_flow_problem. I think you want a minimum cost flow that transfers k units from rows to columns, so you could try solving it like this.
3）最小代价流问题是线性编程的一个特殊情况。我想你可以写下线性规划在区间[0,1]编号分配到矩阵，使得每行，每列和最多不超过1，所有细胞的总数为k的细胞。目标函数为然后在每个小区的次数其成本。
3) The minimum cost flow problem is a special case of linear programming. I think you could write down a linear program to assign numbers in the range [0,1] to cells of the matrix such that each row and each column sums up to no more than 1 and the total of all the cells is k. The objective function is then the number in each cell times its cost.
这篇关于需要配对算法 - 基于匈牙利？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
