Forum » Loža » Prikaz optimalne poti
Prikaz optimalne poti
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.
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.
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.
Ker gre za varianto Traveling Salesman Problema, lahko pričakuješ le bolj ali manj solidne približke ali pa omejeno število postankov.
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.
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 ::
DeusB ::
ARCGIS program, pač bos mogel malo preštudirat ampak gre!
https://www.arcgis.com/features/index.h...
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.
Kako boš pa te podatke izvozil in nato reševal, je drugi problem.
libreus ::
Mavrik ::
Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve.
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 ::
Točno to. Se pa čudim, da z današnjo tehnologijo ni na voljo rešitve.
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 ::
OrkAA ::
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.
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 ::
Smurf ::
X--X--X--X--X--X--X--X--X--X
Gres od leve proti desni. Done. Je tudi absolutno optimalna :).
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
http://archive.li/Wyq3D
Zgodovina sprememb…
- predlagalo izbris: marvin42 ()
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 ::
Utk ::
Pogoji so napisani ze v odprtju teme, nic jih nisem spremenil. Samo zmanjsal tocke na ubogih 10.
noraguta ::
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... ;)
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.
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.
Ampak ja, glede na ukrivljenost Zemlje, tudi ta pot po povrsini ni optimalna, bi se dalo vse skupaj se malo "poglihati", se strinjam.
krneki0001 ::
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.
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
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?
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
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…
- spremenilo: krneki0001 ()
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:
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
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
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. :)
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/...
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.
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…
- spremenilo: krneki0001 ()
krneki0001 ::
Tukaj je pa ena dobra rešitev TPS z ant colony algoritmom:
https://www.codeproject.com/Articles/54...
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.
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.
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.
libreus, programiraš?
Ker gor imaš link do primera narejenega v VS.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | IBM predstavil najzmogljivejši kvantni računalnik (strani: 1 2 )Oddelek: Novice / Znanost in tehnologija | 19319 (15715) | 7982884e |
| » | Koliko racunalnistva zares potrebujete v sluzbi?Oddelek: Loža | 2524 (1597) | noraguta |
| » | Nov kvantni računalnik D-Wave 2X hitrejši od klasičnihOddelek: Novice / Znanost in tehnologija | 17187 (13985) | Qushaak |
| » | algoritm za pot med dvema točkamaOddelek: Programiranje | 1689 (1382) | detroit |
| » | Prejemniki Ig Nobelovih nagrad 2010Oddelek: Novice / Znanost in tehnologija | 5910 (4744) | Spy |