基于置信度匹配两组对象的最佳方法

Question

我搜索了这个问题一段时间，但找不到任何相关内容。

假设我有两种类型的对象，我想在它们之间创建一一对应的关系。假设我的第一组是

integers

，第二组是

letters

。我以某种方式知道每个整数和字母对的置信度（权重/相关性等）。

还假设我有 4 个整数和 3 个字母。他们的对应关系是

1-A, 2-B, 3-C, 4-None

。 （我正在努力得到这个结果）

另外，我知道整数和字母之间的关系。

1 -> (A, 0.9)
2 -> (B, 0.5), (C, 0.4)
3 -> (B, 0.2), (C, 0.4)
4 -> (B, 0.1)

其余都是零，例如

2 -> (A, 0)

等

在此示例中，

1-A

是一对具有高置信度的

0.9

，并且没有其他整数与

A

匹配。因此，我会将这一对添加到匹配对列表中。现在，我需要在

2-B

和

2-C

与

3-B

和

3-C

之间进行选择。由于前一种是更好的选择（置信度之和是

0.9

，而不是

0.6

），因此我们选择

2-B

和

2-C

。

将

1, 2, 3

分别分配给

A, B, C

后，

4

将一无所有。所以，不会有。

我可以使用某种蛮力算法来做到这一点，但我正在寻找一种优雅的方法来做到这一点。对我来说，它看起来像一个图算法，但无法想出比暴力更好的东西。

我可以使用这个算法的更优雅的方式吗？

此时语言并不重要，但我正在使用 python。

Answer 1

这被称为“分配问题”。此链接解释了可以解决该问题的算法之一，即匈牙利算法，并提供了一些您应该能够复制和粘贴的 C 代码。