Problém obchodný cestujúci

Začal som riešiť problém obchodného cestujúceho, kto ma záujem moze kuknut uvodne članky:

https://robopol.blogspot.com/2018/07/obchodny-cestujuci.html

https://robopol.blogspot.com/2018/07/problem-obchodneho-cestujuceho-1-diel.html

http://robopol.blogspot.com/2018/07/problem-obchodny-cestujuci-2-diel.html

tento problem hodlam vyriesit max do konca roka, je okolo toho dost roboty to vsetko popisat

len pridavam, priblizne algoritmy su uspesne a bezne sa pouzivaju. napriklad pri osadzovani plosnych spojov. do poctu cca 10 tis bodov maju uspesnost asi 98 percent.

tak budem dalsi co najde alebo priblizny algoritmus alebo velmi presny pre obecny problem hustej siete rozne rozmiestnenych bodov, taky algoritmus si potom moze naprogramovat kto bude chciet.

som ta nechcel odradzat, naopak      https://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/    odkaz na benchmark,  ak budes mat algoritmus, tak si mozes overit nakolko je dobry

ja uz ten algoritmus mam v hlave, ide o to ho len popisat a dat mu jasne pravidla, nemam pocit ze ho budem niekedy programovat aby som overil jeho silu, bude v podstate jednoduchy, navyse je to prirodzene, ked som sa na to kukal prvy krat na ten problem prislo mi prirodzene riesenie rychlo. A ucinnost sa mi vidi ta najlepsia mozna, len to chvilu potrvaa kym to naklepem do finalnej podoby. Zaroven ho nejdem predavat, takze nebudem ho schovavat, budes ho mat k dispozicii aj ty na testy, mne sa s tym az tak hrat nebude chciet.

A je taký univerzálny algoritmus vôbec možný?

Trochu.. Niečo mi na tom pripomína "sedem mostov Königsbergu"..

A to že sa jedná o neriešiteľnú úlohu, dokázal už Euler..

...

Hmm.. Asi by tam bolo potrebné pridať nejaké "racionalizačné" opatrenie, pre prípad keď v "teréne" nastane situácia "siedmich mostov"..

Ale neviem ako by v praxi vypadalo..

je mozny urcite algoritmus ktory najde skoro dokonalu trasu, ale milion nedostanes za algoritmus ale dokaz ze je najlepsi mozny, alebo ze neexistuje algoritmus ktory vzdy najde dokonalu trasu, ale to je bezpredmetne tam nech sa hraju akademicki matematici na tomto policku..

alamo, toto je klasicky np problem, je urcite mozne vyskusat vsetky moznosti a vybrat optimum. len zlozitost rastie prilis rychlo. uloha je teda najst algoritmus ktoreho cas rastie s mocninou poctu vrcholov a nie faktorialom. alebo dokazat ze taky nie je. pre prakticke pouzitie uz existuju algoritmy ktore su take a ajvieme aka bude ich maximalna odchylka.

ale pre srandu tyso , povedz napr. milion bodov potrebujes spojit, ako vedia aka je optimalna draha teda dokonala? nevedia, vedia priblizne aka je dokonala draha, zaujima ma ako dlho trva napr. nejakepu pocitacu vyopcet tejto cesty, lebo co robim algoritmus tak to urobi velmi rychlo, ani nemrknes brvou.

Inak ten problém "obchodného cestujúceho" je dosť akútny, s ohľadom na všemožné projekty zdieľania automobilov..

V praxi je to zložitejšie o problém "spiatočnej cesty", keď "obchodný cestujúci" vykoná úlohu, musí sa vrátiť domov aby sa pripravil na ďalšiu "štreku".

Čiže cesta sa začína v bode X, a nakoniec sa musí v bode X aj skončiť..

Problémy to robí napríklad pri kontajnerovej doprave, keď sa musia pravidelne presúvať prázdne kontajnery, a doprava prázdneho kontajnera aby mohol byť znovu naplnený, sa dá pokladať za "stratu".

Pri tých zdieľaných automobiloch, zase pravidelne nastane situácia, že niekto si požičia auto, cestuje ním niekam kde "líšky dávajú dobrú noc" a auto tam zostane "visieť", bez možnosti nájsť zákazníka na spiatočnú cestu..

V praxi teda nejde iba o najkratšiu cestu z bodu A do bodu B.

alamo,  to su modifikacie problemu.

Aktualny stav :   http://www.math.uwaterloo.ca/tsp/world/     

 rieseny problem cez vsetky mesta na svete    ktorych je 1,904,711

The best reported tour for the World TSP was found by by Keld Helsgaun using a variant of his LKH heuristic algorithm. The tour of length 7,515,772,107 was found on March 13, 2018

Stale to nie je optimum,   maximalna odchylka od optima je 0.0474%.

Pre presne riesenia je hranica vyrazne nizsia,  ale neviem najst aka.  Pred par rokmi bol svetovy rekord okolo 60 tis bodov.

dnesny stav heuristik je  priblizne  N exp 2 ,     pre 100 miest ide o sekundy. 

A  na otazku robopola,    pre algoritmus sa vacsinou da urcit aka je maximalna mozna odchylka od optima, ale  okrem toho su dalsie algoritmy ktore ju vedia odhadnut presnejsie.  Presne ako netusim, ale su to odhady zalozene na trojuholnikovych nerovnostiach.

tyso

To je síce pekné.

Ale v praxi sa ti "mapa" dynamicky mení v čase, doslova z minúty na minútu. Máš mapu "terénu", a mapu "zákaziek".

Máš "zemepis" mapu na ktorej sú mestá A,B,C,D..

A v tých mestách sú zákazníci, ktorý potrebujú prepravu zákazky 1. z A do B, zákazku 2. z B do C, zákazku 3. C do A..

Fajn ideálny stav..

Pošleš na trasu kamión.. Keď je na polceste, zazvoní ti telefón a zadávateľ zákazky v B ti oznámi že ju stornuje, lebo "medveď" alebo hocičo iné..

A to je ten najjednoduchší príklad dynamickej zmeny, občas premenlivej ako to "počasie"..

alamo,  a otazka ?   pri beznej firme vypocitat novu trasu je otazka sekund, 

tieto algoritmi su ale neuveritelne zatazujuce vypoctovy vykon, pre 100 bodov najdem riesenie aj ja do par sekund, keby som mal take rychle ruky a mysel tak to urobi skor ako ta heuristicka metoda. Ale podstatne je to ze taky algoritmus mozu pouzivat ludia aj bez strojov pre nejaky rozumny pocet bodov, netreba na to pocitace, co je fajn, ze to nerobim zbytocne.

https://robopol.blogspot.com/2018/07/zopar-skvostov.html

je to aj dobra zabavka na relax miesto sudoku :)

No algoritmus by mal byt hotovy, teraz to len vsetko popisat, algoritmus bude obsahova:

1. systemové riesenie podla ktoreho bude postupovat

2. hrubu silu v lokalnych miestach kde nie je mozne urcit optimalnu cestu, hruba sila ale bude eliminovana obecnymi pravidlami ktore platia. hruba sila bude vyuzivana do 10 az 20 uzlov max.

3. bude vyuzivat aj pravdepodobnost istych rieseni, ktore su viac pravdepodobne ako optimalne.

celkovo to proces neuveritelne zrychli, chyba bude minimalna v optimalnej ceste, urcite to bude konkurent v rychlosti, pouzitelnost aj pre cloveka vyriesi problem skor ako zapne program a nadefinuje siet bodov.

Neviem kde to dať.. (Tak aby som nezakladal novú tému.. A mám "ciťák" akejsi súvislosti..)

https://motls.blogspot.com/2018/07/aaronsons-teenage-student-amazingly.html?m=1

Ide vlastne o "tvorbu algoritmov"..

Nejaký študent, nejak nakrkol pána profesora.. A trochu "znemožnil" kvantové počítače..

Ale čo to vlastne? Ako?

Tak konecne som sa dokopal k napisaniu rieseni

https://robopol.blogspot.com/2018/09/obchodny-cestujuci-3-diel.html

tak nejake noazory postrehy? Ak ma niekto zaujem z tychto informacii zostavit alagoritmus vramci zabavy nech sa ozve.

No tak som sa troska pozrel na tie heuristicke algoritmy no u informacii na nete moc mudry z toho nie som. Naiel som nieco napr. taketo : http://www2.fiit.stuba.sk/~pospichal/case_studies06/Peter_Ledna_evol_alg.pdf

Pre tvorbu algoritmu sa budú dat vyuzit niektore závery z clankov u mna, no vysledny funkcny algoritmus bude zrejme celkom nieco ine ako ked to riesi clovek ktory nema milinony pokusov na najdenie optima. Tak dufam, ze aspon tono sa o to zacne troska zaujimat, lebo je to zaujimava tema s velkym vyuzit, teda heuristicky algoritmus.

Mne pride, ze zatial riesis skutocne len tie najjednoduchsie pripady, ked mas niekolko hlucikov bodov, ktore su priblizne rovnako od seba. To skutocne nie je problem riesit na papiery.

Problem obchodenho cestujuceho je zlozity, ked to takto nemas. Zober si napriklad slepu mapu europy a zaznac si do nej hlavne mesta. Ktore casti budes cik-cakovat a ktore pojdes priamo? 

To su prave tie situacie, ktore clovek nevie dostatocne dobre vyriesit, pretoze aj na najdenie nejakeho lokalneho minima je potreba nejakej tej hrubej sily.

Daj obrazok, nie je to iba pre jednoduche pripady, cielom bolo urobit to aj pre ludi nie len pre pocitace, pocitac moze robit x slepych stratenych variant clovek si to dovolit nemoze. v calnku myslim v trcoch dieloch u mna su vsetky podstatne vlastnosti uvedene aj suvislosti. Je tam aj metoda, ktorá prave eliminuje stratene vetvy, samozrejme, ze to nie su pravidla ktore sa zaobidnu bez hrubej sily v zlozitejsich pripadoch asymetrickych, dalsia vec nesluzi to len pre dopravu.

K algoritmom. Zatial co mi cas dovolil som si presiel tak na hrubo ake su algoritmy v com je ich vyhoda v com nie. Nie su uplne, neprehladavaju vsetky moznosti ale iba tie co sa javia ako ze su v danej mnozine hladani. Takze na poli algoritmov su tiez moznosti ako vyrobit nejaky iny. Z clankov na zaklade metod cik caku by sa dal tiez vytvorit algoritmus ktory najde hrubu cestu alebo zopar hrubych ciet a doplnykovy algoritmus najde lokalne minimu tejto kostry cesty.

druha moznost je pouzit existujuce algoritmy len ich pozmenit ci k nim pridat vlastnost ktora je uzitocna a je u mna popisana. Blizsie o tom nejdem pisat.

dalsia moznost je hladat dokonaly algoritmus ak taky je, co chcem tiez troska zbehnut pretoze ak existuje, teda algoritmus ktory neprehladava vsetky cesty iba z mnoziny v ktorej ked existuje ma vlastnosti ktore som nevidel zatial v sposoboch jestuvujucich algortitmov.

Tu mas mapu europskych hlavnych miest:

cielom bolo urobit to aj pre ludi nie len pre pocitace, pocitac moze robit x slepych stratenych variant clovek si to dovolit nemoze.

K algoritmom. Zatial co mi cas dovolil som si presiel tak na hrubo ake su algoritmy v com je ich vyhoda v com nie. Nie su uplne, neprehladavaju vsetky moznosti ale iba tie co sa javia ako ze su v danej mnozine hladani. Takze na poli algoritmov su tiez moznosti ako vyrobit nejaky iny.

Aha a to je velka mnozina? Nuz neviem co dodat ale taketo veci sa riesia hrubou silou teda uplnym algoritmom ktory najde uplnu minimalnu cestu. No fajn to co je obecne zname pisat nemusis, ja som napisal sposob pre ludi ak si na nieco zaujimave prisiel kde to nebude fungovat dobre mozes ukazat. nejde len o samotny cik cak, su tam predsa vypisane vlastnosti ktore musis brat v uvahu. Vyberam v podstate jeden strom z moznych ciest ktory sa javi, ze bude blizko optima, ked si myslis opak tak budem rad ked nieco konkretne aj povies. A tvoje mesta z mapy sa daju riesit touto metodou aj pre cloveka.

Ved to mozme otestovat, skus podla tvojich metod vyriesit tuto mapu a ja skusim pomocov nejakeho hladacieho algoritmu. A uvidime, ako velky je rozdiel. A aby to nebolo voci ludskej metode skutocne nefer, tak mozem vo volnom case mapu preniest do grafu. Nech su jasne dane body a vzdialenost. Ono, ratat great circle vzdialenosti zo zemepisnej sirky a dlzky tiez nie je pre cloveka zrovna sranda ;)