Trovare il percorso più breve in un grafo non connesso completamente connesso

1

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?
posta Qqwy 26.03.2017 - 13:02
fonte

1 risposta

1

Per memorizzare il grafico completo usa una matrice di adiacenza perché hai bisogno di memorizzare la distanza tra ogni due nodi [n * (n + 1) / 2 spigoli per n nodi]. Dovresti inserire bordi n * (n + 1) se usi un elenco di adiacenze.

Per memorizzare la spanning tree minima (MST) usa un elenco di adiacenze dato che devi solo archiviare solo i bordi n-1 per un grafico di n nodi

Per trovare l'MST stai meglio con l'algoritmo di Prim. Funziona in O (E log (V)) se utilizzato con l'elenco di adiacenze. [E spigoli, nodi V]

L'algoritmo di Kruskal ha bisogno di ordinare prima tutti i bordi che in questo caso non sono una buona idea perché hai molti bordi.

    
risposta data 26.03.2017 - 13:38
fonte

Leggi altre domande sui tag