Úvod
Autor algoritmu: RobopolPredstavujem Vám nový veľmi presný algoritmus na riešenie TSP problému. Algoritmus je komplexný a pomerne dlhý. Poskytuje optimálne cesty, resp. blízko optimálnej cesty/dráhy do zhruba cca 100 bodov. Nastavením (parametrami môžeme zrýchliť výsledný čas avšak na úkor toho, že riešenie bude menej presne. Do 100 bodov však nájde optimálne, resp. blízko optimálneho riešenia za relatívne dobrý čas. Nie je to konkurencia voči Kernighan-Lin algoritmu, avšak pre malý počet bodov môže poskytnúť kratšiu dráhu (v niektorých prípadoch) voči Concorde, či Kernighan-Lin algoritmu.
Hrubý princíp metódy
Na obr. č.1 je ukážka toho ako algoritmus pracuje. Začne s trojicou bodov a postupne pridáva najbližšie body, tak, že pre optimalizuje trasu. Algoritmus nie je open source. Z tohto dôvodu presný princíp nebude zverejnený.
Obr. 1 Princíp metódy algoritmu postupného pridávania bodov.
Demonštračný "exe" program
program je vytvorený v Pythone 3.11- download demonštračného programu - LINK (35.5 MB)
Poznámka: pre stiahnutie musíte dať povoliť ant. ochrane stiahnuť a spustiť súbor. Po chvíľke sa program načíta, zhruba 10 sec. Zadajte počet bodov (do zhruba cca. 50) pretože parameter 1 je nastavený na 15 bodov a parameter 2 na hodnotu 0.65, 65%. V demonštračnom programe nie je možnosť meniť parametre pre presnosť ani rýchlosť algoritmu. Pre pokračovania spájania ďalších bodov musíte VŽDY zavrieť aktuálny graf.
Ukážka z pripravovaného programu pre riešenie TSP problému.
