Sto cercando di risolvere un problema in cui ho un elenco di coordinate bidimensionali e voglio trovare il percorso più breve che li colleghi tutti.
All'inizio ho pensato che si trattasse di un caso del problema del venditore ambulante , tuttavia:
- Non è necessario tornare alla città di partenza, che credo che TSP ti voglia.
- Su questo piano bidimensionale in cui lavoriamo con la metrica distanza euclidea, vale la disuguaglianza triangolare , che il normale Gli algoritmi TSP non sono interessati, se ricordo correttamente.
- Non esiste una regola "puoi solo visitare un nodo una volta" in questo problema; il "percorso più breve" potrebbe formare un albero.
Ho quindi pensato di creare un grafico e utilizzare Prim o Kruskal's algoritmo per trovare la (lunghezza del) albero di copertura minimo '. Tuttavia, le rappresentazioni grafiche comunemente usate sono o una matrice di adiacenza, che sembra uno spreco per un grafo non orientato, o una lista di adiacenza, che è più lenta per un grafico sparse (e un grafico completamente connesso è ovviamente l'esatto opposto di sparse) .
Ho la sensazione di scartare le informazioni relative a questo specifico problema, il che risulterà nell'utilizzare più tempo e / o memoria che sarebbe necessario per risolvere il problema del percorso di connessione più breve per un grafico completamente connesso e non orientato in 2d- spazio.
Quindi:
- Quale sarebbe la rappresentazione dei dati pratici più efficiente in cui archiviare questo grafico?
- Quale sarebbe l'algoritmo più efficiente per trovare la lunghezza del percorso più breve che collega tutti i nodi?