2

最適化に関する質問があります。ちょっとだけ巡回セールスマンっぽいです。

目的地のセットと、対応する別の出発地のセットがあるとします。ルート間の変動ができるだけ小さくなるように、各目的地を 1 つの出発地にリンクする必要があります。

合計最短距離で座標のペアを形成することに興味はありません。ルート間の変動を最小限に抑えた後です。

明らかに、出発地と目的地のペアを作成するための可能な組み合わせは多数あります。それは、すべてのルートが多かれ少なかれ等しい最適なものを見つけることの問題です。

それに取り組む方法についてのアイデアはありますか？

4

3 に答える 3

1

問題の「分散」が解の最小距離と最大距離の差によって測定されるという単純な見方をすると、次のアルゴリズムを使用できます。最小距離と最大距離を選択します。次に、このバンドの外にある構造内のルートを消去します。次に、標準の二部マッチングを実行します。(min,max) がバンドで (min<min'<max'<max) の場合、明らかに (min',max') は (min,max) が解ける場合にのみ解かれます。これは、より広い帯域から始めて、二部一致を許容する最も狭い帯域を検索するアルゴリズムにつながります。二部マッチングは複雑度の低いアルゴリズムの問​​題であるため、ソリューション全体が高速である必要があります。二部一致については、http://en.wikipedia を参照してください。

于 2010-01-17T15:15:20.827 に答える
0

より複雑で高速なアルゴリズムを見つける前に、フル スキャン アルゴリズムを試してみることをお勧めします。

  1. 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;
}
于 2010-01-17T14:19:42.343 に答える
0

必ずしも最適なソリューションではありませんが、おそらく良いスタートです:

  1. 原点からAまでの距離の合計が最小になるような点Aを見つけます。
  2. Bから目的地までの距離の合計が最小になるような点Bを見つけます。
  3. AからBへの最短経路を見つけます。

ステップ 1 と 2 では、距離を決定するために Floyd-Warshall アルゴリズムを適用するために O(V^3) を使用し、次に「線形」検索ポイントAとBに O(V) を使用します。ステップ 3 では、最短経路を決定するために O(V^2) を使用します。

于 2010-01-17T13:19:56.743 に答える