algorithm - 在具有相似长度的图中查找边

Question

我在发明算法方面遇到了很大的问题。

我有两组节点。比如说，我们在第一组中有 4 个节点，在第二组中有另外 4 个节点。下图说明了这一点:

我想将第一组的节点与第二组的节点连接起来。该算法应该找到一个理想的解决方案，其中所有连接的长度必须尽可能相似并且一组中的每个节点只能连接到第二组中的一个节点。强>

理想的解决方案如下图所示:

下图展示的不是理想的解决方案，因为这些连接的长度相差太大。

下表显示了每个节点之间的长度。从这张表中，我想找到理想的解决方案。解决方案被包围。

当我的群组有一百个节点时，我如何才能找到最佳解决方案？如果我尝试每一种组合，就会有 100 个!组合，这是很多。我无法提出具有合理复杂性的算法。

Answer 1

正如 Thomas@ 在评论中所问，问题的解决取决于您对“尽可能接近”的定义。让我们将解决方案中的边集定义为 S .假设定义被选择为最小化 max(S) - min(S) (这在实践中是一个合理的假设)，那么这个问题肯定可以在多项式时间内解决。

这是解决方案的示例。对于 100 个节点，只需几秒钟。

1

首先，你必须知道maximum matching problem对于二部图，它可以在多项式时间内求解。最直接Hungarian Algorithm需要 O(nm)其中n是节点数，m是边的数量。对于你的平面图，there are more sophisticated algorithms that can further improve the performance .

让我们将其定义为一个函数 Max_Match(X) , 它返回边集中的最大匹配数 X .

这Max_Match可以计算小于O(n^1.5) , 其中n是节点数。对于 n=100 , 我们只有 n^1.5 = 1000 .

---

2

然后让我们将您的问题转换为最大匹配问题。

让我们定义边集 E到我们可以选择的所有边缘。在你的情况下有 n*n E 中的边, 其中n是一侧的节点数。

让我们定义函数 F(E, low, high) = {e | e in E and |e| >= low and |e| <= high }这意味着 E 的子集边缘其长度介于 [low, high] 之间

然后对于给定的一对数字 low和 high ，当且仅当

Max_Match( F (E, low, high)) == n

---

3

但是，我们如何计算出 low 的值呢？和 high ？

low 的可能值和 high {|e|, e in E} 中所有可能的数字, 其中有 n^2数字。所以尝试所有可能的组合 low和 high将花费 n^4 .很多。

如果我们已经知道low , 我们能算出 high没有枚举？答案是肯定的。请注意:

引理 1

如果对于一个数字 h我们有<强> Max_Match( F (E, low, h)) == n

然后对于每个数字 h' >= h我们还有

Max_Match( F (E, low, h')) == n

这意味着我们可以使用二进制搜索来找出high。一旦我们修复了low .

---

4

所以最终解决方案的框架:

arr[] = {|e|, e in E}.sort()
for i in range(0, len(arr[])):
  low = i
  h_left = i, h_right = len(arr[])-1
  while h_left <= h_right:
    mid = (h_left+h_right)/2
    if Max_Match( F( E, arr[low], arr[mid]))==n:
      h_right = mid - 1
    else:
      h_left = mid + 1
  if h_left >= low:
    if arr[h_left] - arr[low] <= ans:
      ans = arr[h_left] - arr[low]

和ans将是解决方案中边缘之间的最小差异。该算法花费 O(n^3.5 * log(n)) , 其中n是节点数。

编辑:可以在以下位置找到上述算法在 C++ 中的简单而丑陋的实现: ideone.com/33n2Tg .因为我时间不够，我在这个解决方案中手工制作了一个简单的匈牙利算法，它在 n 时很慢很大。为了获得更好的性能，您将需要我在第 1 部分中包含的平面图算法。