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

[Peter Bodo]

és, ha elég részletes a bejárás, akkor egy utcában kétszer mész végig (mindkét oldalon). Így minden csúcs páros élű lesz, ami jelentősen leegyszerűsíti az algoritmust.

  _____  

From: openstreetmap-hungary at googlegroups.com [mailto:openstreetmap-hungary at googlegroups.com] On Behalf Of Imre Samu
Sent: Monday, June 16, 2014 7:00 PM
To: openstreetmap-hungary at googlegroups.com
Subject: Re: [osm-hu] Kínai postások az OSMben


esetleg ez próbáld meg:  https://github.com/rkistner/chinese-postman

Azért egy helyszíni felméréskor annyival bonyolultabb a probléma,  
ott több "postás" van , különböző sebességgel 
és az utcaszakaszok is különböző nehézségűek. 
vagyis egy mapping partyn több felmérőre kell optimalizálni..

és ezeket lehet tovább variálni .. pl.   "k-CPP" probléma  :)
"The k-Chinese Postman Problem (k-CPP) states that k ≥ 2 postmen have to
service a given graph, where each edge has a service time and a cruise time. The
task is to find a k-postman tour with minimal total time. In practice, this often
leads to unsatisfactory results, as differences in total time for each postman are not
accounted for ...
http://www.wiso.tu-dortmund.de/wiso/or/Medienpool/publikationen/dispap30.pdf







üdv,
 Imre





2014. június 16. 18:35 Bihari Kristóf írta, <bihari.kristof at gmail.com>:


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.

Üdv,

-K.



-- 
Magyar OSM Levelezőlista - openstreetmap-hungary at googlegroups.com
leiratkozás: openstreetmap-hungary+unsubscribe at googlegroups.com <mailto:openstreetmap-hungary%2Bunsubscribe at googlegroups.com> 
--- 
Azért kapta ezt az üzenetet, mert feliratkozott a Google Csoportok „openstreetmap-hungary” csoportjára.
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 ide: https://groups.google.com/d/optout.



-- 
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 „openstreetmap-hungary” csoportjára.
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 ide: https://groups.google.com/d/optout.



---
This email is free from viruses and malware because avast! Antivirus protection is active.
http://www.avast.com
--------- következő rész ---------
Egy csatolt HTML állomány át lett konvertálva...
URL: <http://lists.openstreetmap.org/pipermail/talk-hu/attachments/20140616/54e54d86/attachment.htm>