Riduzione al minimo della media euclidea quadratica a coppia

Stai cercando una corrispondenza perfetta peso minimo in un grafo non orientato ponderato completo. I tuoi punti 2n sono i vertici e ogni coppia di vertici ha un bordo non orientato tra loro con un peso uguale alla distanza euclidea tra i punti.

L'algoritmo Blossom Algorithm può risolvere questo problema. Secondo (Kolmogorov, 2009) collegato dalla pagina di Wikipedia, il limite di complessità più noto è O (| V || E | + | V | log | V |), che nel tuo caso sarebbe O (n ^ 3) perché è un grafico completo.

Riferimento: Kolmogorov, 2009. Blossom V: una nuova implementazione di un algoritmo di matching perfetto a costo minimo. Calcolo matematico di programmazione , vol. 1, numero 1, pp. 43-67.

1. Falla funzionare: prova ogni possibile abbinamento con il backtracking a forza bruta (implementazione ricorsiva).
2. Assicurati di non testare lo stesso abbinamento più di una volta (ci sono alcune trappole lì). E prova a derivare la complessità dei tuoi algoritmi. Penso che sia 2k (n!).

Ora puoi pensare a soluzioni più intelligenti e hai un'implementazione di riferimento per verificare la correttezza e il miglioramento della velocità.

1. Confrontando la tua soluzione migliore finora, puoi saltare intere parti del tuo spazio di ricerca (= potatura). Per esempio. Se hai un abbinamento incompleto e la somma delle distanze quadrate è già superiore al tuo miglior punteggio, non cercare di competere con questo abbinamento. Con alcuni calcoli preliminari (come trovare i vicini più vicini per ogni punto) si modifica l'ordine di ricerca in modo da trovare una soluzione ragionevole in anticipo. Ciò aumenterà drasticamente l'eliminazione e accelera l'implementazione.

2. Oppure prova qualcosa di completamente diverso: inizia con qualsiasi abbinamento completo, quindi cerca le ottimizzazioni locali: se puoi migliorare 2 coppie (AB e CD) commutando i loro partner (AC e BD o AD & BC), quindi hai migliorato anche la soluzione totale. Lo ripeti, finché non riesci più a trovare una coppia o una coppia di questo tipo. (MODIFICA: in realtà, questo approccio non è garantito per trovare la soluzione migliore. Può essere "bloccato" in un minimo locale).