多重起源 - 多個目的地

Question

我有一個優化問題。這只是有點旅行推銷員。

可以說我有一組目的地和另一組相對應的原點。 我需要將每個目的地與一個原點鏈接，以便路線之間的差異儘可能小。

我對用最短距離形成一對座標不感興趣。我最小化了路線之間的差異。

很顯然，創建起點到終點對的組合很多，只是找到所有路線都不太平等的最佳組合。

想法解決這個問題？

Answer 1

如果您簡單看待問題中的「差異」是通過差異來衡量的e在解決方案中最小距離和最大距離之間，則可以使用以下算法。選擇最小距離和最大距離。然後在你的結構中清除這個樂隊之外的路線;然後執行標準二分配匹配。如果（最小，最大）是你的帶寬，並且（min，max）最大值只有在（min，max）可以求解的情況下才能求解;這會導致一種算法，然後您可以從更寬的頻帶開始搜索儘可能最窄的頻段，但仍然可以採用雙頻匹配。二部匹配是一個低複雜度的算法問題，所以整個解決方案應該是快速的;二分配匹配，見http://en.wikipedia.org/wiki/Matching_%28graph_theory%29。

Answer 2

不一定是最佳的解決方案，但也許一個良好的開端：

1. 找到點一個這樣的距離從起源到一個之和是最小的。
2. 找到點B使得從目的地到目的地的距離總和最小。
3. 找到從A到B的最短路徑。

步驟1和2取ø（V^3）用於施加Floyd-Warshall算法，以確定的距離，然後O（V）爲 「線性」 搜索點甲和乙。步驟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; 
}