解决随机最大二分匹配问题
我遇到了以下问题：
- <
- 每对元素 (
a,b /code>) （是预先知道的。它表示a属于集合A，其中b属于集合B）有概率 < code>pija与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难的，但我实际上需要某种“单阶段”随机最大加权匹配问题。
I have faced the following problem:
- there are two disjoint sets,
AandB - for each pair of elements (
a,b) (abelongs to setA, wherebbelongs to setB) there a probabilitypijis known in advance. It represents the probability (certainty level) thatamatchesb, or in other words, how closelyamatchesb(and vice-versa, becausepij==pji). - I have to find a matching with the highest probability/certainty and find out pairs (
a,b) which describe the matching - every element must be matched / paired with another from the other set exactly once (like in the standard bipartite matching problem)
- if possible, I would like to compute a number which approximately expresses the uncertainty level for the obtained matching (let's say that 0 represents random guess and 1 represents certainty)
A simple practical example in which such algorithm is required is described below (this is not actually the problem I am solving!):
- two people are asked to write letters
a - z on a piece of paper - for each pair of letters (
a,b) we run a pattern matcher to determine the probability that letterawritten by personArepresents letterbwrote by personB. This gives us the
probability matrix which expresses some kind of similarity correlation
for each pair of letters (a,b) - for each letter that person
Awrote,
we need to find the corresponding
letter written by personB
Current approach:
I am wondering if I could just assign weights which are proportional to the logarithm of certainty level / probability that element a from set A matches element b from set B and then run maximum weighted bipartite matching to find the maximum sum. The logarithm is because I want to maximize the total probability of multiple matching, and since single matches (represented as pairs of matched elements a - b) form a chain of events, which is a product of probabilities, by taking the logarithm we converts this to a sum of probabilities, which is then easily maximized using an algorithm for weighted bipartite matching, such as Hungarian algorithm. But I somehow doubt this approach would ensure the best matching in terms of statistical expected maximum.
After searching a bit, the closest problem I found was a two-stage stochastic maximum weighted matching problem, which is NP-hard, but I actually need some kind of "one-stage" stochastic maximum weighted matching problem.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我想知道你是否可以使用MaxFlow/MinCut。我目前无法证明它是最优的，但无论如何你的问题可能是 NP 难的。当您有一个 V=(A,B) 的二分图时，您可以使用 MF/MC 来找到完美匹配，方法是创建一个连接到 A 中所有节点、权重为 1 的源和一个连接到 B 中所有节点的接收器，权重 1. 我建议你将从 A 到 B 的边的权重设为你上面提到的概率。你怎么认为？
I wonder if you can use MaxFlow/MinCut. I can't prove it's optimal at the moment, but your problem may be NP-hard anyway. You can use MF/MC to find a perfect matching when you have a bipartite graph with V=(A,B) by creating a source connected to all nodes in A with a weight of 1 and a sink connected to all nodes in B with weight 1. I'm proposing you make the weights of edges that cross from A to B be the probabilities you mentioned above. What do you think?