algorithm - N 个请求者和 M 个资源的充足资源

Question

这个问题感觉很熟悉，但我不记得解决方案(或者它是否有用)。

另一种表达方式是，您有 N 个潜在匹配项，以及它们可能处于的 M 个位置 - 每个 N 只能适合 M 个位置的子集 - 是否有足够的位置用于此配置。

最好用图表来说明。将 N 设置为 3(沿着顶部)并将 M 设置为 4，使用 1 指示请求者 (N) 需要哪个资源 (M) - 资源不足的示例情况:

   0  1  2
0  1  1  1
1  1  1  1
2  0  0  0
3  0  0  0

   0  1  2
0  1  X  X
1  X  1  X
2  0  0  0
3  0  0  0

一旦分配了 0 和 1，2 的子集中就没有可用资源了。另一方面，这种情况将允许足够的资源分配。

   0  1  2
0  1  1  1
1  1  1  1
2  0  0  0
3  0  1  0

   0  1  2
0  1  X  X
1  X  X  1
2  0  0  0
3  0  1  0

我真的只关心分配能不能满足。不一定是满足它的配置。

如果没有简单的方法来获得是或否，我正在考虑首先定位可能性最小的行和列。我认为这会迅速缩小范围。同样，确定无法满足的情况可能是一种很好的消除方法。

我想问你，是否有任何数学、好的算法或一类问题我应该为此考虑？它似乎来自实时编程或数独游戏。即使只是一个词到谷歌将不胜感激。

谢谢!

Answer 1

我相信你想检查分配问题(http://en.wikipedia.org/wiki/Assignment_problem)

解决它的一种方法是使用匈牙利算法 ( http://en.wikipedia.org/wiki/Hungarian_algorithm )

并且有一些库已经实现了它，例如:http://robotics.stanford.edu/~gerkey/tools/hungarian.html