Skočiť na obsah

Problém obchodný cestujúci


robopol

Odporúčané príspevky

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. 

Screenshot - 15_ 2.jpg

Odkaz na príspevok
Zdieľať na iných stránkach

  • Pred 2 týždňami...

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.

 

Screenshot - 27_ 2 002.jpg

Screenshot - 27_ 2 003.jpg

Odkaz na príspevok
Zdieľať na iných stránkach

  • Pred 2 týždňami...

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.

Screenshot - 13_ 3.jpg

Odkaz na príspevok
Zdieľať na iných stránkach

  • Pred 1 mesiacom...
  • Pred 3 týždňami...
  • Pred 2 týždňami...

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

 

intro.jpg

Screenshot - 24_ 5.jpg

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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%.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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.

Odkaz na príspevok
Zdieľať na iných stránkach

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?

Odkaz na príspevok
Zdieľať na iných stránkach

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... 

Odkaz na príspevok
Zdieľať na iných stránkach

Vytvorte si účet alebo sa prihláste, aby ste mohli písať príspevky

Ak chcete odoslať príspevok, musíte byť členom

Vytvoriť konto

Zaregistrujte si nový účet v našej komunite. Je to ľahké!

Zaregistrovať si nové konto

Prihlásiť sa

Máte už konto? Prihláste sa tu.

Prihlásiť sa teraz
×
×
  • Vytvoriť nové...

Dôležitá informácia

Táto stránka používa súbory cookies, pre zlepšenie používania stránok tohto webu. Pre viac informácií kliknite sem. Ďalšie informácie nájdete na stránke Zásady ochrany osobných údajov