Algoritm Christofides (manual)
On februarie 1, 2021 by adminUrmează acest exemplu de algoritm: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [introduceți descrierea imaginii aici] [1]] [1]
Calculate minimum spanning tree T:
[! [Introduceți descrierea imaginii aici] [2]] [2]
Calculate the set of vertices O with odd degree in T
La fel ca „the arborele de întindere minim T „, deoarece gradul tuturor vârfurilor sunt impare.
Form the subgraph of G using only the vertices of O
(deoarece toate erau ciudate, acest lucru ar trebui să ne dea graficul original) [! [ introduceți descrierea imaginii aici] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Nu sunt sigur dacă a făcut acest lucru corect ) [! [introduceți descrierea imaginii aici] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [introduceți descrierea imaginii aici] [4]] [4]
Cu siguranță nu este corect.
Ce a greșit?
Comentarii
- Notă: toate imaginile din postare par să fi dispărut. Autorul are întâmplător originalele?
Răspuns
De fapt, ați fost corect tot timpul . Cu toate acestea, nu ați finalizat încă algoritmul Christofides.
Următorul pas este „Calculați turul lui Euler”.
În ultima imagine , ați obținut un multigraf ale cărui vârfuri au grade uniforme. Deci trebuie să aibă o cale euleriană. De exemplu, să selectăm calea euleriană A -> F -> A -> C -> B -> D -> E -> D -> A.
Ultimul pas este „Eliminați vârfurile repetate , oferind algoritmului „ieșire”.
Eliminând al doilea A și al doilea D pe acea cale de mai sus, obținem o ieșire dorită, A -> F -> C -> B -> D -> E -> A . Gata.
Vă rugăm să rețineți că nu este foarte semnificativ să aplicați algoritmul Christofides pe graficul dat.
„Algoritmul Christofides este un algoritm pentru găsirea soluțiilor aproximative la problema vânzătorului călător , în cazurile în care distanțele formează un spațiu metric (acestea sunt simetrice și respectă inegalitatea triunghiului „. Distanțele date nu respectă inegalitatea triunghiului, deoarece d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). În plus, distanța (directă) dintre A și B nu este dată, ridicându-se îndoiala dacă aceasta este deloc o problemă de vânzător călător.
Comentarii
- Sunt nou în acest sens, așa că vă mulțumesc pentru notele secundare! Am câteva întrebări: 1. Fiecare vârf trebuie să fie conectat unul la altul pentru a fi un TSP valid? Adică este încă posibil să creezi o rută " TSP " chiar și cu ruta respectivă lipsă, așa că aș spune că este validă – dar Am greșit înainte. 2. Crezi (sau știi) dacă este posibil să mărești greutățile unora dintre vârfurile din graficul meu în așa fel, încât să se supună inegalității triunghiului ? Cred că graficele cu aspect mai dezordonat sunt mai bune la reprezentarea scenariilor hărții lumii reale, de aceea ' este motivul pentru care l-am creat așa cum este.
- 1. Puteți trata este ca un TSP dacă presupuneți, de exemplu, că toate distanțele directe care lipsesc între orașe sunt suficient de mari sau pur și simplu infinite. În acest fel, acele distanțe lipsă nu vor afecta soluția. Cu toate acestea, nu este încă un spațiu metric. 2. Pentru a respecta inegalitatea triunghiului, puteți adăuga 10 la fiecare distanță specificată și lăsați toate distanțele lipsă să fie 20.
- Acest lucru nu este adevărat: " În ultima imagine , ați obținut un multigraf al cărui vârfuri au grade uniforme. " – Vârfurile E, D, A și F au un grad impar.
- " Ați obținut un multigraph ", un grafic care are voie să aibă mai multe muchii, adică muchii care au același noduri de capăt. Există două margini între D și E. Există două margini între A și F.
- De asemenea, puteți verifica exemplul din Wikipedia . " Aceasta nu este o cale euleriană în timp ce vizitați un vârf de mai multe ori pe acea cale ". Calea euleriană este despre vizitarea fiecărei margini exact o dată. Vorbești despre calea hamiltoniană.
Lasă un răspuns