求解随机最大二分匹配问题

我遇到了以下问题： 有两个不相交的集合，

A

和

B

对于每对元素（

a

，

b

）（

a

属于集合

A

，其中

b

属于集合

B

），预先知道概率

pij

。它代表

a

匹配

b

的概率（确定性水平），或换句话说，

a

与

b

的匹配程度（反之亦然，因为

pij

==

pji

）。 我必须找到具有最高概率/确定性的匹配并找出描述匹配的对（

a

，

b

） 每个元素必须与另一个元素的另一个元素匹配/配对一次（如标准的二分匹配问题） 如果可能的话，我想计算一个近似表示所得匹配的不确定性水平的数字（假设0代表随机猜测，1代表确定性） 下面描述了一个需要这种算法的简单实际例子（这实际上不是我要解决的问题！）： 两个人被要求写信 a - z在一张纸上 对于每对字母（

a

，

b

），我们运行模式匹配器来确定由人

A

写的字母

a

表示由人

B

写的字母

b

的概率。这给了我们 表达某种相似性相关性的概率矩阵 每对字母（

a

，

b

） 对于

A

写的每封信， 我们需要找到相应的 由人写的信

B

目前的做法： 我想知道我是否可以只分配与确定性水平/概率的对数成比例的权重，来自集合

A

的元素

a

与集合

B

中的元素

b

匹配，然后运行最大加权二分匹配以找到最大总和。对数是因为我想最大化多次匹配的总概率，并且因为单个匹配（表示为匹配元素对

a

-

b

）形成一个事件链，这是概率的乘积，通过取对数我们将其转换为然后使用加权二分匹配算法（例如匈牙利算法）容易地最大化概率之和。但我怀疑这种方法可以确保在统计预期最大值方面达到最佳匹配。 搜索了一下后，我发现的最接近的问题是两阶段随机最大加权匹配问题，这是NP难的，但实际上我需要某种“一阶段”随机最大加权匹配问题。