algorithm - 多个起点 - 多个目的地

Question

我有一个优化问题。它只是有点像旅行推销员。

假设我有一组目的地和另一组相应的起点。我需要将每个目的地与一个起点联系起来，以使路线之间的差异尽可能小。

我对形成总距离最短的坐标对不感兴趣。我在尽量减少路线之间的变化。

显然，创建起点-目的地对有许多可能的组合，只需找到所有路线都差不多的最佳组合。

关于解决这个问题的想法？

Answer 1

如果您简单地认为问题中的“方差”是通过解决方案中最小距离和最大距离之间的差异来衡量的，那么您可以使用以下算法。选择最小距离和最大距离。然后擦除你的结构中那些在这个带之外的路线；然后执行标准的二分匹配。如果 (min,max) 是你的乐队并且 (min<min'<max'<max)，那么显然 (min',max') 只有在 (min,max) 可以解决的情况下才能解决；这导致了一种算法，您可以从更宽的频带开始并搜索仍然允许二分匹配的最窄频带。二分匹配是一个低复杂度的算法问题，因此整个解决方案应该是快速的；对于二分匹配，请参阅http://en.wikipedia。

Answer 2

不一定是最佳解决方案，但也许是一个好的开始：

1. 找到点A使得从原点到A的距离之和最小。
2. 找到点B使得从B到目的地的距离之和最小。
3. 找到从A到B的最短路径。

步骤 1 和 2 采用 O(V^3) 应用 Floyd-Warshall 算法来确定距离，然后采用 O(V) 用于“线性”搜索点A和B。第 3 步采用 O(V^2) 来确定最短路径。

Answer 3

在找到更复杂和更快的算法之前，您需要尝试完整的扫描算法。

1. 找到一种算法，以所有可能的方式置换一个集合
2. 在目的地集合上使用此算法
3. 对于每个排列计算方差

例子：

IEnumerable<Point[]> Permute(Point[] points)
{
   if(points.Length > 1)
       foreach(var point in points)
       {
          var remaining = points.Except(point).ToArray();
          foreach(var permutation in Permute(remaining))
               yield return new [] { new [] { point },  permutation}
                  .SelectMany(p => p)
                  .ToArray();
       }
   else
       yield return points;
}

Point[] SortDestinations(
         Point[] origins,
         Point[] destinations)
{
    var minVariance = int.MaxValue;
    Point[] minVariancePermutation;
    foreach(var permutation in Permute(destinations))
    {
        var variance = CalculateVariance(origins, permutation);
        if(variance < minVariance)
        {
            minVariance = variance;
            minVariancePermutation = permutation
        }
    }
    return minVariancePermutation;
}