匈牙利算法 - 分配系统 [英] Hungarian algorithm - assign systematically

问题描述

我实施匈牙利算法中的一个项目。我设法得到它的工作，直到所谓的维基百科。我设法让电脑产生足够的零，以便覆盖线路的最小量为行/列的数量，但我​​坚持，当涉及到实际转让代理权，以合适的工作。我看我怎么可以指定自己，但是这更多的试错 - 也就是，我看不出这当然是必不可少的系统方法的计算机以获取它的工作

I'm implementing the Hungarian algorithm in a project. I managed to get it working until what is called step 4 on Wikipedia. I do manage to let the computer create enough zeroes so that the minimal amount of covering lines is the amount of rows/columns, but I'm stuck when it comes to actually assign the right agent to the right job. I see how I could assign myself, but that's more trial and error - i.e., I do not see the systematic method which is of course essential for the computer to get it work.

假设我们有这个矩阵中底：

Say we have this matrix in the end:

   a  b  c  d
0  30 0  0  0
1  0  35 5  0
2  60 5  0  0
3  0  50 35 40

我们必须采取有分配给作业的每个代理的零点是（a，3），（B，0），（C，2）和（d，1）。什么是背后的艇员选拔这些的系统？我的code现在挑选（B，0）第一，而忽略行0和列b从现在开始。但是，它然后拾取（一，1），但与这个值拾取没有分配可能用于行3了。

The zeroes we have to take to have each agent assigned to a job are (a, 3), (b, 0), (c,2) and (d,1). What is the system behind chosing these ones? My code now picks (b, 0) first, and ignores row 0 and column b from now on. However, it then picks (a, 1), but with this value picked there is no assignment possible for row 3 anymore.

任何提示都是美联社preciated。

Any hints are appreciated.

推荐答案

嗯，我还是设法解决它到底。我使用的方法是检查是否有列/行只有一个零。在这种情况下，该代理必须使用工作，并且该列和行具有在未来被忽略。然后，再做一次，以获得每个代理的工作。

Well, I did manage to solve it in the end. The method I used was to check whether there are any columns/rows with only one zero. In such case, that agent must use that job, and that column and row have to be ignored in the future. Then, do it again so as to get a job for every agent.

在我的例子，（B，0）将是第一选择。之后，我们有：

In my example, (b, 0) would be the first choice. After that we have:

   a  b  c  d
0  x  x  x  x
1  0  x  5  0
2  60 x  0  0
3  0  x  35 40

再次使用该方法，我们可以做（A，3），等等。我不知道是否它已被证明，这是总是正确的，但现在看来，这是。

Using the method again, we can do (a, 3), etc. I'm not sure whether it has been proven that this is always correct, but it seems it is.

这篇关于匈牙利算法 - 分配系统的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！