Skočiť na obsah


Fotografia
* * * - - 1 Hlasov

Problém obchodný cestujúci

matematika

  • Prosím prihláste sa ak chcete odpovedať
Téma má 16 príspevkov

#1 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 23. júl 2018 - 17:16:55

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

https://robopol.blog...-cestujuci.html

https://robopol.blog...eho-1-diel.html

http://robopol.blogs...uci-2-diel.html

 

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


  • 0

#2 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5 493 príspevkov
  • 1 tém

Príspevok bol napísaný: 23. júl 2018 - 18:29:42

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

#3 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 23. júl 2018 - 18:46:59

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.


  • 0

#4 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5 493 príspevkov
  • 1 tém

Príspevok bol napísaný: 23. júl 2018 - 21:40:14

som ta nechcel odradzat, naopak      https://comopt.ifi.u...e/TSPLIB95/    odkaz na benchmark,  ak budes mat algoritmus, tak si mozes overit nakolko je dobry


  • 0

#5 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 24. júl 2018 - 07:50:23

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.


  • 0

#6 alamo

alamo

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 008 príspevkov
  • 110 tém

Príspevok bol napísaný: 24. júl 2018 - 09:20:27

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

#7 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 24. júl 2018 - 09:35:51

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


  • 0

#8 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5 493 príspevkov
  • 1 tém

Príspevok bol napísaný: 24. júl 2018 - 09:54:42

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

#9 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 24. júl 2018 - 09:58:57

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.


  • 0

#10 alamo

alamo

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 008 príspevkov
  • 110 tém

Príspevok bol napísaný: 24. júl 2018 - 10:04:54

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

#11 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5 493 príspevkov
  • 1 tém

Príspevok bol napísaný: 24. júl 2018 - 10:46:36

alamo,  to su modifikacie problemu.

 

 

Aktualny stav :   http://www.math.uwat...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.


  • 0

#12 alamo

alamo

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 008 príspevkov
  • 110 tém

Príspevok bol napísaný: 24. júl 2018 - 11:11:37

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

#13 tyso

tyso

    Vice Admiral

  • Advanced Members
  • PipPipPipPipPipPipPipPip
  • 5 493 príspevkov
  • 1 tém

Príspevok bol napísaný: 24. júl 2018 - 11:20:25

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


  • 0

#14 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 24. júl 2018 - 16:14:32

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.


  • 0

#15 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 24. júl 2018 - 19:00:04

https://robopol.blog...r-skvostov.html

 

je to aj dobra zabavka na relax miesto sudoku :)


  • 0

#16 robopol

robopol

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 615 príspevkov
  • 11 tém

Príspevok bol napísaný: 25. júl 2018 - 08:23:10

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.


  • 0

#17 alamo

alamo

    Rear Admiral

  • Advanced Members
  • PipPipPipPipPipPipPip
  • 4 008 príspevkov
  • 110 tém

Príspevok bol napísaný: 1. august 2018 - 14:34:37

Neviem kde to dať.. (Tak aby som nezakladal novú tému.. A mám "ciťák" akejsi súvislosti..)
https://motls.blogsp...zingly.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?
  • 0





Podobné témy pre kľúčové slovo: matematika

0 člen(ov) číta túto tému

0 členov, 0 návštevníkov