Re: [osm-hu] Kínai postások az OSMben

[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