Ho un set di punti e una funzione di distanza applicabile a ciascuna coppia di punti. Vorrei collegare TUTTI i punti insieme, con la distanza totale minima. Sai di un algoritmo esistente che potrei usare per quello?Algoritmo per connettere tutti i punti con la distanza totale minima
Ogni punto può essere collegato a diversi punti, quindi questo non è il solito "venditore itinerario" problema :)
Grazie!
Quello che vuoi è un .
I due algoritmi più comuni per generare uno sono:
L'algoritmo che si sta cercando è chiamato spanning tree minimo. È utile trovare il costo minimo per una rete idrica, telefonica o elettrica. C'è l'algoritmo di Prim o l'algoritmo di Kruskal. L'algoritmo di IMO Prim è un po 'più facile da capire.
qui http://en.wikipedia.org/wiki/Minimum_spanning_tree è possibile trovare ulteriori informazioni sul spanning tree minimo, in modo da poter adattare alle risolvi il tuo problema
Date un'occhiata al algoritmo di Dijkstra:
l'algoritmo di Dijkstra, ideato per Olandese informatico Edsger Dijkstra nel 1956 e pubblicato nel 1959, è un algoritmo di ricerca grafico che risolve il single-source problema del cammino minimo per un grafico con costi di percorso del bordo non negativi, producendo un albero del percorso più breve. Questo algoritmo viene spesso utilizzato nel routing e come subroutine in altri algoritmi di grafi.
http://en.wikipedia.org/wiki/Dijkstra 's_algorithm
Come altri hanno detto, il minimum spanning tree (MST) vi permetterà di formare un sub-grafico distanza minima che collega tutti i punti.
Per prima cosa è necessario creare un grafico per il set di dati. Per creare in modo efficiente un grafico non orientato, è possibile calcolare lo Delaunay triangulation del set di punti. La conversione dalla triangolazione al grafico è quindi abbastanza letterale - qualsiasi angolo nella triangolazione è anche un bordo nel grafico, ponderato dalla lunghezza del bordo di triangolazione.
Esistono algoritmi efficienti sia per le fasi MST (Prim's/Kruskal's O(E*log(V))) che per la triangolazione Delaunay (Divide and Conquer O(V*log(V))), quindi sono possibili approcci complessivi efficienti.
Spero che questo aiuti.
Questo potrebbe essere interpretato come un problema di spanning-weight minimo. Non sono sicuro che sia il modo migliore per affrontarlo ma è un modo. – biziclop
Se la metrica di distanza segue D (x, z) <= D (x, y) + D (y, z) per ogni tre punti x, y & z, quindi collegando fondamentalmente ogni punto di coppia si ottiene una distanza minima totale. Penso che tu abbia bisogno di affinare la tua domanda un po '. – ElKamina
La metrica della distanza potrebbe essere la somma di tutte le lunghezze delle connessioni. –