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

[Peter Bodo]

Egy értelmesebb megoldás csatolva.
 
ez a hagyományos megoldást csinálja, csak genetikai algoritmus segítségével.
 
1. válasszuk ki a páratlan éllel rendelkező csúcsokat.
2. nézzük meg ezek minden lehetséges párosításánál a párok közötti
legrövidebb utak összegét. (ezt csinálja a GA, mert ez 20 pontnál már
milliós nagyságrendű párosítást jelent)
3. a fentiek közül a minimumot kiválasztva adjuk, hozzá a gráfhoz az ezeknek
a legrövidebb útvonalaknak megfelelő éleket.
4. így euleri gárfot kapunk, amiben már könnyű euleri kört találni (pl.
http://en.wikipedia.org/wiki/Eulerian_path#Hierholzer.27s_algorithm)

  _____  

From: Peter Bodo [mailto:peter.bodo at geologika.hu] 
Sent: Tuesday, June 17, 2014 3:29 PM
To: 'openstreetmap-hungary at googlegroups.com'
Subject: RE: [osm-hu] Kínai postások az OSMben


 
1. csinálsz egy gráfot, ahol az eredeti hálózatod minden éle egy csúcs lesz.
2. minden csúcspárt összekötsz egy akkora súlyú éllel, ami a két eredeti él
legrövidebb távolsága (ehhez használhatsz Dijkstra algoritmust).
Így egy teljes gráfot kapsz, és a kínai postás problémád átalakult utazó
ügynök problémává
 
3. a csúcsokat permutálod, ebből csinálsz egy alappopulációt
4. tesztelsz, keresztezel (90%-ban), mutálsz(0,5%-ban), megtartod mindig a
legjobb eredményt: csinálsz új populációt
5. pár kör után megvagy.
  

  _____  

From: openstreetmap-hungary at googlegroups.com
[mailto:openstreetmap-hungary at googlegroups.com] On Behalf Of Bihari Kristóf
Sent: Tuesday, June 17, 2014 11:09 AM
To: openstreetmap-hungary
Subject: Re: [osm-hu] Kínai postások az OSMben


Köszönöm a válaszokat, sajnos a meglehetősen n00b programozói képességeimet
*egyelőre* meghaladja a feladat, azt hiszem. :) (a matekot meg hagyjuk is) 
A mapping partis tervezőt megtoldanám azzal, hogy az online követést én sem
tartom megvalósíthatónak, ám egy olyan megoldást, ahol a parti elején
mindenki mond egy tervezett bejárandó km-t (gyalogosok kevesebbet, bringások
többet, stb) és ez alapján tervezhetne a rendszer olyan utakat, amik
nagyjából ilyen hosszúak, visszatérnek a kiindulópontra, minél kevesebbszer
futnak olyan úton, amin más is (ez persze elkerülhetetlen, főleg a start/cél
körül), (és lehetőleg nem lógnak át más területére). A session (nap)
befejezésekor a kimaradt területre újratervezés.

Vagy tényleg rendelünk egy kosár GPRS/GPS trackert a DX-ről és egy
diszpécser telefonon/PMR-en irányít mindenkit. :)

-K.


2014-06-17 9:46 GMT+02:00 Báthory Péter <bathory86p at gmail.com>:



2014.06.17. 09:02:50 dátumon tamas.g <gthrepwood at gmail.com> írta: 


Ez mondjuk kialt interaktiv megoldasra. 

Mikor Labatlanban voltatok felmerni, hany embernek volt okoseszkoze
(telefon, tablet) es ebbol mennyinek volt internetes kapcsolatara? Egy
atlagosnak mondhato tarsasag vajon mennyire tudna interaktivan, egyutt
felmerni, mert ugye ahoz legalabb kapcsolatban lenne jo lenniuk, hogy
tudjak, ki merre, hogy all, esetleg mi hianyozhat meg (feher foltok)


Okoseszköze a legtöbb felmérőnek van, mobilnetje már jóval kevesebbnek, de
olyan aksija, ami egész napos online követést, pozíció szórást bírna,
szerintem senkinek. A legkönnyebben valószínűleg a felmérők tudnának
alkalmazkodni egy ilyen rendszerhez.


BP



-- 
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/20140617/92bdcfb7/attachment.htm>
--------- következő rész ---------
A non-text attachment was scrubbed...
Name: Hua and Li-Shan - Genetic Algorithm for Chinese Postman Problems 2003.pdf
Type: application/pdf
Size: 250495 bytes
Desc: nem elérhető
URL: <http://lists.openstreetmap.org/pipermail/talk-hu/attachments/20140617/92bdcfb7/attachment.pdf>