Christofides-algoritme (met de hand)
Geplaatst op februari 1, 2021 door adminIk volg dit algoritme-voorbeeld: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [voer de beschrijving van de afbeelding hier in] [1]] [1]
Calculate minimum spanning tree T:
[! [Voer de beschrijving van de afbeelding hier in] [2]] [2]
Calculate the set of vertices O with odd degree in T
Hetzelfde als “de minimum spanning tree T “aangezien de mate van alle hoekpunten oneven is.
Form the subgraph of G using only the vertices of O
(aangezien ze allemaal oneven waren, zou dit ons de originele grafiek moeten geven) [! [ voer de afbeeldingbeschrijving hier in] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Ik weet niet zeker of ik deed dit goed ) [! [voer de beschrijving van de afbeelding hier in] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [voer hier de beschrijving van de afbeelding in] [4]] [4]
Dit klopt absoluut niet.
Wat ging er mis?
Reacties
- Opmerking: alle afbeeldingen op het bericht lijken te zijn verdwenen. Heeft de auteur toevallig de originelen?
Antwoord
In feite je hebt altijd gelijk gehad . U bent echter nog niet klaar met het Christofides-algoritme.
De volgende stap is “Bereken Euler-tour”.
In de laatste foto , je hebt een multigraph verkregen waarvan alle hoekpunten even graden hebben. Het moet dus een Euleriaans pad hebben. Laten we bijvoorbeeld het Euleriaanse pad A -> F -> A -> C -> B -> D -> E -> D -> A selecteren.
De laatste stap is “Verwijder herhaalde hoekpunten , waardoor het algoritme “s output” wordt gegeven.
Door de tweede A en de tweede D op dat pad hierboven te verwijderen, krijgen we een gewenste output, A -> F -> C -> B -> D -> E -> A . Klaar.
Merk op dat het niet erg zinvol is om het Christofides-algoritme op de gegeven grafiek toe te passen.
“Het Christofides-algoritme is een algoritme voor het vinden van benaderende oplossingen voor het handelsreizigersprobleem , in gevallen waarin de afstanden een metrische ruimte vormen (ze zijn symmetrisch en gehoorzamen de driehoeksongelijkheid “. De opgegeven afstanden voldoen niet aan de driehoeksongelijkheid, aangezien d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). Bovendien wordt de (directe) afstand tussen A en B niet gegeven, wat twijfel doet rijzen of dit überhaupt een handelsreizigersprobleem is.
Opmerkingen
- Ik ben hier nieuw in, dus bedankt voor de kanttekeningen! Ik heb een paar vragen: 1. Moet elk hoekpunt met elkaar worden verbonden om een geldige TSP te zijn? Ik bedoel, het is nog steeds mogelijk om een " TSP " route te maken, zelfs als die route ontbreekt, dus ik zou zeggen dat deze geldig is – maar Ik heb het eerder mis gehad. 2. Denkt u (of weet u) of het mogelijk is om de gewichten van sommige hoekpunten in mijn grafiek op zon manier te verhogen, dat deze voldoet aan de driehoeksongelijkheid ? Ik denk dat meer rommelig uitziende grafieken beter zijn in het weergeven van scenarios op de kaart van de echte wereld, dat ' de reden is waarom ik het heb gemaakt zoals het is.
- 1. Je kunt het als een TSP behandelen als je bijvoorbeeld aanneemt dat alle ontbrekende directe afstanden tussen steden voldoende groot of gewoon oneindig zijn. Op die manier hebben die ontbrekende afstanden geen invloed op de oplossing. Het is echter nog steeds geen metrische ruimte. 2. Om de ongelijkheid van de driehoek te gehoorzamen, kun je gewoon 10 optellen bij elke afstand die je hebt opgegeven en alle ontbrekende afstanden 20 laten zijn.
- Dit is niet waar: " In de laatste afbeelding heb je een multigraph verkregen waarvan alle hoekpunten even graden hebben. " – De hoekpunten E, D, A en F hebben een oneven graad.
- " Je hebt een multigraph ", een grafiek die meerdere randen mag hebben, dat wil zeggen randen die dezelfde eindknooppunten. Er zijn twee randen tussen D en E. Er zijn twee randen tussen A en F.
- U kunt ook het voorbeeld op Wikipedia bekijken. " Dat is geen Euleriaans pad aangezien je een hoekpunt meer dan eens bezoekt in dat pad ". Euleriaans pad gaat over het precies één keer bezoeken van elke rand . Je hebt het over het Hamiltoniaanse pad.
Geef een reactie