Problém obchodný cestujúci

Našiel som nejakú aplikáciu ale len na aple store Concorde TSP. Nejaké video :

Exaktne riešenie to nemôže byť, možno existujú nejaké matematické práce na túto tému ako zúžiť výber, čo samozrejme sú práve tie optimalizačné heuristiky.

nie,   je to exaktny algoritmus.   Ved to pisu.  A mozes si stiahnut zdrojaky 
https://www.math.uwaterloo.ca/tsp/concorde/
 

načo by som sťahoval divne zdrojaky, keď to je na githube v pythone.

https://github.com/jvkersch/pyconcorde

No a divne je to, že sa o tom dozvedám až teraz :)

divne zdrojaky od autorov ? :) No, nic. 
Lenze takto mas nieco uplne ine,  stiahnes si wraper, ktory zavola ten divny kod, ktory nechces stahovat :) a bez zdrojakov.

nie ja som myslel, že tam je rovno kód algoritmu v pythone preto som to pozeral, ale ten zdroj na python mi hlási chyby. Ak pochopím metódu nemusím nič kopčiť zo zdrojov roku 2001 a podobne dátumy. Ja sa chcem pozrieť na kód toho programu.

V podstate to dôležité je, že našli exaktný algoritmus na obchodného cestujúceho už dávno a my sme tu debatovali úplne zbytočne. zaujímavé je aj to, že informácie na nete sú sporadické a program concorde TSP je z roku 2003. To je dosť smutné, že v podstate rýchla exaktná metóda má jeden programik z roku 2003, čo som si aj nainštaloval.

Miesto toho sme sa tu bavili o chrobákoch (a pod) ako našli "riešenie obchodného cestujúceho v roku 2019". Smutne

Nie je teda dôvod ďalej riešiť tieto veci, ale modul v pythone by sa zišiel. Pretože podľa mňa to ani neexistuje ako nástroj. 

zadal som TSP python a vyzera ze nie je problem nejake najst.  Ale stale je sanca ze sa podari vylepsit algoritmus, len to asi chce ovela viac matematiky.

nejaké, doležíte je funkčne a dobre kódy, ja som skúšal nejaké, nič z toho mi nešlo.  mam iba hrubú predstavu o čo ide (lineárne programovanie). Ak si našiel niečo zaujímavé písané v pythone, algoritmus na metódu, tak pošli odkaz.

Inak len pre zábavu v minulosti som postupoval správne a všetky zistenia boli platne, dnes som si istý napr. tým, že neurónová sieť by to vyriešila taktiež, dokonca rýchlejšie ako ten spomínaný algoritmus concorde TSP, keďže on ma aj optimalizačne kroky. V podstate je asi zbytočne sa tomu nejak venovať, keďže je to vyriešené celkom dobre. 

Tak som sa chvíľku pohral s "dokonalym riešenim" v programe. Skúšal som túto sekvneciu 1000 náhodných bodov a zistil som, že to robil cca 5 minut. Som si istý, že som schopný urobiť softwer, čo to urobí do 10 sec, možno to nebude dokonalá cesta ale rozdiel od tej "dokonalej nebude viac ako 0,05% možno ešte menej. Prikladam aj to, že ľudské oko nájde chyby pri pohlade na obr. za 5 sec. Chyba je vyznačená aj nakreslená správna cesta, no a bohviečo je tam ešte "dokonalé" ...

pre porovnanie prvý ľudsky nestrel (neoptimalizovane), robene od oka podľa tu popísaných zásad, trasa sa nelíši ani o 0.5%. Nelíši sa to od dokonalej trasy. Tie trápne úvahy, že simulované žíhanie je lepšie ako tu popísané zásady pre spájanie, je ako prirovnať bukyho vo fyzike s Einsteinom. 

Tak som vytvoril ďalší článok na problematiku obchodného cestujúceho:

link: https://robopol.sk/blog/obchodnycestujuciporovnaniealgoritmovtsp

troška to ešte optimalizujem a :

Na obr vidíte progres medzi simulovaným žíhaním a vylepšenou metódou najbližšieho suseda (optimalizovanou). Táto metóda nájde optimálne riešenie, resp. blízko optimálneho riešenia do cca 35-50 bodov. Záleží od rozmiestenia. Na obrázku je vyznačené , že ak zrušíme kríženie, tak spojnicami, červenou farbou dostaneme optimálnu cestu.

program v pythone som kompiloval aj do . exe verzie na otestovanie. Takže aj bez concorde sa dá cez dostupnú metódu (ľahko naprogramovanú) dostať optimálne dráhy po miernej korekcii (ak je treba pri krížení dráh). Funguje to zhruba dobre do 50 bodov. 

tak mi to zas nedalo a vylepšil som ten algoritmus najbližšieho suseda.

Simulovane žíhanie sa ani po 3000 iteráciach nepriblížilo k tejto jednoduchej metóde, ktorá bola významne vylepšená. Pracuje to rýchlo.

aj niečo náročnejšie ide a dokonca rýchlejšie ako u concorde

Tie posledné obrázky už vyzerajú celkom slušne. Pri riešení tohoto problému si získal aj programátorské skúsenosti, čo sa ti určite hodí. Trochu si ma inšpiroval a rozmýšľal som nad inou metódou. Hneď som narazil na otázku, kde začať a ktoré oblasti prioritne riešiť. V podstate sa dá postupovať napríklad z vonkajšieho obvodu, smerom do vnútra, ale to určite nie je optimálna cesta.

Pri veľkom počte bodov som každému bodu priradil potenciál, napríklad v tvare exp(-x^2). Výsledný potenciál množiny bodov (súčet, alebo súčin potenciálov ) vytvoril "zvlnenú plochu" a maximá plochy boli najväčšie tam, kde bola najväčšia hustota bodov. Začal som spájať najprv body v oblasti najväčšieho potenciálu, s najväčším gradientom. To vlastne zodpovedá - najbližšiemu susedovi. Výsledok nebol najhorší, ale čiary sa krížili pri prechode z jedného centra do druhého. Už sa mi stým potom nechcelo baviť, ale zrejme by som nedosiahol lepší výsledok. Navyše som do výpočtu zaviedol nelineárne funkcie a to spomaľuje algoritmy. 

dik Tono, vylepšil som metódu najbližšieho suseda a to tak, že do 20 bodov nájde skoro vždy najlepšiu, alebo blízku optimum, do 200 bodov je veľmi blízko tej optimálnej metódy zhruba odchylka do 5% z tej najkratšej dráhy. Simulovane žíhanie je pomalšie oveľa na opt. výsledok pre 10 bodov potrebuješ 500 iteracii, do 15 bodov 1000, nad 15 zhruba 5000 iterácii a potom sa už simulovane žíhanie nechytá ani v rýchlosti riešenia ani v optimálnej drahé, pri 500 bodoch to predčí  niekoľkonásobne simulované žíhanie.

Dá sa však vytvoriť algoritmus na lepšej báze ako je najbližší sused. Avšak algoritmus najbližšieho suseda je jednoduchý a moja optimalizačná časť k tomu je tiež jednoduchá, celkovo teda môžeš využívať tento algoritmus ako spoľahlivý a rýchly. do zhruba 200-300 bodov, potom neviem ako stráca na najkratšiu dráhu asi už 5%.

asi ho dám free, môžeš si ho otestovať čoskoro.

Zdrojový kód:
 V Pythone: traveling_salesman_problem_3.py
exe súbor: traveling_salesman_problem_3 .exe (spustiteľný súbor bez nutnosti inštalácie Pythonu)

Kód by sa dal ešte zrýchliť tým, že by bola vytvorená matica všetkých dĺžok, potom by si nepotreboval opakovane rátať vzdialenosti medzi bodmi, keď hľadáš najbližšieho suseda a pod.

PS: ak potrebuješ vysvetliť kód použi Open AI nakopíruj text kódu a napíš jej až ti kód vysvetli v SK jazyku. Bude vedieť aj kusy kódu preložiť napr. do jazyka c++. Zrejme nebude vedieť napísať požuté funkcie z rôznych modulov, skús ak chceš, možno bude.

Program https://www.poling.sk/TSP/traveling_salesman_problem_3.exe antivírová ochrana ESET nechcela program spustiť. Potom som to povolil, ale zobrazilo sa mi len okno 

no na chvíľku kým sa to načíta máš prázdne okno, a chyba ti nejaký path.

zadaj do google

api ms win core path l1 1 0 dll

https://windll.com/dll/microsoft-corporation/api-ms-win-core-path-l1-1-0

PS: skôr nastal problém v tom, že keď si to stiahol a hneď dal aj spustiť, tak paranoidný antivirus aj windows začali všetko blokovať. Nakopíruj si to do nejakej zložky a potom to skús spustiť.

Ide ti to? Daj vediet, či sa da spustit ten exe subor aj na inom pc. Ak mas python nainstalovany, tak staci ked napises dve veci do prikazoveho riadku:

pip install matplotlib

potom

pip install shapely

základy inštalácie Pythonu su na nete.

Spustil som exe na inom počítači s Windows10 a program funguje bez problémov. Vyzerá to veľmi dobre, aj keď na prvý pohľad nedokážem posúdiť, či je to najoptimálnejšia cesta. Zrejme si to testoval, tak to vieš najlepšie posúdiť. Je vidieť, že si sa s tým pohral, blahoželám.

áno pohral som sa s metódou najbližšieho suseda, čo ma svoje limity keďže je to až moc jednoduchý algoritmus. záleží od počtu bodov, čím viac ich zadáš tým sa to zhoršuje tak do 200 bodov to funguje dobre, potom sa to odkláňa od dokonalej cesty viac nad 4% určite. je to len vylepšenie toho základného algoritmu, je ešte jednej dobrý kandidát, ktorý by to mohol robiť lepšie a aj rýchlejšie. Pozriem na to časom.

Odhadujem, že pri veľkej hustote náhodné umiestnených bodov už nebude veľký rozdiel medzi optimálnou cestou a postupným spájaním bodu po bode. Stredná hodnota vzdialenosti bodov bude takmer rovnaká. Takže nezáleží len na počte bodov, ale aj ich hustote. Reálne má tvoj program praktické využitie aj s obmedzením na 200 bodov.  

tak ono je to ťažké povedať ja som to zatiaľ detailne neskúmal, skúmal som ako je to pri menšom počte bodov a to je prekvapivo dobre, takže neviem ako to reálne stráca napr. pri 500 bodoch na tu dokonalú cestu, to časom zistím. Napr. moje vylepšenie dalo 7,1% menšiu trasu ako keď urobíš z 500 bodov najbližšieho suseda, vyberieš tu najlepšiu trasu. Pričom stále je čo optimalizovať aj na tom mojom algoritme.