Jump to content

Problém obchodný cestujúci


robopol

Recommended Posts

Algoritmus najbližšieho suseda nájdeš tu :

- odkaz 

Tam nájdeš tie optimalizačné kroky, je tam aj cely kód v pythone.

ja sa ti čudujem, že to robíš na stránke, je to pracnejšie, musíš upravovať parametre servera a podobne, musíš robiť pod Linuxom. Nie každý software je vhodný robiť na stránke. Užívateľ si vie stiahnuť aplikáciu a používať ju aj offline

Link to comment
Share on other sites

V kútiku mi, ale hra taká pesnička s hlasom, že možno existuje ešte lepší a rýchlejší algoritmus, ktorý by pospájal milióny bodov v rovnakom čase ako pospája tisíc bodov. Ten algoritmus, ktorý máš už aj ty je rýchlejší ako Concorde. Tento algoritmus je v pythone a tak je pomalší, v c++ by bol o dosť rýchlejší. Lenže neviem, či táto okrajová  téma mi stojí za to. Možno by bolo nie na škodu sa pozrieť na tie numerické algoritmy na riešenie diferenciálnych rovníc. Netuším či je tam potenciál urobiť nejaký, kde už nebudeme potrebovať hľadať analytické riešenia, lebo tie numerické modely sa im priblížia dostatočne. Možno sa zase vrátim k nedoriešenému problému ako je Collatz, kde potrebujem proste zdolať jednu rovnicu a nájsť všeobecný dôkaz. Čo je samozrejme pre život na planéte úplne zbytočne :)

Link to comment
Share on other sites

Našiel si algoritmus, ktorý úspešne rieši úlohu Problém obchodný cestujúci. Otázkou je, či ti to úsilie stálo za to. Podľa mňa áno. Naučil si sa nové veci, ktoré môžeš využiť. Ja som sa chvíľu "zabával" s Pythonom a podľa mňa je to perspektívny jazyk, aj pre vedecké výpočty. V jazyku C a C++ sa budú zrejme programovať už len mikroprocesory a PLC. 

Numerické riešenie diferenciálnych rovníc v javascripte sa mi podarilo rozchodiť". Robím už nejakú aplikáciu, ale musím sa učiť. V mojom veku to už ide pomaly. Čo sa dnes naučím, to už zajtra zabudnem. Staré vedomosti mi zostávajú v pamäti, ale tie nové už nie... 

Link to comment
Share on other sites

Môžem samozrejme využiť inde, ale aj tak si to neuchovávam v pamäti. Rovnako by som sa musel pozerať, čo som to vyriešil a ako s Riemannovou hypotézou, či Collatzovou hypotézou. Pre mňa ešte ostáva stále vyskúšať nejaké nápady na "dokonalý algoritmus" a asi až potom túto tému opustím. Asi si kladime veľmi ambiciózne ciele, uvidíme.

Link to comment
Share on other sites

pred 1 hodinou, robopol napísal:

 Asi si kladime veľmi ambiciózne ciele, uvidíme.

Ja som "našťastie" vo veku, keď už nemusím rozmýšľať nad tým, či to čo robím má nejaký zmysel a či takto vynaložený čas sa mi aj zúročí. Keď človek musí zabezpečiť seba a rodinu, tak je to luxus, zaoberať sa takýmito témami. Ale ľudia obetujú mnoho času na nezmysli. Ak robia to, čo im prináša radosť, napríklad sledovanie športových udalostí, tak to pre nich nie je "stratený" čas. Mňa baví fyzika, ale neočakávam, že v nej dosiahnem nejaké úspechy. Som rád, keď dokážem pochopiť aspoň to, čo si prečítam vo vedeckých článkoch. Väčšinou ani to. Klásť si vyššie ambície by bolo pre mňa frustrujúce. 

  • Like 1
Link to comment
Share on other sites

  • 2 weeks later...

Tak som porobil nejaké ďalšie funkcie k programu, ďalšie ability a zároveň som začal pracovať na ešte lepšom algoritme (teda dúfam). Mna aspoň uspokojuje to, že celý rad matematikov predo mnou to riešil roky a mne to trvalo par mesiacov. Mam konkurencie schopný algoritmus.

Screenshot - 13_ 6.jpg

Bude sa dať použiť aj na skutočnú cestu v google maps.

 

skuska.jpg

TSP_solver.png

Link to comment
Share on other sites

  • 1 month later...

tak som sa ešte pohral s tým najbližším susedom a podstatne som zrýchlil algoritmus a zároveň zlepšil kvalitu dráhy.

Screenshot - 2_ 8.jpg

Link to comment
Share on other sites

  • 9 months later...

Trocha som vylepšil metódy a program:

TSP Solver verzia 1.0.1 Update: Aktualizácia programu o ďalšie metódy a nastavenia. Zlepšenie účinnosti :20-50 násobné zrýchlenie metódy "Najbližšieho suseda" pomocou knižnice Numba, ktorá výpočet robí v strojovom kóde. Zmeny v licenciách a vo verzii demo. Stránka programu: https://robopol.sk/tsp-solver/index

S Optimalizovaným najbližším susedom (cca 5% dlhšia ako optimálna dráha) je možné robiť desiatky tisíc bodov. V budúcnosti plánujem vytvoriť ďalší algoritmus, ktorý by mal byť rýchlejší a presnejší ako optimalizovaný najbližší sused, len neviem kedy sa k tomu dostanem a odladím to.

Screenshot - 2_ 5.jpg

Link to comment
Share on other sites

Ten obrázok mi pripomína nejakú organickú štruktúru.

Link to comment
Share on other sites

Zaujímavé, že z nejakého relatívne jednouchého princípu môže vzniknúť niečo takéto. Nie je to práve problém obchodného cestujúceho, ale v určitom zmysle to pripomína morfológiu mozgu. Napríklad, ako evolučne dosiahnuť maximálny povrch mozgu pri danom objeme, limitovaný minimálnou dĺžkou kapilár, rovnomerne prekrvujúcich celý povrch mozgu. Alebo, aký povrch mozgu zabezpečí najväčší počet a najkratšie spojenie všetkých synapsií na povrchu danej oblasti.   

Link to comment
Share on other sites

  • 2 weeks later...

Tono,

Ono sa to zdá, že je to nejaký jednoduchý princíp, ale nie je to tak, Algoritmus tej metódy je pomerne dlhý, keďže ale vychádza z nesprávneho základu zázrak sa nedá urobiť.  Výpočtová náročnosť neúmerne stúpa. Len matica vzdialenosti pri 100 tisíc bodoch je 100000*100000, čo je 10 miliárd výpočtov, zároveň to zaťažuje pamäť a tak je potrebná optimalizácia všetkého, ešte aj takej základnej veci ako je matica vzdialenosti.

Link to comment
Share on other sites

pred 4 hodinami, robopol pridal:

Tono,

 Len matica vzdialenosti pri 100 tisíc bodoch je 100000*100000, čo je 10 miliárd výpočtov, zároveň to zaťažuje pamäť a tak je potrebná optimalizácia všetkého, ešte aj takej základnej veci ako je matica vzdialenosti.

Z teoretického hľadiska je to zaujímavá úloha, ale v prípade "obchodného cestujúceho", nemá také veľké množstvo bodov praktické využitie. Ale keď sa v minulosti riešili teoretické problémy, nakoniec sa našla aj aplikácia, v celkom neočakávanej oblasti.

Keď sa pozerám na grafické výsledky, tak pri veľkom počte bodov na danej ploche, by mala efektivita optimálnej trajektórie klesať. Vychádzam z úvahy, že pri veľkom počte náhodne generovaných bodov na danej ploche, sa hustota bodov blíži k rovnomernému rozloženiu. Keby sme hustotu náhodne generovaných bodov infinitezimálne aproximovali rovnomernou hustotou, potom môžeme zvoliť aj trajektóriou "riadok po riadku" a táto trajektória by sa dĺžkou limitne blížila najkratšej trajektórii. Ale možno sa mýlim, to by sa dalo len vyskúšať. Pri nerovnomernom rozložení bodov, ktoré sú umiestnené v clustroch, to samozrejme neplatí.       

Link to comment
Share on other sites

Tak to sa isto mýliš, pri väčšom počte bodov smerom k nekonečnu presnosť nakódovanej metódy klesá. Pri random generácii nedostaneš rovnaké vzdialenosti bodov, ono sa  zdá, že vzdialenosti medzi bodmi sú rovnaké, ale zabúdaš na to, že ti rastie aj počet bodov, proste tvoja úvaha nie je správna.

Link to comment
Share on other sites

Efektivitu vyhodnocuješ zrejme na základe dĺžky výslednej trajektórie. Keby sme zvolili najmenej efektívnu metódu, tak by sme postupovali kreslením čiary v riadku a následne pokračovaním čiary v nasledujúcom riadku. Na to nepotrebuješ program, dĺžka čiary sa dá vypočítať z počtu riadkov a stĺpcov. Táto metóda by mohla byť etalónom, voči ktorej sa dá porovnávať efektivita optimálnej metódy.

Ak by sme mali len dva body, metóda riadok po riadku by bola najneefektívnejšia. S pribúdaním bodov by sa jej efektivita zvyšovala. Bol by zaujímavý graf efektivity, teda pomeru dĺžky týchto trajektórií, v závislosti od počtu bodov na danej ploche. Samozrejme, úvahy s takouto vysokou hustotou bodov, na danej ploche, sú len teoretické.

Link to comment
Share on other sites

Teraz neviem, čo presne myslíš. Skús sa vyjadriť presnejšie, názornejšie. Presnosť algoritmov porovnávam s optimálnou dráhou (na čo mam tiež napr. algoritmus), ktorú viem získať do zhruba 2000-3000 bodov (v rozumnom čase)a viem, že optimalizovaný najbližší sused (presnosť) klesá, teda dráha ide >5%. O 5% je dlhšia ako optimálna dráha. Ja teda tvrdím, že ak generuješ viac a viac bodov, tak sa ti dráha predlžuje nad optimálnu dráhu.

Link to comment
Share on other sites

pred 6 hodinami, robopol pridal:

Presnosť algoritmov porovnávam s optimálnou dráhou (na čo mam tiež napr. algoritmus), ktorú viem získať do zhruba 2000-3000 bodov (v rozumnom čase)a viem, že optimalizovaný najbližší sused (presnosť) klesá, teda dráha ide >5%. 

Odkiaľ máš algoritmus na optimálnu dráhu?  

Link to comment
Share on other sites

Takže môžeš efektivitu tvojho algoritmu porovnávať. Ale bez ohľadu na to, o aký algoritmus sa jedná, pri veľkej hustote bodov jeho efektivita musí klesať. Limitne, pre veľkú hustotu bodov je potom jedno, akú trajektóriu si zvolíš. 

Link to comment
Share on other sites

Zoberme si príklad. Nech má obrazovka 640x480 pixelov. Nech vzdialenosť pixelov je 1mm. Dĺžka riadku je úsečka dĺžky cca 640 mm. Počet riadkov je 480. Celková dĺžka čiary je L = 640 x 480 = 307200 mm

Takže ak by sme použili metódu spájania všetkých bodov čiarou cez riadok a potom by sme pokračovali čiarou v nasledovnom stĺpci, dĺžka celkovej čiary by bola 307200 mm. Touto čiarou by sme prepojili všetky body.

Ak by sme efektivitu definovali počtom prepojených bodov N k celkovej dĺžke čiary L

effectivity = N/L*100

potom pri 2 bodoch by bola efektivita 2/307200 = 6.5E-4 %. Ak by boli obsadené všetky body v rastri, efektivita tejto "stupídnej" metódy by bola 100 %. Efektivita ľubovoľnej metódy by sa pri veľkej hustote bodov mala limitne blížiť k tejto hodnote. Napríklad v rastri 640 x 480, k dĺžke čiary 307200 mm.

Link to comment
Share on other sites

ale to mas úplne inú úlohu, kde máš rovnaké vzdelanosti, tak môžeš robit taký cik cak. No lenže keď generuje random body náhodne aj do nekonečna, tak sa ti zázračne nerozmiestnia v rovnakej vzdialenosti od seba. My neriešime triviálnosti, ale body, ktoré nie su rozmiestnené od seba rovnako. Ty ani pri generovaní bodov smerom k nekonečnu nedostaneš rovnaké vzdialenosti, to je chybná úvaha, máš síce čoraz menšie vzdialenosti od seba, ale stále sú to rozdielne vzdialenosti a pri veľkom počte bodov sa ta diskrepancia vyrovná.

Link to comment
Share on other sites

Skús si program. Máš bielu obrazovku a nech random funkcia ti vygeneruje súradnice pixelov na obrazovke, ktoré budú čierne. Po určitej dobe bude obrazovka "čierna". Ale aj po "nekonečnej dobe" nájdeš na obrazovke biele pixeli. Je to preto, že random je pseudonáhodná funkcia. Ak by to bola náhodná funkcia, po nejakom čase musí byť každý pixel čierny.

Ale to nie je podstatné. Podstatné je, že pri veľkej hustote bodov by sa mala efektivita každého algoritmu blížiť k rovnakému výsledku. Veľká hustota bodov nie je ale zmyslom riešenia danej úlohy, takže to je len poznámka na okraj.

 

Link to comment
Share on other sites

No ja nič nemusím skúšať, pretože chápem ako sa to chová. Obrazovka nie je ideálna, ma len určitý počet pixelov, ktoré by si raz vyplnil všetky. Ak chceš viesť takéto úvahy, tak samozrejme sa nebavíme o pseudonáhodných algoritmoch, ani sa nebavíme o konečnom rozlíšení obrazovky, ak sme v matematickom svete, kde máš nekonečné rozlíšenie, tak sa ti to nestane. Naopak je pravda, že akýkoľvek nepresný algoritmus ti postupom času dá čoraz horšie výsledky. Takže tvoj záver je nesprávny a pravý opak tvojho tvrdenia je pravda.

Link to comment
Share on other sites

Na rozdiel od teba som si to vyskúšal v praxi. Random je pseudonáhodná funkcia. Pri serióznych fyzikálnych experimentoch, napríklad pri korelácii fyzikálnych javov, sa funkcia random nepoužíva, preto že by generovala "fantómové" maximá, ktoré nemajú nič spoločné s fyzikálnou realitou. Ako generátor náhodnej funkcie sa využíva "biely šum" z nejakého reálneho fyzikálneho objektu. 

Pri veľkej hustote bodov môžeme použiť aj najstupenejšiu metódu s rovnakým výsledkom. To ale nijako nedehonestuje sofistikované metódy. Cieľom algoritmu "obchodného cestujúceho" nie je zvyšovať hustotu bodov na danej ploche, pretože to nemá praktické využitie. Podobné úlohy sa riešia napríklad pri navrhovaní plošných spojov. Úlohou je spojiť množiny bodov, s čo najkratšou spojnicou a iné množiny bodov, s ktorými sa tieto množiny nesmú križovať. Z praxe ti môžem povedať, že zatiaľ neexistuje algoritmus, ktorý by bol efektívnejší, ako manuálny návrh. Je to proste zložitý matematický problém. Výhodou je zatiaľ iba to, že tieto metódy dokážu verifikovať manuálny návrh, nájsť v ňom prípadné chyby, opraviť ich a optimalizovať manuálne riešenie. Sami však nie sú schopné dopracovať sa k výsledku, pri komplikovanej konfigurácii.    

 

  

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue. Additional information you can see at Privacy Policy