Algoritmo per minimizzare la variazione della distanza tra le coordinate 2D

2

Ho cercato un algoritmo che ottimizzasse la distanza tra 2 liste di coordinate e scegliamo quale coordinata dovrebbe andare insieme.

Dire che ho Elenco 1:

205|200
220|210
200|220
200|180

Elenco 2:

210|200
207|190
230|200
234|190

Distanza calcolata tra le coordinate:

205|200 to 210|200 == 5.00
205|200 to 207|190 == 10.20
205|200 to 230|200 == 25.00
205|200 to 234|190 == 30.68

220|210 to 210|200 == 14.14
220|210 to 207|190 == 23.85
220|210 to 230|200 == 14.14
220|210 to 234|190 == 24.41

200|220 to 210|200 == 22.36
200|220 to 207|190 == 30.81
200|220 to 230|200 == 36.06
200|220 to 234|190 == 45.34

200|180 to 210|200 == 22.36
200|180 to 207|190 == 12.21
200|180 to 230|200 == 36.06
200|180 to 234|190 == 35.44

Questo Algoritmo avrebbe scelto:

205|200 to 230|200 == 25.00
220|210 to 207|190 == 23.85
200|220 to 210|200 == 22.36
200|180 to 234|190 == 35.44

L'Algoritmo selezionerebbe questi numeri come se fossero il gruppo che avrebbe la minima differenza tra la distanza. Condizioni:

  1. Una coordinata può essere utilizzata solo da ciascuna lista
  2. Se List 1 o List2 è più grande di sempre, usa una volta sola ogni coordinata, ma cerca di ottenere la varianza di distanza più piccola e non fa nulla con le coordinate inutilizzate.

Se hai bisogno di ulteriori chiarimenti, per favore chiedi.

P.S. Ho esaminato l'algoritmo ungherese e sembra che farà il lavoro, ma non esattamente come mi aspettavo. L'algoritmo ungherese cercherà solo la distanza minima tra tutte le coordinate, il che può significare la varianza più piccola, ma non tutte le volte che la varianza è più importante, quindi l'ottimizzazione della distanza minima.

Informazioni aggiuntive

Avrò un array di List1, List2 e quindi le distanze:

Distance[List1_item_0][List2_item_0] = 5;
Distance[List1_item_0][List2_item_1] = 10.20;
Distance[List1_item_0][List2_item_2] = 25.00;
Distance[List1_item_0][List2_item_3] = 30.68;

Distance[List1_item_1][List2_item_0] = 14.14;
Distance[List1_item_1][List2_item_1] = 23.85;
Distance[List1_item_1][List2_item_2] = 14.14;
Distance[List1_item_1][List2_item_3] = 24.41;

Distance[List1_item_2][List2_item_0] = 22.36;
Distance[List1_item_2][List2_item_1] = 30.81;
Distance[List1_item_2][List2_item_2] = 36.06;
Distance[List1_item_2][List2_item_3] = 45.34;

Distance[List1_item_3][List2_item_0] = 22.36;
Distance[List1_item_3][List2_item_1] = 12.21;
Distance[List1_item_3][List2_item_2] = 36.06;
Distance[List1_item_3][List2_item_3] = 35.44;

Dalla Distanza ['List1_item_ #] Avrei bisogno di scegliere una distanza. Una volta selezionata la distanza, [List2_item_ #] NON può essere scelto da un altro [List1_item_ #]. Le distanze scelte per ogni elemento [List1_item_ #] dovrebbero essere selezionate in modo che la varianza tra tutte queste sia minima. Quindi la distanza per ogni [List1_item_ #] dovrebbe essere il più vicino possibile l'uno all'altro senza riutilizzare un [List2_item_ #] più di una volta.

    
posta Steven10172 25.05.2012 - 22:06
fonte

2 risposte

2

Sembra un problema Programmazione dinamica . Sembra che ci siano coppie N * M possibili. Il problema è che, dati i punti A1 e A2, e B1 e B2, la domanda se le coppie (A1, B1) + (A2, B2) siano migliori di (A1, B2) + (A2, B1) dipende dall'aggiunta di punti A3 e B3.

Sospetto quindi che qualsiasi soluzione analitica sarà O (exp (N * M)), cioè veramente cattivo.

    
risposta data 28.05.2012 - 23:58
fonte
0

Per gli elenchi di piccole dimensioni, puoi provare a eseguire una ricerca completa, applicando un algoritmo branch-and-bound .

Se le dimensioni delle liste non sono più applicabili poiché il tempo di esecuzione supera il tempo disponibile, è necessario un algoritmo di ottimizzazione discreto come la ricottura simulata o la ricerca tabu per trovare una soluzione buona (forse non la migliore a livello globale). Ecco un libro online gratuito che si occupa di molti algoritmi di ottimizzazione globale, spero che questo aiuti:

link

    
risposta data 28.05.2012 - 14:23
fonte

Leggi altre domande sui tag