Origini multiple - più destinazioni

Question

Ho una domanda di ottimizzazione. E 'solo un po' in viaggio-venditore-ish.

Diciamo che ho una serie di destinazioni e un altro relativo insieme di origini. Devo collegare ogni destinazione con una sola origine in modo che la differenza tra i percorsi è il più piccolo possibile.

non sono interessati a formare coppie di coordinate con una distanza più breve totale. Sono dopo minimizzando la variazione tra i percorsi.

Ovviamente, ci sono molte possibili combinazioni di creazione coppie origine-destinazione, è solo una questione di trovare l'ottimale quella in cui tutti i circuiti sono più-meno uguale.

Idee su un modo per affrontare questo?

Answer 1

Se si prende una visione semplice che "varianza" nel vostro problema è misurata dalla differenza tra la distanza minima e massima nella soluzione, quindi è possibile utilizzare il seguente algoritmo. Seleziona una distanza minima e una distanza massima. Poi cancellare le rotte nella struttura che sono fuori di questa banda; quindi eseguire corrispondenza bipartita standard. Se (min, max) è la tua band e (min http://en.wikipedia.org/wiki/Matching_%28graph_theory % 29 .

Answer 2

Non necessariamente la soluzione ottimale, ma forse un buon inizio:

1. Trova il punto di A in modo tale che la somma delle distanze dalle origini al A è minima.
2. Trova il punto di B in modo tale che la somma delle distanze da B per le destinazioni è minima.
3. Trova il percorso più breve da A per B .

I passi 1 e 2 take O (V ^ 3) per applicare l'algoritmo di Floyd-Warshall per determinare le distanze, e poi O (V) per il punto di ricerca "lineare" A e B . Passo 3 take O (V ^ 2) per determinare il percorso più breve.

Answer 3

Si vuole provare il pieno algoritmo di scansione prima di trovare quelli più complessi e più veloci.

1. Trova un algoritmo che permutare una raccolta tutti i modi possibili
2. Utilizza questo algoritmo sulla raccolta destinazioni
3. Per ogni permutazione calcolare la varianza

Esempio:

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;
}