Christofides algoritm (för hand)
On februari 1, 2021 by adminJag följer detta algoritmsexempel: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [skriv in bildbeskrivning här] [1]] [1]
Calculate minimum spanning tree T:
[! [Skriv in bildbeskrivning här] [2]] [2]
Calculate the set of vertices O with odd degree in T
Samma som ”the minsta spännande träd T ”eftersom graden på alla hörn är udda.
Form the subgraph of G using only the vertices of O
(eftersom alla var udda bör detta ge oss den ursprungliga grafen) [! [ ange bildbeskrivning här] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Jag är inte säker på om jag gjorde detta rätt ) [! [skriv in bildbeskrivning här] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [skriv in bildbeskrivning här] [4]] [4]
Detta är definitivt inte rätt.
Vad gick fel?
Kommentarer
- Obs! Alla bilder på inlägget verkar ha försvunnit. Har författaren råkar ha originalen?
Svar
Faktum är att du har haft rätt hela tiden . Du har dock inte avslutat Christofides-algoritmen ännu.
Nästa steg är ”Beräkna Euler-turné”.
I den sista bilden , du har fått en multigraph vars vars hörn har jämna grader. Så det måste ha en Euleriansk väg. Låt oss till exempel välja Eulerian-vägen A -> F -> A -> C -> B -> D -> E -> D -> A.
Det sista steget är ”Ta bort upprepade hörn , som ger algoritmen ”s output”.
Att ta bort den andra A och den andra D på den ovanför banan, vi får en önskad output, A -> F -> C -> B -> D -> E -> A . Klar.
Observera att det är inte så meningsfullt att tillämpa Christofides-algoritmen på den angivna grafen.
”Christofides-algoritmen är en algoritm för att hitta ungefärliga lösningar på problemet för resande säljare , i fall där avstånden bildar ett metriskt utrymme (de är symmetriska och följer triangelns ojämlikhet ”. De angivna avstånden följer inte triangelns ojämlikhet, eftersom d (B, D) + d (D, E) = 1 + 4 < 6 = d (B Dessutom ges inte (direkt) avståndet mellan A och B, vilket väcker tvivel om detta alls är ett resande säljproblem.
Kommentarer
- Jag är ny på det här, så tack för sidoteckningarna! Jag fick några frågor: 1. Måste varje toppunkt vara ansluten till varandra för att det ska vara en giltig TSP? Jag menar att det fortfarande är möjligt att skapa en " TSP " rutt även om den rutten saknas, så jag skulle säga att den är giltig – men Jag har haft fel tidigare. 2. Tror du (eller vet du) om det är möjligt att öka vikterna på några av hörnpunkterna i min graf på ett sådant sätt att den följer ojämlikheten i triangeln ? Jag tycker att mer röriga diagram är bättre på att representera verkliga världsscenarier, att ' varför jag skapade det som det är.
- 1. Du kan behandla är som en TSP om du antar att till exempel alla saknade direkta avstånd mellan städer är tillräckligt stora eller helt enkelt oändliga. På det sättet påverkar inte de saknade avstånden lösningen. Det är emellertid inte ett metrisk utrymme fortfarande. 2. För att följa ojämlikheten i triangeln kan du bara lägga till 10 till varje avstånd du har angett och låta alla saknade avstånd vara 20.
- Detta är inte sant: " I sista bilden har du fått en multigrafik vars alla hörn har jämna grader. " – Hörnpunkterna E, D, A och F har en udda grad.
- " Du har fått en multigraph ", ett diagram som får ha flera kanter, det vill säga kanter som har samma slutnoder. Det finns två kanter mellan D och E. Det finns två kanter mellan A och F.
- Du kan också kontrollera exemplet på Wikipedia . " Det är inte en Eulerian-sökväg när du besöker ett toppunkt mer än en gång i den sökvägen ". Eulerian-vägen handlar om att besöka varje kant exakt en gång. Du pratar om Hamiltonian-vägen.
Lämna ett svar