Problém obchodný cestujúci

No ale ja som tu nezačal debatu o pseudonáhodných generátoroch, to si tu vniesol tu ty. Pri 100 tisíc bodoch to nerozlíšiš, pretože generátor ma oveľa dlhšiu periódu. Nechápem o čom tu ty básniš dal som ti názov algoritmu, ktorý rieši 10-100 tisíc bodov, máš tu aj obrázok TSP art, ktorý je tak vyriešený. Tak čo vlastne ty tu spochybňuješ? Ja som urobil cely program a navrhol vlastnú metódu, ktorá je rýchla, tak o čom by si ma chcel poučiť?

Ja som nič nespochybňoval ani ťa nechcem poučovať. Prepáč, ak si to tak pochopil.

Tak som doprogramoval ďalšiu metódu pre použitie v programe(TSP Solver) LKH 3.0.10, zatiaľ najlepšia metóda výkon/dĺžka cesty + dorobil som modul pre TSP ART tak len niečo malé na ukážku, keďže tu sa nedajú pridávať veľké súbory

Blog článok ako si vytvoriť vlastný TSP Art v programe TSP Solver + niekoľko vytvorených TSP Artov v svg súboroch, ktoré si môžete naškálovať podľa potrieb.

https://robopol.sk/blog/tsp-art

Tak som vytvoril webovú verziu programu TSP Solver  verzia 1.0.4.  Ide zatiaľ o offline webovú aplikáciu, takže si inštalačný súbor môžete stiahnuť a vyskúšať omnoho lepšiu grafiku ako to bolo doposiaľ v tkiner aplikácii (python).

Aplikácia beží ako flusk server na PC, takže pozor na zatváranie konzoly - cmd. Viac informácii nájdete na: 

 https://robopol.sk/tsp-solver/index

Tono,

neviem, či ešte sleduješ toto vlákno, tak som celu aplikáciu urobil ako webovú a podarilo sa mi vytvoriť extrémne rýchly algoritmus, s optimálnou trasou je pri nesymetrických bodoch ma 4-5% dlhšiu trasu, pre symetrické je to 1-2%, napr. TSP Art. Metoda je schopná za 4 sekundy vyrátať 5000 bodov. Je to ohodne rýchlejšie ako najlepší algoritmus LKH 3.0.10, lenže ten nájde optimálnu trasu alebo pri veľkom počte bodov trasu do +1%, možno je na tom dokonca lepšie, nikto totiž nemá lepšiu metódu, ktorá by preverila presnosť na extrémnom počte čísiel.

pred 16 hodinami, robopol pridal:

neviem, či ešte sleduješ toto vlákno

Sledujem tvoje pokroky, ale podrobnejšie sa týmto problémom nezaoberám. V súčasnosti sa neviem na nič sústrediť.

Tak si znova o niečo pokročil. Webová aplikácia je dnes už takmer nutnosťou. Ak si chce niekto vyskúšať nejakú demo verziu, málo kto je ochotný niečo inštalovať, aj z bezpečnostných dôvodov. Kto má vážny záujem, alebo sa o problematiku hlbšie zaujíma, ten bude hľadať kontakt na autora.

Vyskúšať sa da metóda základná v javascripte https://www.poling.sk/TSP/index.html, mam offline verziu, kde využívam strojový kod cez numba a python a mam v nej sofistikovanejšie modely, napr. robopol algorithm precise, alebo LKH 3.0.10. V demo verzii offline programu, ktorý vyžaduje inštaláciu si môže napríklad ľubovoľnú fotku zmeniť na body a tie pospájať, v demo verzii je možnosť urobit 10 tisic bodov. ten výpočet trva par sekund. Mojim cielom j e poraziť ten LKH algoritmus, ktory najde najlepšiu trasu behom kratkeho času. Ja mam extrémne rýchly algoritmus ale nenajde optimalnu drahu pre velky počet bodov, zato je však neuveritelne rýchly a ešte ho škálujem, aby daval lepšie výsledky a to spustením ako multiproces, teda súčasne bude robit naraz viaceré alternatívy naraz, čo ho posunie o 1-2% k optimalnej trase. No dostať sa na optimálnu trasu bez použitia prístupov LKH je vyzva naročná.

Ak by som to chcel mat ako online web aplikaciu, to vyžaduje, aby som si zakupil server, kde budem využivať CPU, GPU, alebo RAM servera, musel by tam bežať python a podobne.

Tak už sa bližim k optimalnym riešeniam, nejake kroky pomohli teraz je to takto: 

Robopol Algoritmus

V sekcii Metódy výber "Robopol algoritmu" predstavuje vylepšený prístup najbližšieho suseda, ktorý obsahuje optimalizačné kroky na dosiahnutie vysoko efektívnych výsledkov. Algoritmus je optimalizovaný na rýchlosť vďaka využitiu knižnice Numba, ktorá kompiluje Python kód do strojového kódu. To zabezpečuje výrazne rýchlejšie vykonávanie v porovnaní s optimálnou trasou, pričom presnosť závisí od počtu a rozloženia bodov. Navyše, v porovnaní s LKH 3.0.10 Robopol algoritmus jasne vyniká rýchlosťou. Algoritmus využíva maticu vzdialeností uloženú v RAM, pričom na spracovanie veľkých datasetov vyžaduje 16 GB pamäte.  Rýchlosť tohto algoritmu je unikátna, je vhodny na velké počty bodov, kde nepotrebujeme dosiahnuť optimalnu trasu, presnosť je niekde od+1% (od optimalnej trasy) pre maly počet bodov 100 bodov a potom to rastie a pre velke inštancie bodov >50 tisic to bude niekde 6-7%. Presnosť algoritmov bola testovaná na náhodne rozmiestnených bodoch. Ak sú však body symetricky rozložené, presnosť sa môže zlepšiť až o 2–3 %.

Robopol Algoritmus - Presný

Presný Robopol algoritmus (Robopol Precise) je rozšírením štandardnej verzie a poskytuje vyššiu presnosť. Pri menších datasetoch (100–200 bodov) so špecifickými nastaveniami, ako je max_segment_size=5 a vykonanie algoritmu viac ako 50-krát, dosahuje takmer optimálne riešenia s odchýlkou približne +0,5 % od optimálnej trasy. Pri datasetoch strednej veľkosti (1 000–2 000 bodov) sa dĺžka trasy mierne zvyšuje, pričom odchýlka od optimálnej trasy je približne 1–3 %. Pri veľmi veľkých datasetoch (>10 000 bodov) je presnosť citlivejšia na nastavenia parametrov, no vo všeobecnosti je dĺžka trasy približne o 4–5 % dlhšia ako optimálna.

Presnosť algoritmov bola testovaná na náhodne rozmiestnených bodoch. Ak sú však body symetricky rozložené, presnosť sa môže zlepšiť až o 2–3 %.

Čas prvej exekúcie

Stojí za zmienku, že prvé vykonanie Robopol algoritmu aj Presného Robopol algoritmu trvá dlhšie po načítaní stránky programu. Toto oneskorenie je spôsobené tým, že knižnica Numba počas prvej exekúcie kompiluje Python kód do strojového kódu, čím optimalizuje algoritmy pre ďalšie spustenia.