Christofides algoritme (i hånden)
On februar 1, 2021 by adminJeg følger dette algoritmeeksempel: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [indtast billedebeskrivelse her] [1]] [1]
Calculate minimum spanning tree T:
[! [Skriv billedbeskrivelse her] [2]] [2]
Calculate the set of vertices O with odd degree in T
Samme som “the minimum spændende træ T “, da graden af alle hjørner er ulige.
Form the subgraph of G using only the vertices of O
(da alle var ulige, skulle dette give os den originale graf) [! [ indtast billedbeskrivelse her] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Jeg er ikke sikker på, om jeg gjorde dette rigtigt ) [! [indtast billedbeskrivelse her] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [indtast billedbeskrivelse her] [4]] [4]
Dette er bestemt ikke rigtigt.
Hvad gik galt?
Kommentarer
- Bemærk: Alle billederne på indlægget ser ud til at være forsvundet. Har forfatteren tilfældigvis originalerne?
Svar
Faktisk du har været korrekt hele tiden . Du er dog ikke færdig med Christofides-algoritmen endnu.
Det næste trin er “Beregn Euler-tur”.
I det sidste billede , du har fået et multigrafi, hvis hjørner har lige grader. Så det skal have en Euleriansk sti. Lad os for eksempel vælge den Euleriske sti A -> F -> A -> C -> B -> D -> E -> D -> A.
Det sidste trin er “Fjern gentagne hjørner , der giver algoritmen “s output”.
Når vi fjerner den anden A og den anden D på den ovenstående vej, opnår vi et ønsket output, A -> F -> C -> B -> D -> E -> A Udført.
Bemærk, at det ikke er meget meningsfuldt at anvende Christofides algoritme på den givne graf.
“Christofides algoritmen er en algoritme til at finde omtrentlige løsninger til det rejsende sælgerproblem i tilfælde, hvor afstande danner et metrisk rum (de er symmetriske og adlyder trekantsuligheden “. De givne afstande overholder ikke trekantens ulighed, da d (B, D) + d (D, E) = 1 + 4 < 6 = d (B Desuden er den (direkte) afstand mellem A og B ikke givet, hvilket rejser tvivl om, hvorvidt dette overhovedet er et rejsesælgerproblem.
Kommentarer
- Jeg er ny på dette, så tak for sidebemærkningerne! Jeg har nogle spørgsmål: 1. Skal hvert toppunkt være forbundet med hinanden, for at det kan være en gyldig TSP? Jeg mener, det er stadig muligt at oprette en " TSP " rute selv med den rute mangler, så jeg vil sige, at den er gyldig – men Jeg har taget forkert før. 2. Tror du (eller ved) om det er muligt at øge vægten af nogle af hjørnerne i min graf på en sådan måde, at den adlyder trekantens ulighed ? Jeg synes, at mere rodet udseende grafer er bedre til at repræsentere virkelige verdenskortscenarier, at ' hvorfor jeg oprettede det som det er.
- 1. Du kan behandle er som en TSP, hvis du for eksempel antager, at alle manglende direkte afstande mellem byer er tilstrækkelige store eller simpelthen uendelige. På den måde vil de manglende afstande ikke påvirke løsningen. Det er dog stadig ikke et metrisk rum. 2. For at adlyde trekantens ulighed kan du bare tilføje 10 til hver afstand, du har angivet, og lade alle de manglende afstande være 20.
- Dette er ikke sandt: " I sidste billede har du fået en multigraf, hvis hjørner har lige grader. " – Hjørnerne E, D, A og F har en ulige grad.
- " Du har fået en multigraf ", en graf, der tillades at have flere kanter, det vil sige kanter, der har den samme slutknudepunkter. Der er to kanter mellem D og E. Der er to kanter mellem A og F.
- Du kan også kontrollere eksemplet på Wikipedia . " Det er ikke en Euler-sti, da du besøger et toppunkt mere end én gang i den sti ". Euleriansk sti handler om at besøge hver kant nøjagtigt en gang. Du taler om Hamilton-stien.
Skriv et svar