Algoritmo di Christofides (a mano)
Su Febbraio 1, 2021 da adminSto seguendo questo esempio di algoritmo: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [inserisci qui la descrizione dellimmagine] [1]] [1]
Calculate minimum spanning tree T:
[! [Inserisci qui la descrizione dellimmagine] [2]] [2]
Calculate the set of vertices O with odd degree in T
Uguale a “il albero di copertura minimo T “poiché il grado di tutti i vertici è dispari.
Form the subgraph of G using only the vertices of O
(poiché tutti erano dispari, questo dovrebbe darci il grafo originale) [! [ inserisci qui la descrizione dellimmagine] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Non sono sicuro di ha fatto bene ) [! [inserisci la descrizione dellimmagine qui] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [inserisci qui la descrizione dellimmagine] [4]] [4]
Questo non è assolutamente corretto.
Che cosa è andato storto?
Commenti
- Nota: tutte le immagini sul post sembrano essere scomparse. Lautore ha gli originali?
Risposta
Infatti, hai sempre avuto ragione . Tuttavia, non hai ancora completato lalgoritmo di Christofides.
Il passaggio successivo è “Calcola tour di Eulero”.
In lultima immagine , hai ottenuto un multigrafo tutti i cui vertici hanno gradi pari. Quindi deve avere un percorso euleriano. Ad esempio, selezioniamo il percorso euleriano A -> F -> A -> C -> B -> D -> E -> D -> A.
Lultimo passaggio è “Rimuovi vertici ripetuti , dando allalgoritmo “output s”.
Rimuovendo il secondo A e il secondo D su quel percorso sopra, otteniamo un output voluto, A -> F -> C -> B -> D -> E -> A . Fatto.
Per favore nota che non è molto significativo applicare lalgoritmo di Christofides al grafico dato.
“Lalgoritmo di Christofides è un algoritmo per trovare soluzioni approssimative a il problema del venditore ambulante , nei casi in cui le distanze formano uno spazio metrico (sono simmetriche e obbediscono alla disuguaglianza triangolare “. Le distanze date non obbediscono alla disuguaglianza del triangolo, poiché d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E) Inoltre, la distanza (diretta) tra A e B non è data, sollevando il dubbio che si tratti di un problema di venditore ambulante.
Commenti
- Sono nuovo in questo, quindi grazie per le note a margine! Ho alcune domande: 1. Ogni vertice deve essere connesso tra loro per essere un TSP valido? Voglio dire che è ancora possibile creare un percorso " TSP " anche senza quel percorso, quindi direi che è valido, ma Mi sono sbagliato prima. 2. Pensi (o sai) se è possibile aumentare i pesi di alcuni dei vertici nel mio grafo in modo tale da obbedire alla disuguaglianza del triangolo ? Penso che grafici dallaspetto più disordinato rappresentino meglio scenari di mappe del mondo reale, che ' è il motivo per cui lho creato così comè.
- 1. Puoi trattarlo come un TSP se presumi, ad esempio, che tutte le distanze dirette mancanti tra le città siano sufficientemente grandi o semplicemente infinite. In questo modo, quelle distanze mancanti non influenzeranno la soluzione. Tuttavia, non è ancora uno spazio metrico. 2. Per obbedire alla disuguaglianza del triangolo, puoi semplicemente aggiungere 10 a ciascuna distanza che hai specificato e lasciare che tutte le distanze mancanti siano 20.
- Questo non è vero: " Nell ultima immagine , hai ottenuto un multigrafo tutti i cui vertici hanno gradi pari. " – I vertici E, D, A e F hanno un grado dispari.
- " Hai ottenuto un multigraph ", un grafico che può avere più bordi, cioè bordi che hanno lo stesso nodi finali. Ci sono due bordi tra D ed E. Ci sono due bordi tra A ed F.
- Puoi anche controllare lesempio su Wikipedia . " Questo non è un percorso euleriano quando visiti un vertice più di una volta in quel percorso ". Il percorso euleriano consiste nel visitare ogni bordo esattamente una volta. Stai parlando di percorso hamiltoniano.
Lascia un commento