Problém obchodný cestujúci

To akze mam ti pospajat rucne body a ty skontrolujes s najlepsou drahou? Este raz to je metoda pre ludi a myslim ze dobra a efektivna kedze clovek nie je stroj, na algortimy sa zide partak urcite co ma chut nieco naprogramovat ked je v tom zbehly, ja by som si musel oprasovat stare vedomosti naucene len z netu. Postup je troska iny, musim dobre pochopit jestvujuce algoritmy, pretoze u algoritmov to bude ine kedze je viac moznosti, jednou je napr. ghladat uplny algoritmus ktory bude elminovat zbytocne vetvy, ktore proste nemozu byt dobre. Potom sa da hladat turbu algoritmus ze najde rychlo nejake lokalne minimum ale v nejakej vetve ktora sa javi ako najperpektivnejsia, prinos je hlavne rychlosti dali by sa riesit dostatocne velke mnozstva bodov, teda aj viac ako tisice. Ked mas takyto problem s obrovským poctom bodov tak to nemas taketo ze par miest na velkej ploche rozutekanych. Ja dufam ze sa aj tono zapoji a ked sa vymysli nieco zaujimave nemusime to vesat nanet zadarmo, az taky dobrak nie som ze venujem tomu kopu casu a potom to dopadne este tak, ze sa ma niekto opyta a na co to vlastne je:)

 

takze spolupraca na takychto veciach sa vzdy hodi.

vygeneruj nahodne na nejakej ploche  do 1000 bodov a ja ti to ukazem, ale to co chces vlastne je pracne, navyse to ide o dokazovanie ze metoda pre ludi je dobra, mozeme skusit ale s tym sa naciaram 1000 spojnic

To akze mam ti pospajat rucne body a ty skontrolujes s najlepsou drahou? Este raz to je metoda pre ludi a myslim ze dobra a efektivna kedze clovek nie je stroj,

Ja ti neviem, ked tvorim nejaky algoritmus, tak vzdy chcem vediet jeho vykonnost. Mysliet si, ze je dobry, mi nestaci. Aj ked je len pre ludi, a je jasne, ze nebude 100% optimalny, by mna, ako autora, zaujimalo nakolko sa prbilizuje inym implementaciam.

 

vygeneruj nahodne na nejakej ploche  do 1000 bodov a ja ti to ukazem, ale to co chces vlastne je pracne, navyse to ide o dokazovanie ze metoda pre ludi je dobra, mozeme skusit ale s tym sa naciaram 1000 spojnic

Ak si ten algoritmus schopny formalne definovat, tak skutocne nie je problem ho zapisat do kodu a pozriet, ako sa mu vedie. A vobec tych bodov nemusi byt 1000, staci 10, nerovnomerne distribuovanych na ploche. To by nemal byt problem nakreslit na stvorcekovy papier, pospajat a odmerat/vypocitat.

Mas ho formalne definovany a nie len formalne, mas ho na via ako 10 bodov, mas prikaldy mozes skusat, pretoze pre ludi nie je zaiden :) ale si srandista ze 10 bodov myslim ze touto vetou si to zabil. A ja fakt nemam cas na plytke debaty.

Algoritmus je do max 3 iteracii u 10 bodov na jednu, ak najdes nejaky lepsi algoritmus na tri iteracie, a to nehovorim, ze staci si to zratat sam ked mas o tom pochybnosti ako sa to chova pri viac bodoch random rozhodenych prave to mas obrazok v predoslom prispevku, urcite to nie je optimalne je to na jednu iteraciu, a ze sa to nebude az tak lisit s dokonalou drahou mozes preverit sam na tych jednoduchsich, u symetrickych co mam v prikladoch je to dokonala trasa akurat je tam jeden zlozitejsi a ten si mozes prepocitat sam, mne netreba vsetko pracne ratat vidim ze to je blizko optima, co je skvale na do troch iteracii.

Pridal som nejake dalsie zlozitejsie asymetricke obrazky do clanku, popri kave. CO je podstatne je to, ze sa dju samozrejme zratat drahy a porovnat to by musel mat clovek program. TAk ako mozeme vediet, ze je to blizke optimalnej drahy bez narocneho ratania, to je celkom zaujimave ako hadanka, ktora ma samozrejme riesenie.

 

 

Tak ukaz ako sa ti podari klasicky problem , hlavne mesta v USA

to je zopar bodov, nic viac je tam len obvodova technika a par pincipov nekrizit, mat z jedneho uzla dve spojnice, minimalne drahy medzi uzlami pouzit a to co mas nakreslene tomu zodpoveda

ved ano, ale  dost trvalo kym to ludia v 18 storoci nasli,    tak ukaz ako funguje tvoj algoritmus a mas zaroven spravny vysledok.  

tyso ty si hadam rozumny clovek tak si precitaj ten diel treti alebo vsetky najdes v nom postupy ako to robit, ja necurujem dodrziam to co som popisal a tak by som aj tu darhu co si dal nakreslil. lebo ked dodrzis co som napisal sa k tomu dopracujes a pomerne rychlo. vidis hore kde je mozno aj 200 uzlov, to som urobil okamzite samozrejme sa to da optimalizovat pri troche casu, pc by to urobil tak rychlo este aj soptimalizaciou ze by si to mal do sekundy podla tych pravidiel. Samozrejme netvrdim ze neexistuje v narocnom probleme vela bodov nejaka nestandartna ecsta ktora ma este nizsie minimum, to nie je v ludskych silach robit bez systemu.

 

Pre zaujimavost slovensko vzdusnou ciarou.

Mas ho formalne definovany a nie len formalne, mas ho na via ako 10 bodov, mas prikaldy mozes skusat, pretoze pre ludi nie je zaiden :) ale si srandista ze 10 bodov myslim ze touto vetou si to zabil. A ja fakt nemam cas na plytke debaty.

Pytat sa na uspesnost algoritmu, ktory ty povazujes za optimalny, skutocne nie je plytka debata. Ako si vobec dosiel na tvrdenie, ze je optimalny, ked si ani samotnu cestu nezmeria.

Momentalne som vo Varsave, ale ked pridem, tak asi nakodim apku, ktora ti vygeneruje urcity pocet bodov, ktore ti nasledne dovoli pospajat, a zaroven ti ale vypocita cestu pomcou simulovaneho zihania. Takze porovnat vysledky uz vobec nebude pracne ;)

Afrika - obvodova technika

Plytke je ze povazujes 10 bodov za nejaku dostatocnu vzorku udajom pre porovnavanie efektivnosti, pri tom pocte ani nepouzijes cik cak, vidis sam na mapach afriky, USA su len naznaky pouzitia cik - caku. Na to ako viem ze je optimalny bez toho aby som poznal celkovu dlzku, odpovedam to je moje tajomstvo, skor urobim tu cestu ako spocitam 100 bodov.

Ale ja pisem ze zatial mam efektivnypostup pre ludi, o tom nepochybujem, vobec neviem ako by to bolo naucit to pocitac, ci by nebol kod prilis zlozity na rozdiel od dostupnych algoritmov. Algoritmus pre pocitac bude nieco asi nieco ine to musim premysliet a hlavne sa musim zoznamit s algoritmami ktore su a ako funguju detailne. Kebyze ma existovat dobra aplikacia musi body abstrahovat z lubovolneho obrazka, previest ich na suradnice poratat dlzky medzi nimi atd. Az nasledne moze spustit nejaky algoritmus a teraz zavisi ci uplny ci neuplny, tato metoda sa prave ujme pri obrovskom pocte bodov kde nie je mozne urobit uplny algoritmus z dovodu limitov vypoctoveho vykonu pc. Mate metodu, mna nikto neplati za napady, ani za vyucbu ako co robit ..

tak mi napadlo, keď som nevedela v noci spať, že tento problém by mohol byť zaujímavejší, alebo bol, obchodní cestujúci existovali už aj v časoch, ke´d auto nebola samozrejmosť:  keby ten obchodný cestujúci musel počítať so spojmi... napadlo mi to z jednej detektívky dámy Agathy Christie, kde v jednom z príbehov vystupuje obchodný cestujúci, ktorý cestuje vlakmi :)

už padám :ahooj:

Skor by bolo na mieste ci ti clanky nieco dali, pretoze kazdy jeden niekedy potrebuje navstivit x miest po sebe a potom sa vratit domov. 

ale isteže, nepoužila by som k tomu matematiku, nie som matematik, ale v podstate sú to veci, ktoré sa využívajú... jedna príhoda spred nesmierne mnoho rokov:

bola som malé decko, v tých časoch v rodine ešte bol zvyk robiť hodne veľké svadby, autá nemal každý mládenec, a v meste bolo zvykom prísť pekne k rodine a pozývať na svadbu osobne - predstaviť nevestu, oznámiť, že sa idú brať a osobne pozvať...

pán a dáma, ktorí k nám vtedy zaklopali, on bol veterinár, ona mladá právnička, a zobrali to pekne z gruntu: neskôr som sa dozvedela, že si popísali ulice, zavolali tetu, ktorá poznala každého, vyčlenili na to jednu sobotu poobede a jednu nedeľu poobede a peši pochodili všetkých v celom mestečku pekne podľa podobného plánu... odvtedy sme podobné plány využili už veľakrát, v menšom merítku samozrejme... v skutočnosti je to jediné rozumné riešenie, keď dobrý človek musí pochodiť hodne, účelne a za čo najkratšiu dobu  : )

 

tie vaše články sú vskutku fajn, a páči sa mi aj diskus... ale čo môj chudák bez auta? teda Agathin chudák : )

tak je fajn, aspon to nie je debata daj algoritmus a dovidenia :) urcite je to zaujimave tema, matamatika nanajvys pre zakladnu skolu, nic zlozite. nesmierna vyhoda je to ze sa to da robit aj pre naozaj vela bodov a da sa vybudovat aj k tomu algoritmus. Ludia si dnes zvykaju na cudne veci chvalia uplne kraviny, ale to co ma nejaku cenu tak to si ani nevsimnu.

pripravujem vylepsenie metod a pokus najst dokonaly algoritmus, z urcitych vylepseni jestvujucich poznatkov, ak ma niekto zaujem ten co vie programovat pomoc sa zide. Pokial sa to podari malo by to byt lepsie ako to co existuje na trhu a to urcite.

Zdá sa, že jednobunkové slizovky vedeli vyriešiť problém "Obchodného cestujúceho" už dávno. https://www.osel.cz/11507-elektronicka-hlenka-nasla-reseni-obchodniho-cestujiciho-v-rozumnem-case.html Je zaujímavé, že analógové riešenia niektorých úloh sa aj dnes ukazujú efektívnejšie, ako digitálne riešenia na superpočítačoch.   

Vrátil som sa k salesman problému. Za hodinku som urobil taký nastreľ metódy simulovaného zihania v pythone.

link na súbor:

https://github.com/robopol/Travelling-salesman-problem/blob/main/traveling_salesman_problem.py

No a táto metóda nie je zďaleka taká efektívna , povedal by som dokonca podpriemerná v tom čo očakávam ako optimálnu trasu. tak do 10 bodov to beží dobre, potom sa výsledky dramaticky zhoršujú. 100 bodov bude metóda už zla. Chcem sa tomu povenovať v budúcnosti a nájsť optimálny algoritmus na to.

PS: python verzia 3.11 už výrazne zlepšil rýchlosť. V budúcnosti hádam dobehne aj c++

robopol ma urcite opravi a doplni,  
ja si tak so vzdialenej minulosti pamatam :
Je to problem s exponecialnou zlozitostou,   sleduju sa aj rekordy, kolko bodov sa podari exaktne vyriesit ( naposledy som videl tusim cosi cez 100 tis. 
Ale ide o celkom prakticky problem pri navrhu cipov,  v praxi su preto algoritmy ktore vysledok len odhaduju ale s garantovanou odchylkou  ( chyba od idealu je menej ako 2 percenta).
https://arxiv.org/pdf/1303.6437.pdf

 

A ked budes testovat svoje riesenie, tak mas
https://neos-server.org/neos/solvers/co:concorde/TSP.html
kde je server, ktory riesi TSP.

100 tisíc bodov exaktne bude nad rámec výpočtového výkonu, ide totiž o všetky permutacie 100 tisíc bodov, čo je 100000! (faktoriál). To je nad rámec superpočítača.

pred 2 hodinami, robopol napísal:

PS: python verzia 3.11 už výrazne zlepšil rýchlosť. V budúcnosti hádam dobehne aj c++

To nie, ale ak spravne pouzivas kniznice v C, tak rozdiel nemusi byt velky.  Ale v tomto pripade mam pochyby ze to nepojde. 

pred 5 minútami, robopol napísal:

To je nad rámec superpočítača.

mozem sa mylit,  mari sa mi ze som to nedavno niekde cital,  mozno na quore ale neviem to najst. 
Ale na wiki pisu
April 2006 an instance with 85,900 points was solved using Concorde TSP Solver, taking over 136 CPU-years,

btw faktorialny cas ma len hruba sila, podla wiki je dnes najlepsi algoritmus n(exp 2) . 2exp(n). 

To sa mýliš, veď len 100 faktoriál je vysoké číslo, Ak máš nainštalovaný python tak tento jednoduchý kód simulovaného žíhania urobí "celkom dobre" 10 bodov, je podstatne horši ako moje metódy tu popísané, ktoré však vyžadujú robustný kód, teda cielenú heuristiku, ešte je možné to skúsiť cez neurónové siete, ktoré by si musel trénovať na sebe.

Ak chce niekto exe súbor, tak mu ho dodám ale simulovane žíhanie je slabé naozaj. rýchle ale slabé. dal som ho použiť na 20 bodov 1000 krát , urobil to rýchlo ale nenašiel vôbec optimálne riešenie.

ok,  tak asi  "len"  85,900.

 

85900! faktoriál random možnosti ti nevypočíta žiaden počítač v galaxii. Takže sú to len nejaké optimalizované heuristiky, je ich asi hodne ale všetky stoja za ..

100!=https://www.wolframalpha.com/input?i=100!

PS: dôležité je aj ako máš rozmiestené body, ak náhodne tak o exaktnom riešení sa môže niekomu len snívať, výpočet koľko to "zhruba" má byť pri random generovaných bodov je tiež len nejaký odhad, to sa nedá presne zistiť, veď je to kombinačná úloha predsa.

 

nie, to je exaktne riesenie.  A nerata to vo faktorialnom case.
https://en.wikipedia.org/wiki/Concorde_TSP_Solver