Re: [osm-hu] Kínai postások az OSMben
Gábor Kovács
kovacsgabor55 at gmail.com
2014. Jún. 16., H, 16:59:54 UTC
Üdv szerintem egészen biztos, hogy van már rá meglévő algoritmus
http://web.alt.uni-miskolc.hu/anyagok/logrend1/jarattervezes.pdf már ha
csak a járattervezésre rákeresek googlében akkor elég sok anyagot dob ki rá.
2014. június 16. 19:03 írta, <osm at igor2.repo.hu>:
>
>
> On Mon, 16 Jun 2014, Bihari Kristóf wrote:
>
> Hello,
>> Hallott már esetleg valaki kínaipostásprobléma-megoldóról OSM-re? Ha nem,
>> akkor mennire lenne vajon bonyolult megcsinálni egy olyan
>> webservicet/JOSM-plugint/stb, ami egy adott területen (pl. településhatár)
>> belüli összes útra készít egy (közel) optimális (legrövidebb) bejárást
>> (megadott kezd?ponttal), amely minden utcát legalább egyszer érint? (Ez
>> lenne
>> a híres kínaipostás-probléma.)
>> Egy adott, m?holdról jórészt berajzolt hely felszíni felméréséhez baromi
>> jól
>>
>> jönne.
>> Ha még nincs ilyen, mennyire lenne bonyolult csinálni egy ilyet? Van elvi
>> akadálya? Ha jól sejtem, az utcákból súlyozott/irányított gráfot csinálni
>> nem lehetetlen, max. a futási id? nem lehet kevés, ha nincs a
>> bruteforce-nál
>> jobb algoritmus...
>>
>> Minden gondolat (h?, tök jó lenne/hú, baromság/ejha, meg is
>>
>> csinálom/lehetetlen, hacsak nincs hozzáférésed a Cray Titanhez/stb)
>> érdekel.
>>
>
>
> Ez nagyban fugg attol, hogy mennyire terhetsz el az optimalistol. Lehet
> csinalni kb trivialis megoldast, ami nagyon gyorsan le is fut, csak sok
> utcan egynel tobbszor atvisz, tehat feleslegesen gyalogoltat. Tehat ha csak
> az a feladat, hogy mindenhol jarjal, de nem erdekel, hogy hany ezer plusz
> kilometert gyalogoltat...
>
> Jobb megoldashoz az angol nyelvu wikipedia cikknel erdemes kezdeni.
>
> Nem tudom, hogy mennyire sok utat tudsz bejarni egy alkalommal, de ha
> olyasmi nagysagrendet, mint amire gondolok, akkor az eleg kicsi hozza, hogy
> olcsobb legyen kezzel talalni egy kozel optimalis megoldast. Ez sokkal jobb
> a fenti trivialis megoldasnal viszont nem kell ennyit kodolni hozza, mint
> az igazi megoldashoz, cserebe valoszinuleg kicsi grafon nem lesz sokkal
> rosszabb annal.
>
> Udv,
>
> Igor2
>
>
> --
> Magyar OSM Levelezőlista - openstreetmap-hungary at googlegroups.com
> leiratkozás: openstreetmap-hungary+unsubscribe at googlegroups.com
> --- Azért kapta ezt az üzenetet, mert feliratkozott a Google Csoportok
> szolgáltatásbeli openstreetmap-hungary csoportra.
>
> Az erről a csoportról és az ahhoz kapcsolódó e-mailekről való
> leiratkozáshoz küldjön egy e-amailt a(z) openstreetmap-hungary+
> unsubscribe at googlegroups.com címre.
> További lehetőségekért látogasson el a(z) https://groups.google.com/d/
> optout címre.
>
--
Kovács Gábor (Y6DSOP) G4BPI-KW
Programtervező Informatikus (BSc) ME-GÉIK
Korszerű WEBtechnológiák sáv
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: <http://lists.openstreetmap.org/pipermail/talk-hu/attachments/20140616/7c4df001/attachment.htm>
További információk a(z) Talk-hu levelezőlistáról