Christofides algoritme (for hånd)
On februar 1, 2021 by adminJeg følger dette algoritmeeksemplet: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [skriv inn bildebeskrivelse her] [1]] [1]
Calculate minimum spanning tree T:
[! [Skriv inn bildebeskrivelse her] [2]] [2]
Calculate the set of vertices O with odd degree in T
Samme som «the minimum spennende tre T «da graden av alle hjørner er odde.
Form the subgraph of G using only the vertices of O
(som alle var rare, dette burde gi oss den originale grafen) [! [ skriv inn bildebeskrivelse her] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Jeg er ikke sikker på om jeg gjorde dette riktig ) [! [skriv inn bildebeskrivelse her] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [skriv inn bildebeskrivelse her] [4]] [4]
Dette er definitivt ikke riktig.
Hva gikk galt?
Kommentarer
- Merk: Alle bildene på innlegget ser ut til å ha forsvunnet. Har forfatteren tilfeldigvis originalene?
Svar
Faktisk, du har vært riktig hele tiden . Du er imidlertid ikke ferdig med Christofides-algoritmen ennå.
Neste trinn er «Beregn Euler-tur».
I det siste bildet , har du skaffet et multigrafi, hvis hjørner har jevne grader. Så det må ha en Euleriansk sti. La oss for eksempel velge Eulerian-banen A -> F -> A -> C -> B -> D -> E -> D -> A.
Det siste trinnet er «Fjern gjentatte hjørner , som gir algoritmen «s output».
Når vi fjerner andre A og andre D på den ovennevnte banen, får vi en ønsket utgang, A -> F -> C -> B -> D -> E -> A Ferdig.
Vær oppmerksom på at det ikke er veldig meningsfylt å bruke Christofides-algoritmen på den gitte grafen.
«Christofides-algoritmen er en algoritme for å finne omtrentlige løsninger på det omreisende selgerproblemet , i tilfeller der avstandene danner et metrisk rom (de er symmetriske og følger trekantsulikheten «. De gitte avstandene overholder ikke ulikheten i trekanten, siden d (B, D) + d (D, E) = 1 + 4 < 6 = d (B Videre blir ikke den (direkte) avstanden mellom A og B gitt, noe som gir tvil om dette i det hele tatt er et reisende selgerproblem.
Kommentarer
- Jeg er ny på dette, så takk for sidene! Jeg har noen spørsmål: 1. Må hver toppunkt være koblet til hverandre for å være en gyldig TSP? Jeg mener det er fremdeles mulig å opprette en " TSP " rute selv med at ruten mangler, så jeg vil si at den er gyldig – men Jeg har tatt feil før. 2. Tror du (eller vet) om det er mulig å øke vektene til noen av toppunktene i grafen min på en slik måte, slik at den adlyder ulikheten i trekanten ? Jeg tror mer rotete grafer er bedre til å representere virkelige verdenskart-scenarier, at ' hvorfor jeg opprettet det slik det er.
- 1. Du kan behandle er som en TSP hvis du for eksempel antar at alle manglende direkte avstander mellom byene er tilstrekkelig store eller bare uendelige. På den måten vil de manglende avstandene ikke påvirke løsningen. Imidlertid er det fortsatt ikke et metrisk område. 2. For å adlyde ulikheten i trekanten, kan du bare legge til 10 til hver avstand du har spesifisert og la alle de manglende avstandene være 20.
- Dette stemmer ikke: " I siste bilde , har du fått et multigrafi som alle hjørnene har jevne grader. " – Hjørnene E, D, A og F har en merkelig grad.
- " Du har fått en multigraph ", en graf som tillates å ha flere kanter, det vil si kanter som har samme sluttnoder. Det er to kanter mellom D og E. Det er to kanter mellom A og F.
- Du kan også sjekke eksemplet på Wikipedia . " Det er ikke en Eulerian-bane når du besøker et toppunkt mer enn en gang i den banen ". Eulerian sti handler om å besøke hver kant nøyaktig en gang. Du snakker om Hamilton-stien.
Legg igjen en kommentar