Christofidův algoritmus (ručně)
On 1 února, 2021 by adminSleduji tento příklad algoritmu: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [zde zadejte popis obrázku] [1]] [1]
Calculate minimum spanning tree T:
[! [Zde zadejte popis obrázku] [2]] [2]
Calculate the set of vertices O with odd degree in T
Stejné jako „the minimum spanning tree T „as the degree of all vertices are odd.
Form the subgraph of G using only the vertices of O
(protože všechny byly liché, měl by nám poskytnout původní graf) [! [ zde zadejte popis obrázku] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( nejsem si jistý, jestli udělal to správně ) [! [zde zadejte popis obrázku] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [zde zadejte popis obrázku] [4]] [4]
To rozhodně není správné.
Co se stalo?
Komentáře
- Poznámka: Zdá se, že všechny obrázky v příspěvku zmizely. Má autor náhodou originály?
Odpověď
Ve skutečnosti po celou dobu jste měli pravdu . Algoritmus Christofides jste však ještě nedokončili.
Dalším krokem je „Vypočítat Eulerovu prohlídku“.
Na posledním obrázku , získali jste multigraf, jehož všechny vrcholy mají sudé stupně. Musí to tedy mít euleriánskou cestu. Vyberte například euleriánskou cestu A -> F -> A -> C -> B -> D -> E -> D -> A.
Posledním krokem je „Odstranit opakované vrcholy , což dává algoritmu „výstup“.
Odstraněním druhého A a druhého D na výše uvedené cestě získáme požadovaný výstup, A -> F -> C -> B -> D -> E -> A . Hotovo.
Upozorňujeme, že použití algoritmu Christofides v daném grafu není příliš smysluplné.
„Algoritmus Christofides je algoritmus pro nalezení přibližného řešení problém obchodního cestujícího v případech, kdy vzdálenosti tvoří metrický prostor (jsou symetrické a dodržují nerovnost trojúhelníku „. Dané vzdálenosti nedodržují nerovnost trojúhelníku, protože d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). Navíc není uvedena (přímá) vzdálenost mezi A a B, což vyvolává pochybnosti, zda se jedná o problém obchodního cestujícího.
Komentáře
- Jsem v tom nový, takže děkuji za poznámky! Mám několik otázek: 1. Musí být každý vrchol navzájem propojen, aby byl platným TSP? Myslím tím, že je stále možné vytvořit " TSP " trasu, i když tato trasa chybí, takže bych řekl, že je platná – ale Předtím jsem se mýlil. 2. Myslíte si (nebo víte), zda je možné zvýšit váhu některých vrcholů v mém grafu takovým způsobem, aby vyhověl nerovnosti trojúhelníku ? Myslím, že více chaoticky vypadající grafy lépe reprezentují scénáře map reálného světa, a proto jsem jej ' vytvořil tak, jak je.
- Můžete zacházet jako s TSP, pokud předpokládáte, že například všechny chybějící přímé vzdálenosti mezi městy jsou dostatečně velké nebo jednoduše nekonečné. Tímto způsobem nebudou mít chybějící vzdálenosti vliv na řešení. Nejedná se však stále o metrický prostor. 2. Chcete-li dodržet nerovnost trojúhelníku, stačí přidat 10 ke každé zadané vzdálenosti a nechat všechny chybějící vzdálenosti rovné 20.
- To není pravda: " Na posledním obrázku jste získali multigraf, jehož všechny vrcholy mají sudé stupně. " – Vrcholy E, D, A a F mají lichý stupeň.
- " Získali jste multigraph ", graf, který může mít více hran, tj. hran, které mají stejné koncové uzly. Mezi D a E jsou dvě hrany. Mezi A a F jsou dvě hrany.
- Příklad můžete zkontrolovat na Wikipedii . " To není euleriánská cesta, protože v této cestě navštívíte vrchol více než jednou ". Eulerianská cesta je o návštěvě každé hrany přesně jednou. Mluvíte o Hamiltonovské cestě.
Napsat komentář