Christofides algoritmus (kézzel)
On február 1, 2021 by adminEzt az algoritmus-példát követem: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [ide írja be a kép leírását] [1]] [1]
Calculate minimum spanning tree T:
[! [Ide írja be a kép leírását] [2]] [2]
Calculate the set of vertices O with odd degree in T
Ugyanaz, mint “a minimális átfedő fa T “, mivel az összes csúcs foka páratlan.
Form the subgraph of G using only the vertices of O
(mint minden furcsa volt, ez megadja nekünk az eredeti gráfot) [! [ írja ide a kép leírását] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Nem vagyok biztos benne, hogy ezt jól tette ) [! [írja be ide a kép leírását] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [ide írja be a kép leírását] [4]] [4]
Ez egyáltalán nem helyes.
Mi lett a baj?
Megjegyzések
- Megjegyzés: Úgy tűnik, hogy a bejegyzés összes képe eltűnt. Előfordul, hogy a szerzőnél vannak eredetik?
Válasz
Valójában végig helyes voltál . Azonban még nem fejezte be a Christofides algoritmust.
A következő lépés az “Euler-túra kiszámítása”.
az utolsó képen , egy multigráfot kapott, amelynek minden csúcsa páros fokú. Tehát euleri útnak kell lennie. Válasszuk ki például az Eulerius-utat A -> F -> A -> C -> B -> D -> E -> D -> A.
Az utolsó lépés az “Ismételt csúcsok eltávolítása” , megadva az algoritmus “kimenetét”.
Eltávolítva a második A-t és a második D-t a fenti útvonalról, kapunk egy kívánt kimenetet, A -> F -> C -> B -> D -> E -> A Kész.
Felhívjuk figyelmét, hogy nem túl értelmes a Christofides algoritmust alkalmazni az adott grafikonon.
“A Christofides algoritmus egy algoritmus a az utazó eladó problémája , olyan esetekben, amikor a távolságok metrikus teret képeznek (szimmetrikusak és engedelmeskednek a háromszög egyenlőtlenségnek “. A megadott távolságok nem engedelmeskednek a háromszög egyenlőtlenségének, mivel d (B, D) + d (D, E) = 1 + 4 < 6 = d (B Ezenkívül az A és B közötti (közvetlen) távolság nincs megadva, ami kétségessé teszi, hogy ez egyáltalán egy utazó eladó problémája-e.
Megjegyzések
- Új vagyok ebben, ezért köszönöm a mellékjegyzeteket! Van néhány kérdésem: 1. Minden csúcsot össze kell kapcsolni egymással, hogy érvényes TSP legyen? Úgy értem, még mindig lehetséges létrehozni egy " TSP " útvonalat, még akkor is, ha ez az útvonal hiányzik, tehát azt mondanám, hogy érvényes – de Korábban tévedtem. 2. Gondolod (vagy tudod), hogy lehetséges-e oly módon növelni a gráfom egyes csúcsainak súlyát, hogy azok engedelmeskedjenek a háromszög egyenlőtlenségének ? Úgy gondolom, hogy a rendetlenebb megjelenésű grafikonok jobban reprezentálják a valós világ térképi forgatókönyveit, ezért ' ezért hoztam létre olyannak, amilyen.
- 1. Akkor kezelheti TSP-ként, ha például azt feltételezi, hogy a városok közötti hiányzó közvetlen távolságok elég nagyok vagy egyszerűen végtelenek. Ily módon a hiányzó távolságok nem befolyásolják a megoldást. Ez azonban még mindig nem metrikus tér. 2. A háromszög egyenlőtlenségének betartásához egyszerűen adjon hozzá 10-et minden megadott távolsághoz, és hagyja, hogy az összes hiányzó távolság 20 legyen.
- Ez nem igaz: " Az utolsó képen egy multigráfot kapott, amelynek minden csúcsa páros fokú. " – Az E, D, A és F csúcsok páratlan fokúak.
- " multigrafikus ", egy olyan grafikon, amelynek megengedett több éle, vagyis ugyanazokkal az élekkel vég csomópontok. Két él van D és E között. Két él van A és F. között.
- A példát a Wikipédián is ellenőrizheti . " Ez nem egy euleri útvonal, amikor többször is meglátogat egy csúcsot ezen az útvonalon ". Az euleri út arról szól, hogy minden élt pontosan egyszer keressen fel. Hamilton-ösvényről beszélsz.
Vélemény, hozzászólás?