Je dáno m měst. Některá města jsou propojena silnicemi, délka silnic je známa. Úkolem obchodního cestujícího je navštívit všechna města (práve jednou, aspoň jednou, uvažujte případ, který se Vám víc líbí) a vrátit se do výchozího města. Nalezněte takovou tůru (permutaci měst), aby délka uražené cesty byla co nejmenší.
Navrhněte a implementujte algoritmus rešící problém obchodního cestujícího. Funkčnost algoritmu ověřte na sadě dodaných testovacích příkladů (ve všech třech variantách - viz níže).
Předpokládáme, že budete implementovat nějaký iterativní algoritmus (pokud možno nějakou z pokročilých iterativních metod). Určitě vyzkoušejte a popište vliv počátečního stavu na kvalitu nalezeného řešení.
Testovací příklady jsou ohodnocené neorientované grafy zadané uzlovou maticí. Ohodnocení jedné hrany (koincidence uzel-uzel) je reprezentováno jedním znakem v matici (vlastně dvěma, neboť se jedná o neorientované grafy). Ohodnocení hrany je určeno pořadím znaků '1'-'9', 'A'-'Z', '0' znamená, že hrana mezi uzly neexistuje (viz popis níže). Hodnota hrany se spočítá
Neexistující hrany (tzn. hrany s hodnotu '0') zpracujte třemi způsoby:if (matice[a][b]=='0')
tak tam žádná hrana není /* viz popis níže */
if ((matice[a][b]>='1') && (matice[a][b]<='9'))
hodnota=matice[a][b]-'0';
else if ((matice[a][b]>='A') && (matice[a][b]<='Z'))
hodnota=matice[a][b]-'A'+10;
Příklady se jmenují a.txt, b.txt,
?.., k.txt. Protože se jedná
o docela velké soubory (až 4MB), jsou zabaleny v arj souboru tspbench.arj .
Pro odladění Vašich programů máte též k dispozici generátor grafů - původně součást diplomové práce z University of Alberta. Program hcp generuje neohodnocené grafy a hledá v nich Hamiltonovy kružnice různými algoritmy. Program hcp2tsp dává hranám náhodné ohodnocení a převádí grafy do formátu popsaného nahoře. Maximální velikost grafu je 1600 uzlů, maximální stupeň uzlu je 50. Zdrojové texty obou programů:
Program byl původně určen pro SunOS 4, nyní byl testován na
Oba programy jsou nainstalovány na CSLABu (Y:\VLSI\TSP), SunOS
4 (/usr.sw/bin) a Solaris 2 (/opt/bin).
V našem řešení použijeme variantu "navštívit všechna města práve jednou".
Jelikož je tento problém typu NPC, tak použitím exaktní metody s exponenciální složitostní skončíme u několika málo měst. Proto musíme sáhnout to nějaké heuristice. Předloženy nám byli tyto metody:
Pro řešení jsme zvolili metodu simulovaného ochlazování protože byla částečně vysvětlena na cvičení, ale osobně bych si možná zvolil podle názvu nejpřitažlivější genetické algoritmy. Metoda vyžaduje vytvořit v grafu hamiltonovu kružnici, a tu poté modifikuje. Kružnici vytvoříme tak, že vybereme počáteční bod z uzlů s největším počtem incidujících hran. Poté se přesouváme do nejbližšího dosud nepoužitého uzlu. Dojde-li k situaci, že nelze tento uzel přidat, cestu zde napojíme a nazpět až do tohoto místa obrátíme a pokračujeme z posledního uzlu. Aby nedošlo k zacyklení, pamatujeme si v kterém místě došlo k záměně a příšte použijeme jiný uzel pro záměnu. Nezdáří-li se nalézt Hamiltonovu kružnici, zvolíme jiný počáteční uzel.
Simulované ochlazování jsme implementovali podle [1]. Tento algoritmus jsme použili vícekrát (žíhání) k omezení možnosti uvíznutí v lokálním minimu.
Vliv počátečního stavu na řešení je významný, proto se vyplatí věnovat více času k nalezení prvního řešení.
Tabulka testování různých hodnot parametrůJak je videt z grafů, při volbě beta blízkému 1 a větších rozsahů počátečních a koncových teplot, je získané řešení nepatrně lepší, ale vede to k velkému prodloužení potřebného času pro výpočet. Přítomnost náhodného faktoru ve druhé fázi algoritmu vede k větší citlivosti na změnu parametrů což vede k uváznutí v různych lokálních minimech a velké rozdíly výsledků. Výsledek prvního algoritmu je velmi důležitý, protože vrátí-li výsledek blízký optimu, ulehčí tak velice výpočetně náročné druhé fázy. Zvýšením počáteční teploty vede k prodloužení výpočtu, ale jen v některých případech ke zlepšení.
Metoda simulovaného ochlazování se osvědčila, jen je třeba věnovat více času nastavení jejích parametru popřípadě je dynamicky měnit. Jinak při tvorbě algoritmu se mi vyplatilo eliminovat vliv náhody a použít sice pomalejší ale promyšlenější metodu což ve výsledku vedlo k lepšímu řešení.