» »

Prikaz optimalne poti

Prikaz optimalne poti

«
1
2

libreus ::

Pozdravljeni,

pozna kdo kakšno spletno stran kamor bi vnesel cca. 250 naslovov (hišna in poštna številka) in po obdelavi podatkov prejel optimalno pot od prve do zadnje točke z vsemi vmesnimi točkami.

Hvala.

solatko ::

Zemljevidi, Michelin, google map,......
Delo krepa človeka

error7891 ::

Mislim, da je ta problem se casovno neresljiv za danasnje racunalnike.
Ali se motim?

steev ::

:|

windigo ::

Optimap za Google Maps, mislim da do 100 naslovov.

Ker gre za varianto Traveling Salesman Problema, lahko pričakuješ le bolj ali manj solidne približke ali pa omejeno število postankov.

libreus ::

Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve. :P

windigo ::

Saj je. V akademske namene lahko morda celo zastonj.
Vzameš neke prosto dostopne zemljevide z API, poiščeš naslove, izračunaš najkrajše/najhitrejše poti med vsemi točkami (v tvojem primeru 250x250 poti) in daš zadevo v reševanje recimo Concorde TSP.

Če rabiš v komercialne namene, pa malo poišči, kdo je že to naredil zate in je pripravljen to prodati kot storitev ali produkt. Za zastonj je preveč CPU intenzivno, da bi lahko pokrili s podatki ali reklamami.

Utk ::

libreus je izjavil:

Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve. :P

Narisi si na papir 10 takih točk in to reši, če si tako pameten. 10 boš pa ja zmogel na listu papirja?

DeusB ::

ARCGIS program, pač bos mogel malo preštudirat ampak gre!

https://www.arcgis.com/features/index.h...

next3steps ::

Google Maps zna računati čas poti, ker ima žnj naprav, ki mu stanje na cestah poročajo real-time.
Kako boš pa te podatke izvozil in nato reševal, je drugi problem.

libreus ::

Utk je izjavil:

libreus je izjavil:

Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve. :P

Narisi si na papir 10 takih točk in to reši, če si tako pameten. 10 boš pa ja zmogel na listu papirja?

Zares ne razumem namena tega sporočila?

Mavrik ::

libreus je izjavil:

Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve. :P


Rešitev je, ampak gre predvsem za dokaj drage pakete programske opreme namenjene poštam, kurirskim službam in ostalim logističnim družbam. Ne vem za nič zastonjskega.
The truth is rarely pure and never simple.

Jure14 ::

libreus je izjavil:

Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve. :P

Začneš v točki 1.
Kam greš iz nje? Do ene izmed preostalih 249 točk.
In kam iz te točke? Do ene izmed preostalih 248 točk.
In tako naprej.

In dobiš 249*248*247*....*4*2 možnih poti
In potem za vsako pot izračunaš dolžino in vzameš najkrajšo.

Težava je le tistih 249! možnih kombinacij.
Kar je približno 10^500 kombinacij.

Če računalnik izračuna 1000000000000000 kombinacij na sekundo (kar pa jih ne, in še dolgo ne bo), bi računanje trajalo hmmm, 10^485 sekund, kar je približno 10^478 let.

Zgodovina sprememb…

  • spremenilo: Jure14 ()

rokp ::

Utk je izjavil:


Narisi si na papir 10 takih točk in to reši, če si tako pameten. 10 boš pa ja zmogel na listu papirja?


Ce ne spremenis pogojev, z lahkoto. ;)

OrkAA ::

error7891 je izjavil:

Mislim, da je ta problem se casovno neresljiv za danasnje racunalnike.
Ali se motim?


Casovno neresljiv je, ce hoces absolutno optimalno resitev. Priblizki so pa povsem izvedljivi.

GupeM ::

Rabiš nekaj, kjer se lahko sprehajaš po grafu, ki ima uteži na povezavah med node-i. Kaj je zate optimalna pot? Čim krajši čas? Čim krajša razdalja? Čim manjša poraba goriva? Nekaj vmes? Te uteži moraš dodati na povezave, nato pa lahko z raznimi algoritmi, kot so A, A*, Dijkstra itd izračunaš. Čas reševanja bo mnogo, mnogo krajši, kot zgoraj omenjeni bruteforce uporabnika Jure14. Verjetno pa bo pri 250 node-ih še vedno predolg.

Zelo odvisno je tudi od grafa, ki ga sestaviš. Če ima graf veliko naslovov, ki so zaporedni na eni cesti, bo algoritem hitro vedel, da jih lahko najbolj optimalno obiščeš zaporedoma in ne s skakanjem naprej/nazaj ali po drugih poteh.

Utk ::

rokp je izjavil:

Utk je izjavil:


Narisi si na papir 10 takih točk in to reši, če si tako pameten. 10 boš pa ja zmogel na listu papirja?


Ce ne spremenis pogojev, z lahkoto. ;)

No dej.

Smurf ::

X--X--X--X--X--X--X--X--X--X

Gres od leve proti desni. Done. Je tudi absolutno optimalna :).

snow ::

Na zadnjem Kaggle tekmovanju kjer je bilo potrebno najti najboljse poti (za dedka mraza), so zmagovalne tri ekipe za resevanje uporabljale simulated annealing.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

krneki0001 ::

Tukaj imaš primer rešen v ruby-ju (rock band tour problem) z genetskim algoritmom.
http://archive.li/Wyq3D

Zgodovina sprememb…

  • predlagalo izbris: marvin42 ()

nodrim ::

Optimalna pot v kakšnem smislu?

rokp ::

Hvala, Smurf. Tocno tako sem mislil, ja.

marvin42 ::

krneki0001 je izjavil:

Tukaj imaš primer rešen v ruby-ju (rock band tour problem) z genetskim algoritmom.
http://archive.li/Wyq3D


Oprosti, najprej sem kliknil "predlagaj izbris" namesto citiraj.

Hotel sem samo vprašati - bi ta metoda dobro delovala na 250 mestih, kot je vprašal op?
Mostly Harmless

jernejl ::

bi ta metoda dobro delovala na 250 mestih, kot je vprašal op?

Za genetski algoritem to ne bi smel biti problem, ni pa rečeno, da bo vrnil (najbolj) optimalno pot.

Utk ::

Smurf je izjavil:

X--X--X--X--X--X--X--X--X--X

Gres od leve proti desni. Done. Je tudi absolutno optimalna :).

Ni pa na zemljevidu. Pa se to svojo trditev bi moral dokazat.

rokp ::

Ja, saj to je bilo od predpostavki, da ne spreminjas pogojev... ;)

Utk ::

Pogoji so napisani ze v odprtju teme, nic jih nisem spremenil. Samo zmanjsal tocke na ubogih 10.

noraguta ::

marvin42 je izjavil:

krneki0001 je izjavil:

Tukaj imaš primer rešen v ruby-ju (rock band tour problem) z genetskim algoritmom.
http://archive.li/Wyq3D


Oprosti, najprej sem kliknil "predlagaj izbris" namesto citiraj.

Hotel sem samo vprašati - bi ta metoda dobro delovala na 250 mestih, kot je vprašal op?

Nikakor v tem stoletju.
Pust' ot pobyedy k pobyedye vyedyot!

rokp ::

OK, pa naj bo. Poisci poljubno ravno ulico na zemljevidu, kjer so hise s stevilkami 2, 4, 6, 8, 10, 12, 14, 16, 18 in 20 ena za drugo (pazi, razdalja med posameznimi hisami niti ni nujno, da je konstantna, kot je narisal Smurf, na Zemlji moras samo toliko paziti, da ta ulica ni predolga, da ne bi po drugi strani krogle bilo blizje ;) ) . Startaj pri stevilki 2, potem jih pa obisci v vrstnem redu, kot gredo po velikosti. Ce najdes bolj optimalno varianto, ti cestitam.
Edit: Je pa res, da se tule "prepiramo" za oslovo senco... ;)

Zgodovina sprememb…

  • spremenil: rokp ()

Utk ::

Lahko tudi tako, ampak ti dokazi da si nasel optimalno pot. Jaz ne bom. Ti pravis da je lahko.

Itak si pa cist zgresil. Isce se splosna resitev, ne pa resitev enga problema, ki si si ga zase zamislu. Kot da bi reku, da je cist enostavno napisat zmagovalno sedmico. In si zavrtel zrebanje od prejsnega tedna.

Zgodovina sprememb…

  • spremenil: Utk ()

moose_man ::

Ce bos resitev programiral sam, rabis resit problem trgovskega potnika. Jaz sem to enkrat delal s Simulated Annealing algoritmom in za vec 100 po zemljevidu razprsenih lokacij dobil zelo dobre rezultate.

Zgodovina sprememb…

  • spremenilo: moose_man ()

rokp ::

Saj to ze ves cas trdim, da si ti narobe zastavil, ko si ponudil, da si nekdo na papir narise 10 tock (in ne, da najde splosno resitev za 10 tock). Ce pa hoces splosno resitev za katerihkoli 10 tock, imas pa seveda prav, je kompleksen problem, samo tega zgoraj nisi napisal (in zato ter samo zato sem trdil, da je to cisto enostavno, seveda pod predpostavko, da ne spreminjas zacetnih pogojev). Ceprav sem preprican, da se da za tocke, ki so na premici, optimalnost te resitve tudi dokaj enostavno dokazati, tega nikjer (do sedaj) ni bilo zahtevanega. Ampak, saj pravim, oslova senca.

Utk ::

Narisi si 10 tock ja, zarad mene lahko tudi v ravni crti, in pokazi postopek, po katerem bos dobil optimalno resitev. Ce si ti narises 10 tock, neko pot in reces to je to, ne, to ni to, to ni nic. Ne ves, ce je tvoja pot optimalna, samo sklepas da je.

rokp ::

Mah, na ravni crti je enostavno, ce zacnes na enem koncu. Da bo lazje, oznacimo prvo hiso z 0, drugo z 1, tretjo z 2, itd. in so hkrati to tudi oddaljenosti od prve hise (v poljubnih enotah). Do desete hise je najkrajsa razdalja 9 (pa ne mi sedaj s kaksnimi neevklidskimi). Ce zelis priti od prve do desete (ne glede na to, ali vmes obisces se kaksno drugo ali ne), moras torej prehoditi minimalno 9 enot (ker krajse poti ni). Ce se spotoma pri vsaki hisi se ustavis in potem nadaljujes, se ta razdalja nic ne podaljsa. Ce katerokoli preskocis, se moras potem vrniti do nje. Ker je katerakoli taksna razdalja (kjer se vracas), vecja od nic, se vsota kvecjemu poveca, zmanjsati se ne more. QEMM ;)

Ampak ja, glede na ukrivljenost Zemlje, tudi ta pot po povrsini ni optimalna, bi se dalo vse skupaj se malo "poglihati", se strinjam.

krneki0001 ::

noraguta je izjavil:

marvin42 je izjavil:

krneki0001 je izjavil:

Tukaj imaš primer rešen v ruby-ju (rock band tour problem) z genetskim algoritmom.
http://archive.li/Wyq3D


Oprosti, najprej sem kliknil "predlagaj izbris" namesto citiraj.

Hotel sem samo vprašati - bi ta metoda dobro delovala na 250 mestih, kot je vprašal op?

Nikakor v tem stoletju.


Zakaj ne? Na starejšem i7 procu algoritem dela za teh 15 mest kako sekundo (pa je verjetno izpis tisti, ki največ požre), za 250 bi pa par ur ali dni, ampak naredil bi.

Se bom danes malo poigral.

rokp ::

Verjetno si ne predstavljas, kako hitro raste n!

</head> ::

Ne samo verjetno. Očitno.

moose_man ::

Ce komu ta podatek prav pride: sel sem gledat v svoje zapiske od starega projekta (glej moj prejsnji post), ki sem ga delal leta nazaj. Optimalno pot med 7000 kraji mi je Simulated Annealing izracunal v manj kot uri in to na precej povprecnem laptopu. Sel sem pogledat tudi kaksno kodo sem pisal takrat (jezik C), in vidim, da je nisem nic kaj veliko optimiziral. V zapiskih sem si se zacrtal graf z izmerki, kako hitro raste casovna zahtevnost algoritma s preverjanjem vseh kombinacij v primerjavi z annealingom ... mind blown. Med 6 in 12 kraji je casovna poraba greedy algoritma poskocila za vec redov velikosti, casovna poraba annealinga pa niti za enega.

Zgodovina sprememb…

  • spremenilo: moose_man ()

krneki0001 ::

Enkratno delo (to bo pobralo največ časa):
1.) Nabereš vseh 250 GPS točk.
2.) Izračunaš poti med točkami in jih ovrednostiš glede na dolžino in čas poti
3.) Postaviš to v pravilno matriko 250x250

Vse kar še ostane je računanje na grafiki. Recimo TPS on CUDA https://github.com/slowr/TSP-Cuda

moose_man je izjavil:

Ce komu ta podatek prav pride: sel sem gledat v svoje zapiske od starega projekta (glej moj prejsnji post), ki sem ga delal leta nazaj. Optimalno pot med 7000 kraji mi je Simulated Annealing izracunal v manj kot uri in to na precej povprecnem laptopu. Sel sem pogledat tudi kaksno kodo sem pisal takrat (jezik C), in vidim, da je nisem nic kaj veliko optimiziral. V zapiskih sem si se zacrtal graf z izmerki, kako hitro raste casovna zahtevnost algoritma s preverjanjem vseh kombinacij v primerjavi z annealingom ... mind blown. Med 6 in 12 kraji je casovna poraba greedy algoritma poskocila za vec redov velikosti, casovna poraba annealinga pa niti za enega.


Kakšne podatke si pa imel (kako si ovrenotil poti med eno in drugo točko? Samo razdaljo med krajema? razdaljo + čas ali razdaljo + čas + cena prevoza?

Zgodovina sprememb…

moose_man ::

Edini kriterij je bila cim manjsa razdalja med dvema točkama na sferi: Great-circle distance @ Wikipedia

Moji vhodni podatki so bile GPS koordinate. Razdalje med mesti sem računal kar sproti. Se mi zdi, da bi bil problem veliko težji, če bi bile vmes ceste, ampak za nekaj 100 krajev z neprevelikim omrežjem cest med njimi se mi problem zdi še vedno obvladljiv (ampak lahko da tule zelo podcenjujem kompleksnost tega problema).

Tole je rezultat za cca 500 mest. Shranjen mam tudi graf za 7000, ampak ni tako pregleden kot tale:

 travelling salesman

travelling salesman

Zgodovina sprememb…

  • spremenilo: moose_man ()

moose_man ::

Shranjen mam tudi graf za 7000 lokacij, glej spodaj. Mislim pa da si precej teh lokacij deli iste GPS koordinate, ocenite sami. Na zalost se ne spomnim podrobnosti o podatkih ki sem jih takrat obdeloval. :)

 salesman 7000 data points

salesman 7000 data points

Zgodovina sprememb…

  • spremenilo: moose_man ()

jernejl ::

Ce komu ta podatek prav pride: sel sem gledat v svoje zapiske od starega projekta (glej moj prejsnji post), ki sem ga delal leta nazaj. Optimalno pot med 7000 kraji mi je Simulated Annealing izracunal v manj kot uri

Trgovski potnik je NP-težek problem.

Si prepričan, da si dobil optimalno pot?

Zgodovina sprememb…

  • spremenil: jernejl ()

moose_man ::

Po vseh teh letih tega ne morem trdit zagotovo. :) In uporabil sem izraz optimalna pot, kar je zavajujoče: reči bi moral zame sprejemljiv približek optimalne poti.

Moje rezultate sem prilepil bolj kot vzpodbudo, da se nekaj da dosečt in da je vredno sprobat. To, kako dober približek pa OP rabi, pa bo seveda vedel le on sam. :)

borisk ::

mi smo se s tem igrali na faxu, uporabljali smo majhno skripto za autocad (ne vem zakaj smo uporabljali to, verjetno zaradi tega ker sem bil na strojnem faxu). Uporablaji smo mislim da genetski algoritem, in potem spustili ne vem, 1000generacij, 5000generacij, in primerjali hitrosti, kdaj smo dobili točno ali dovolj točno rešitev v odvisnosti od stopnje mutacij in križanj. če mutacije ni bilo dovolj, kolonija ni znala priti iz lokalnega optimuma. mi smo sicer reševali probleme, za katere so bili znane točne rešitve, če pa tega nimaš, ne moreš biti nikoli prepričan da si v globalnem optumumu.


https://www.fmf.uni-lj.si/~skreko/Pouk/...

krneki0001 ::

Ali ste uporabljali swarm algoritem (ant colony algoritem)?

Tukaj je kar nekaj razloženih algoritmov
http://www.cleveralgorithms.com/nature-...

Razloženi so besedno, s pseudo kodo in potem še narejeni v ruby-ju.
Nekatere izmed njih sem še dodatno optimiziral (ko sem še na faks ob delu hodil), so pa v večini prišli prav na vajah, da sem po pseudo kodi lahko potem v C ali C++ napisal algoritem.

Zgodovina sprememb…

krneki0001 ::

Tukaj je pa ena dobra rešitev TPS z ant colony algoritmom:
https://www.codeproject.com/Articles/54...

borisk ::

bi moral pogledati če imam kakšne zapiske, je pa bil to majhen izbirni predmet (genetske in evolucijske metode v strojništvu) mislim da 30 ur vse skupaj. Glede na to da nismo imeli neke podlage v programiranju, smo se samo seznanili z različnimi metodami, in naredili nekaj testov z že sprogramiranimi skriptami, samo parametre smo spreminjali.

libreus ::

Hvala za zanimive perspektive in poglobljeno debato ... Ena dobra variatna je tudi: https://www.multiroute.de/. Sicer v free verziji omogoča manj točk, ampak najde optimalno pot.

Zanimalo me je pa glede free rešitev. Batchgeo (https://batchgeo.com/) ti omogča vnos točk na zemljevid, potrebujem še zaporedje z npr. najkrajšo potjo.

Potreboval bi pa zaporedja za več področij. Področij/okrajev imam nekaj okoli 600. To pomeni, da bi za vsako od 600-tih okrajev imel zaporedje, ki bi ga nato vnesel v program in bi izpisoval naslove glede na zaporedje izračunane poti/obhoda.

borisk ::

@nebivedu
ja, mislim da smo imeli mravlje, nekaj sto kolonij, vsaka naslednja generacija je uporabila prejšno generacijo + križanje + mutacije. Zanimivo je, ko smo v živo spremljali rezultate posameznih kolonij, ko začne kakšna kolonija delati bisten napredek, eksponentno dobiva prednost pred ostalimi (če se ne zacikla v kak strm lokalni optimum iz katerga ne more priti.

krneki0001 ::

Ja, mravlje so za take zadeve odlične.

libreus, programiraš?
Ker gor imaš link do primera narejenega v VS.
«
1
2


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

IBM predstavil najzmogljivejši kvantni računalnik (strani: 1 2 )

Oddelek: Novice / Znanost in tehnologija
5615703 (12099) 7982884e
»

Koliko racunalnistva zares potrebujete v sluzbi?

Oddelek: Loža
102202 (1275) noraguta
»

Nov kvantni računalnik D-Wave 2X hitrejši od klasičnih

Oddelek: Novice / Znanost in tehnologija
2316550 (13348) Qushaak
»

algoritm za pot med dvema točkama

Oddelek: Programiranje
161343 (1036) detroit
»

Prejemniki Ig Nobelovih nagrad 2010

Oddelek: Novice / Znanost in tehnologija
95252 (4086) Spy

Več podobnih tem