选择数字矩形的数字

Question

我发明算法有一个很大的问题.

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

我想将第一组中的节点与第二组中的节点连接起来.他们必须与最佳路径相连.- 所有路由的长度必须尽可能接近,每个节点只能连接一条路由. 像这样的东西:

我不想像下一张图片那样做,因为路线的长度非常不同.

下表演示了所有节点之间的长度.从这张表中,我想选择最佳解决方案.最好的解决方案是环绕的.

当我拥有一百个节点的组时,如何才能找到最佳解决方案？如果我尝试每一个组合,就会有100个!组合,这是很多.我不能为此发明任何算法.

Answer 1

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

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

1

首先，您必须知道二部图的最大匹配问题，并且可以在多项式时间内解决。最直接的匈牙利算法，其中O(nm)是n节点数，m是边数。对于您的情况的平面图，有更复杂的算法可以进一步提高性能。

让我们将其定义为一个函数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 部分中包含的平面图算法。