Jump to content

Problém obchodný cestujúci


Recommended Posts

robopol

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

Link to post
Share on other sites

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.

Link to post
Share on other sites
robopol

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.

Link to post
Share on other sites
robopol

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.

Link to post
Share on other sites

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

Link to post
Share on other sites
robopol

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

Link to post
Share on other sites

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.

Link to post
Share on other sites
robopol

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.

Link to post
Share on other sites

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.

Link to post
Share on other sites

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.

Link to post
Share on other sites

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

Link to post
Share on other sites
robopol

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.

Link to post
Share on other sites
robopol

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.

Link to post
Share on other sites
  • 1 month later...

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.

Link to post
Share on other sites

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.

  • Upvote 1
Link to post
Share on other sites

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.

Link to post
Share on other sites

Tu mas mapu europskych hlavnych miest:

post-32-0-69256700-1537198811_thumb.jpg

 

 

 

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

To je bohuzial natura vacsiny takychto problemov, preto na to mame pocitace.

 

 

 

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.

Napisat algoritmus, ktory prehladava cely strom moznosti (ci uz do sirky, alebo do hlbky) vobec nie je problem. A prave s takymi algoritmami sa zacina na skolach, aby sa ukazala komplexita problemu a nutnost pouzit nejake "chytrejsie" algoritmy, ktore vedia lepsie eliminovat slepe ulicky a v akceptovatelnom case prist k nejakemu vhodnemu lokalnemu minimu.
Link to post
Share on other sites

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.

Link to post
Share on other sites

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 ;)

Link to post
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
  • Similar Content

    • robopol
      By robopol
      O rôznych témach, oblastiach matematiky, problémoch príkladoch.
      Niečo málo k teorii čísiel:
      - malá Fermatova veta: https://robopol.sk/blog/mala-fermatova-veta-prvocisla-5-diel
      - vylepšená Fermatova veta: https://robopol.sk/blog/vylepsene-hladanie-prvocisiel2diel
      -Riemanova hypoteza: https://robopol.sk/blog/prvocisla-riemannova-hypoteza-2-diel
      -Pseudoprvočísla: https://robopol.sk/blog/prvocisla-golden-part
      - Špeciálne prvočísla:https://robopol.sk/blog/specialne-prvocisla
      - najväčšie prvočísla: https://robopol.sk/blog/najvacsie-prvocisla
      - Mobiova funkcia. Eulerova veta a funkcia: https://robopol.sk/blog/eulerova-veta-a-funkcia-möbiova-funkcia
       
       
    • Pipa
      By Pipa
      Ahojte :) potrebovala by som poradiť s jednou úlohou z VŠ matematiky s ktorou si neviem poradiť. Ak by sa našiel niekto, tak rada ju rada pošlem na email. Ďakujem :)
    • game
      By game
      keď máte podobný "príklad", pridajte ho do témy, skúsime sa s ním popasovať :)
       
       
      dnes mi prišlo mailom :
       
       
      Ahojte,
       
      mala uloha aby ste sa trosku rozhybali
       
      Do prílohy sa dostanete, ak správne vyriešite úlohu.
       
      V autobuse je 7 dievčat, každé dievča má 7 tašiek. V každej taške je 7
      veľkých mačiek, každá veľká mačka má 7 mačiatok.
      Všetky mačky majú 4 nohy.
      Otázka: koľko nôh je v autobuse. Výsledný počet nôh je heslom k súboru v
      prílohe...:-)
       
      Nie je tam žiadny chyták, iba jednoduchá matematika....
       
       
      sú tri možnosti : alebo je to len haluz, a žiadna príloha tam nebude, alebo nevie počítať ten, kto to zadal, alebo ja :)
       
       
      edit: počítala som to niekoľkokrát, a počítala som aj s možnými chytákmi :)
    • robopol
      By robopol
      Už dávnejšie som narazil na jeden zaujímavý problém v spojitosti mohutnosti nekonečna. Mohutnosť nekonečna prirodzených čísiel je definovaná ako alef 0. Mohutnosť nekonečna realnych čísiel je definovana ako alef 1. Dalej sa v matematike tvrdí, že neexistuje bijekcia medzi množinou prirodzených a realnych čísiel z dôvodu väčšej mohutnosti nekonečna realnych čísiel.
       
      Zoberme si interval 0-1. Je to úsečka o velkosti 1 cm. Vieme, že každé číslo v tomto intervale sa dá zaznačiť ako "bod" s presnou polohou od začiatku "0".
       
      ak takto označíme každý takto vynesený bod celým číslom, pričom body budeme vynášať tak, že každý interval rozdelíme na dve polovice a tam vynesieme bod, tak postupným delením intervalov budeme zapĺňať takýto interval bodmi, ktoré reprezentujú čísla na tom intervale.
       
      Takýmto neustálym delením v limite zaplname celý interval bodmi, ktoré reprezentujú reálne čísla. Každému takému bodu priradimé jedno prirodzené číslo. Pokial by sme uznali, že výsledkom takéhoto delenia je nekonečný počet bodov na našom intervale, limitne by sme mali tvrdiť, že sme obsiahli všetky body na intervale. Tie body reprezentuju realne čísla z toho intervalu.
       
      No podľa matematiky sa tvrdí, že stale existujú čísla, ktoré sme neobsiahli. Ako príklad uvediem transcendentné číslo pi, či e.
       
      Cantorova diagonala:
      spočíva v tom, že majme takýto predpis priradovania čísiel:
      1-1
      1,1-2
      1,11-3
      1,111-4
      atd.
       
      ako vidiet minieme všetky prirodzené čísla na takéto priradenia pričom napr. čislo 1,2 nikdy nedosiahneme. Z čoho následne dedukujú, že nemôžeme priradiť všetkým reálnym číslam práve jedno prirodzené číslo.
       
      Ak však zvolíme iný spôsob priradzovania (pre zjednodušenie rozdelíme úsek medzi číslami na 10 rovnakých dielikov - v zmysle 10 sústavy) tak môžeme vytvoriť takéto priradzovanie:
      1-1
      1,1-2
      1,2-3
      1,3-4
      ....
      2-11
      1,11-12
      1,12-13
      1,13-14
      ...
      1,21-22
      1,22-23
      1,23-24
      ...
      1,3-31
      1,31-32
      1,32-33
      ...
      atd
       
      Tu sme našli postupnosť kde nebude chýbať ani jedno číslo v zápise 10 sústavy, ktoré by neležalo na tomto intervale. Čo vedie k opačnému záveru v matematike, že nemôžeme priradiť všetkým reálnym číslam z nejakého intervalu 1-2 práve jedno celé číslo.
×
×
  • 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