Несколько источников - несколько пунктов назначения - PullRequest
Новая
       6

Несколько источников - несколько пунктов назначения

2 голосов
/ 17 января 2010

У меня есть вопрос по оптимизации. Это всего лишь путешествующий продавец.

Допустим, у меня есть набор пунктов назначения и другой соответствующий набор источников. Мне нужно связать каждый пункт назначения с одним источником, чтобы различия между маршрутами были как можно меньше.

Меня не интересует формирование пар координат с полным кратчайшим расстоянием. Я после минимизации различий между маршрутами.

Очевидно, что существует множество возможных комбинаций создания пар источник-пункт назначения, просто нужно найти оптимальную, где все маршруты более-менее равны.

Идеи о том, как справиться с этим?

Ответы [ 3 ]

1 голос
/ 17 января 2010

Если вы просто видите, что «дисперсия» в вашей задаче измеряется разницей между наименьшим и наибольшим расстоянием в решении, вы можете использовать следующий алгоритм. Выберите минимальное расстояние и максимальное расстояние. Затем сотрите те маршруты в вашей структуре, которые находятся вне этой полосы; затем выполните стандартное двустороннее сопоставление. Если (min, max) ваша полоса и (min http://en.wikipedia.org/wiki/Matching_%28graph_theory%29.

0 голосов
/ 17 января 2010

Вы захотите попробовать алгоритм полного сканирования, прежде чем найдете более сложные и быстрые.

  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;
}
0 голосов
/ 17 января 2010

Не обязательно оптимальное решение, но, возможно, хорошее начало:

  1. Найдите точку A так, чтобы сумма расстояний от начала координат до A была минимальной.
  2. Найдите точку B так, чтобы сумма расстояний от B до пунктов назначения была минимальной.
  3. Найдите кратчайший путь от A до B .

Шаги 1 и 2 берут O (V ^ 3) для применения алгоритма Флойда-Варшалла для определения расстояний, а затем O (V) для «линейной» точки поиска A и B . Шаг 3 возьмите O (V ^ 2) для определения кратчайшего пути.

...