Problém obchodný cestujúci

Tak som zobral riadnou okľukou, teraz robim praktickú aplikáciu s viacerými funkciami a chcem doprogramovat viaceré metódy vrátane metódy lineárneho programovania ako ma Concorde TSP, možno v budúcnosti pridám aj neuronovu siet, ako by sa jej darilo nachádzať dobre riešenia. 

Publikácia venovaná optimalizacii metódy najbližšieho suseda s popisom algoritmu:

https://robopol.sk/blog/vylepšenie-metody-najblizsieho-suseda-tsp-problem

Pracujem na novom algoritme aj metóde TSP solving, táto metóda bude rýchla a bude mat veľmi dobre výsledky, len pre porovnanie o rozprávkach analytických riešení concorde TSP uvádzam príklad, kde som ručne (zatiaľ) požil metódu a porovnal s Concorde, našiel som kratšiu cestu ako Concorde. Dokaz je na obrázkoch.

staviam ten exaktný algoritmus a aktuálne sa snažím o jeho optimalizáciu, aby pracoval, čo najrýchlejšie. Concorde je aktuálne rýchlejší ako môj exaktný algoritmus v pythone (python je o dosť pomalší ako c++), avšak zistil som, že Concorde nie je žiaden "exaktný algoritmus". Urobil som jeden pokus na 20 bodov a okamžite som zistil, že moja trasa je kratšia o 1,7 cm merané pri 100% veľkosti priloženého obrázku  - merané na prvom grafe. Je kopu práce na tom algoritme tak zatiaľ neviem kedy bude finálny program so všetkými metódami, ako je metóda mravcov - ACO heuristic, 2 opt. optimalizácia, vylepšený najbližší sused, potom môj algoritmus (možno pridám aj simulované žíhanie, čo je úplne najhorší spôsob) ktorý bude ponúkať exaktne riešenie, alebo v nastavení aj menej presné, ale o dosť rýchlejšie.

Nový algoritmus pre TSP problém, viac na : https://robopol.sk/blog/tsp-metoda-postupneho-pridavania-bodov-robopol

článok obsahuje odkaz na demonštračný program pre pochopenie princípu a toho ako algoritmus pracuje.

tak finalizujem môj programik a pre ukážku optimálnej cesty cez všetky mesta a mestečka v SR vzdušnou čiarou:

Tono, 

Ahoj, prosím ta ak chceš môžeš vyskúšať aplikáciu TSP Solver, obsahuje rôzne funkcie, napr. das si neimportovať obrázok, das si create points a miesta, ktoré chceš pospájať, alebo si môžeš dat random points. Su implantovane dve metódy (iné nemajú význam), vylepšená metóda najbližšieho suseda a najkratšia trasa, v programe, ktorý tu dávam dočasne nefunguje akurát: napovedá, uloženie súboru, export obrázka, uloženie súboru, import data, export data. Je to len ukážkový software (intuitívne ovládanie), kam som to dotiahol a ako rýchlo nájde riešenie. tento odkaz bude zmazaný za 3 dni. Okno programu si môžeš zväčšovať ako chceš. Napíš mi, či ti to funguje ako ma. Je to komprimovaný rar súbor. niekde si ho ulož, rozbal, a spusti - traveling_salesman.exe.

LINK:https://www.poling.sk/TSP/traveling_salesman.rar

Dostal som správu:

Ahoj s tým si mal už problém, keď si skúšal konzolovú aplikáciu pre najbližšieho suseda. Nejak si to potom rozchodil, zrejme si to otvoril na PC nie notebooku.

Bežne robím na PC s Windows7. Musím to otvoriť na Windows10, ten PC momentálne nemám, ale tam to funguje, ozvem sa. 

ok, tak pridám taký malý test, spajal to asi 3-4 minuty:

vsimol som si ze riesenia vedu k krivke, ktora sa nekrizuje,  zaujimave.

Ano presne tak, zaujímavé je, že sa stala mala anomália a v tomto obrázku je jedno kríženie, ktoré program odignoroval, pretože tam nemusí byť, ale ta zmena vzdialenosti je na úrovni 0,01%.

Otvoril som program, nakreslil body, ale ako sa spúšťa spájanie bodov?  

calculate,   tlačidlo chart ti vykresli samostatný graf so súradnicami bodov,   create points klikáš myškou kam chceš, delete points maze body, clear vymaže všetko z obrazovky, method si volíš metódu, import image vkladáš obrázok, random points spúšťaš cez menu - data. remove lines zrušis spojnice bodov.

calculate je čo button? Ja tam nič také nevidím, čím by som spustil spájanie bodov. Mám nakreslené body, aký je ďalší krok?

pozri si obrazok programu tu vyššie, vidíš pod menu 4 tlačidla? tam je calculate.

Ja ich tam nevidim. Spustil som program traveling_salesman.exe

rozšír si okno programu z nejakých príčin sa ti úvodné okno otvorilo menšie ako malo.

Jasne, nems tam rolovacie listy, tak nie je jasne, ci je to zmensene okno.

A podarilo sa ti to zväčšiť? už by si to mal vidieť, problém je možno preto, že používaš nízke rozlíšenie obrazovky. Potrebuješ viac pixelov nastaviť na obrazovke.

Ale áno, už som to spustil. 

ja používam nastavenie 3840 x 2160, tak som si neuvedomil, že to okno programu sa neotvorí celé pre malé rozlíšenia.

Ak si si to vykúšal, tak sám vidíš silu algoritmu, mravce aj tie umelé sa s tým nedajú porovnať, pretože nenájdu najkratšiu trasu. Čo som prekvapený, že ten optimalizovaný najbližší sused je o niečo málo rýchlejší, ale pri väčšom počte bodov začína strácať na tu najkratšiu trasu. Chcelo by to ešte jeden optimalizačný krok pre ten algoritmus. Ale už sa mi to nechce robiť, všetko to stoji čas a energiu.

Ak sa pozriem na výsledok, algoritmus máš urobený veľmi dobre. Metódu najnižšieho suseda aplikuješ v každom bode, do ktorého si sa práve dostal, alebo na začiatku programu?

pred 9 hodinami, robopol napísal:

Ale už sa mi to nechce robiť, všetko to stoji čas a energiu.

Ale naučil si sa  pri tom veci, ktoré môžeš využiť aj inde. Ja som začal riešiť diferenciálne rovnice v Pythone a je to neporovnateľne efektívnejší nástroj, ako C++. Python má veľa knižníc a väčšinu práce, ktorú by si musel napísať v C++, sú už hotové. Nakoniec som to ale vzdal, kvôli tomu, o čom sme sa bavili. Dnes potrebuješ mať aplikáciu na stránke, a aj kvôli sebe. Keď otváraš bránu, kŕmiš mačku, alebo zalievaš záhradu...