0

我遇到了以下问题：

  • 有两个不相交的集合，A并且B
  • 对于每对元素 ( a, b)（a属于 set A，其中b属于 set B），预先知道一个概率pij。它表示匹配 的概率（确定性级别）a，b或者换句话说，a匹配b的紧密程度（反之亦然，因为pij== pji）。
  • 我必须找到具有最高概率/确定性的匹配并找出描述匹配的对 ( a, )b
  • 每个元素必须与另一个集合中的另一个元素匹配/配对一次（就像在标准的二分匹配问题中一样）
  • 如果可能的话，我想计算一个数字，该数字近似表示所获得匹配的不确定性级别（假设 0 代表随机猜测，1 代表确定性）

下面描述了一个需要这种算法的简单实际示例（这实际上不是我要解决的问题！）：

  • 要求两个人在一张纸上写字母 a - z
  • 对于每对字母 ( a, )，我们运行一个模式匹配器来确定person写的字母代表person写的b字母的概率。这给了我们一个概率矩阵，它表示每对字母 ( , )的某种相似性相关性aAbBab
  • 对于那个人写的每封信A，我们需要找到这个人写的对应的信B

当前方法： 我想知道我是否可以只分配与确定性水平的对数/集合中的元素与集合中的元素匹配的概率成比例的权重，然后a运行A最大加权二分匹配以找到最大总和。对数是因为我想最大化多个匹配的总概率，并且由于单个匹配（表示为匹配元素对-bBab) 形成一个事件链，它是概率的乘积，通过取对数，我们将其转换为概率之和，然后使用加权二分匹配算法（例如匈牙利算法）轻松最大化概率之和。但我不知何故怀疑这种方法能否确保在统计预期最大值方面的最佳匹配。

经过一番搜索，我发现最接近的问题是两阶段随机最大加权匹配问题，这是 NP-hard，但我实际上需要某种“单阶段”随机最大加权匹配问题。

4

1 回答 1

1

我想知道你是否可以使用 MaxFlow/MinCut。我目前无法证明它是最优的，但无论如何你的问题可能是 NP 难的。当您有一个 V=(A,B) 的二分图时，您可以使用 MF/MC 找到完美匹配，方法是创建一个连接到 A 中所有节点的权重为 1 的源和一个连接到 B 中所有节点的接收器权重 1. 我建议您将从 A 到 B 的边的权重设为您上面提到的概率。你怎么看？

于 2011-04-05T16:39:28.657 回答