Irodalomkutatás. Munkacím: PPC Live Map. GPS & Útkeresés

Irodalomkutatás Munkacím: PPC Live Map GPS & Útkeresés

Készítette: SZIRBIK FERENC & BEDŐK DÁVID 2004. április 22. BMF-NIK IAR Budapesti Műszaki Főiskola – Neumann János Informatikai Kar Intelligens Automatizált Rendszerek

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

TARTALOMJEGYZÉK TARTALOMJEGYZÉK .................................................................................................................... 2 ANGOL-MAGYAR SZAKSZÓTÁR ................................................................................................. 4 ELŐSZÓ ...................................................................................................................................... 5 URL: HTTP://WWW.AIGURU.COM/PATHFINDING.HTM .......................................................... 6 Idézet ................................................................................................................................... 6 English:.............................................................................................................................. 6 Magyar: ............................................................................................................................. 6 Az útkeresésről általában ............................................................................................. 6 HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/........................................ 8 Az első szimulációs program: From Game To Map ............................................ 8 Csapdák............................................................................................................................... 9 Algoritmusok alapja........................................................................................................ 9 Dijkstra's algoritmusa és a Best-First-Search (legjobbat először) .............. 9 Az A* algoritmus............................................................................................................ 11 HTTP://WWW.CCG.LEEDS.AC.UK/JAMES/ASTAR/ AVAGY A HULLÁMTECHNIKÁS ÚTKERESÉS ............................................................................................................................... 12 Legrövidebb út................................................................................................................ 12 Megjegyzések.................................................................................................................. 14 Legbiztonságosabb út .................................................................................................. 16 Megjegyzések.................................................................................................................. 19 Implementálás ................................................................................................................ 19 GRÁFOK, MINIMÁLIS KÖLTSÉGTÉRÍTÉSŰ FESZÍTŐFA, ÉS A LEGRÖVIDEBB ÚT ..................... 20 Néhány definíció............................................................................................................. 20 Gráfok ................................................................................................................................ 20 Gráfok ábrázolása.......................................................................................................... 20 Minimális költségtérítésű feszítőfa.......................................................................... 22 Algoritmusa ................................................................................................................... 22 Legrövidebb út................................................................................................................ 23 A legrövidebb út fogalma ............................................................................................ 23 Az algoritmus lényege.................................................................................................. 23 Az algoritmus részletesebben...................................................................................... 25 Az algoritmus pszeudokódja....................................................................................... 25 A második szimulációs program: Graphs and spanning trees..................... 26 Megjegyzések.................................................................................................................. 26 A PPC LIVEMAP ÉS A GPS .................................................................................................... 27 Bevezetés ......................................................................................................................... 27 U-Blox MS1E GPS vevőmodul................................................................................... 27 Rövid ismertető.............................................................................................................. 27 A készülék hitelessége .................................................................................................. 28 Feléledési idők ............................................................................................................... 28 Technikai áttekintés ...................................................................................................... 29 Működési feltételek....................................................................................................... 29 Kimeneti tüskék leírása ................................................................................................ 29 Soros Interfész Jel .......................................................................................................... 30 Speciális táp-tüskék....................................................................................................... 30 Útkeresés

38/2.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Jel meghatározás............................................................................................................ 30 Fizikai specifikáció ........................................................................................................ 31 A feszültségszint-konvertáló áramkör ....................................................................... 31 A soros port (RS232) tűkiosztása................................................................................. 32 A tesztszoftver ............................................................................................................... 32 Megjegyzés ..................................................................................................................... 33 A Garmin eTrex Vista készülék ................................................................................ 33 A választott protokoll a GPS készülékkel való kommunikációhoz....................... 33 Talker sentences – Közlő mondatok ........................................................................... 33 Proprietary sentences – Gyártóspecifikus mondatok .............................................. 34 Query sentences – Lekérdező mondatok................................................................... 34 Az adatok lekérdezésének megvalósítása ................................................................. 34 A soros port-ról történő olvasás.................................................................................. 35 IRODALOM JEGYZÉK ................................................................................................................. 37 Útkeresés .......................................................................................................................... 37 1. fejezet........................................................................................................................... 37 2. fejezet........................................................................................................................... 37 3. fejezet........................................................................................................................... 37 4. fejezet........................................................................................................................... 37 További információk a témához:................................................................................. 37 GPS...................................................................................................................................... 37

Útkeresés

38/3.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

ANGOL-MAGYAR SZAKSZÓTÁR Magyar szó/kifejezés útkeresés kiinduló pont cél elkerülendő (objektumok) elkerülendő ellenségek költségek minimalizálása objektum elkezd mozogni csapda csúcs feszítőfa

Útkeresés

Angol szó/kifejezés pathfinding starting point goal avoiding obstacles avoiding enemies minimizing costs object begins to move trap vertex spanning tree

38/4.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

ELŐSZÓ A dokumentáció a PPC Live Map programhoz készült. A térképprogramban fontos szerep jut az útkeresésnek, mivel terveink szerint egy navigációs szoftvert készítünk, nem egy hagyományos térképet. A teljesség igényével, ám fizikai határokon belül néhány útkeresési megoldást megvizsgáltam, és tapasztalataimat összegyűjtöttem ezen dokumentációban. A PPC Live Map egyelőre még csak munkanév. A projekten Szirbik Ferenc és jómagam dolgozunk. A későbbi tervek ezen megoldások demonstrálása speciális szimulátorprogramok segítségével. Ezen programok terveiről szintén lehet olvasni. Sok esetben ezen programok többet fognak tudni, mint amit egy térképprogramban ezekből fel lehet majd használni, de így talán növelhető az algoritmusok stabilitása, ha nem csupán az „alap” dolgokat tudja az algoritmus, hanem néhány esetben sokkal többet is. A leírásban található „fordítások” nem tükörfordítások, és sok esetben nem is tükrözik azt, ami a felettük lévő eredeti forrásból származnak, csupán a számomra lényeges momentumokat fogalmaztam meg a saját nyelvemen. Az esetleges félrefordításokért, elnézést kérek. Az információk döntő többsége az Internet-ről származik, és az eredetük minden esetben fel van tüntetve. Ezúton is köszönöm az adott információ összegyűjtését, és/avagy közkincsé tételét az adott oldalak alkotóinak. Külön köszönet illeti Vámossy Zoltán tanár urat, aki linkeket ajánlott az információ gyűjtés elkezdésének könnyítése érdekében. Budapest, 2004. április 22. Szirbik Ferenc (Szife)

Útkeresés

38/5.

Bedők Dávid (Qwaevisz)

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

URL: HTTP://WWW.AIGURU.COM/PATHFINDING.HTM Idézet English: Pathfinding is one of the most visible types of Artificial Intelligence in video games. Few things make a game look "dumber" than bad pathfinding. Fortunately, pathfinging is mostly a "solved" problem. If you ask most game developers "How to I do pathfinding?", the vast majority will answer "A*". Magyar: Az útkeresés az egyik legkeresettebb mesterséges intelligencia típus a számítógépes játékokban. Sok mindentől függ, hogy egy játék jó lesz-e. Egy ilyen fontos tényező az alkalmazott útkereső algoritmus. Szerencsére ez a probléma ma már többnyire megoldott, de azért az ember nap mint nap találkozhat félresikerült alkotásokkal, amiben nem gondolták végig, hogy ennek milyen nagy jelentősége van. Az útkeresésről általában Egy térképprogram esetében mit is jelent az a probléma, hogy útkeresés. Ismerünk egy adott pontot, ahol éppen mi állunk. Ezt a modern rendszerekben, és így a mienkben is egy GPS készülék segítségével a felhasználó gyorsan beazonosíthatja. Amennyiben nem rendelkezik GPS készülékkel, egy egyszerű kereső funkció segítségével ezt a pontot az ember maga is kijelölheti. A GPS-es pont pontossága vitatható, sőt sokszor nem is határozható meg, mivel a vevő nem lát elég holdat, avagy a holdak túl közel vannak egymáshoz képest, így a látott holdak közül „kidob” a készülék párat. Ilyen esetekben szoftveresen van megoldás segítségre, hiszen több, mint valószínű, hogy az illető annak a környezetnek a közelében van, amit az elmúlt pár percben megjelölt vagy a GPS, vagy a felhasználó a jelenlegi helyzetének, így a szoftver felajánl egy közeli pontot valahol az előző koordináta, és az előzőleg kijelölt cél között. Ezt aztán az ember módosíthatja, de ekkor már valószínűleg ismerős neki a környék. A másik pont a cél. Ezt vagy kijelöli az illető a térképen (rámutat), avagy beírja szövegesen, hogy mit keres. Miután a program viszont kérdésekkel egyértelműen beazonosított 1 pontot, ami szintén szerepel a térképen, akkor az útkeresés folyamata elindulhat. Ha a térképen lévő pontokat gráf pontoknak tekintjük, akkor az útkeresés ezen gráf pontjai közötti utakat jelenti, amennyiben azok léteznek (egy adott térképen szinte mindig létezik út két pont között, lehetne mondani, de ez nem minden esetben van így: pl. ha valaki gyalogosan közlekedik, akkor a folyó közepére nincs út, avagy az autópálya 4 sávja közepére. Ettől függetlenül a program egy figyelmeztetés mellett amennyiben az adott lehetőségekkel út nem létezik, keres alternatív lehetőségeket, tervünk szerint). Van egy olyan lehetőség is, miszerint a térképet grafikusan képzeljük el, és mint „képet” dolgozza fel a program. Ezt nevezzük pixeles megoldásnak. Ez valószínűleg sokkal pontosabb utat tud meghatározni, ámde felmerül ezzel olyan probléma, hogy GPS koordinátákat képtelenség minden képponthoz tárolni (bár ha szoftveresen számoljuk ki a koordinátákat, akkor talán igen). Útkeresés

38/6.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Mindkét módszernek vannak előnyei, és hátrányai is, ezért talán a legjobb megoldás, ha az előnyüket kivéve egy hibrid módszer megvalósítását tűzzük ki célul. A GPS adatokat egy több szintű gráf-háló tárolja (több szint: minden közlekedési módszernek külön gráf-háló). Létezik egy összesített gráf is, ami minden szint pontjait tárolja, itt akkor keres utat a program, ha nincs út a megadott 2 pont között, avagy erre utasítást kap. Mindezekre rákerül egy információ-gazdag grafikus felület, mely színek segítségével tárol adatokat. Ennek van egy váza, ami tartalmazza azon pontokat, amelyek minden eszköz számára megközelíthetetlenek. Ilyen például egy folyó (híd nélküli része ☺), vagy egy ház alapja. Erre kerülnek rá a közlekedési módszerek különféle sémái. Pl. ha gyalog vagyunk, akkor azon utak jelennek meg, amik gyalogosan elérhetőket, a többi út ugyanolyan akadály marad, mint mondjuk a ház alapja. Itt is lehetőség lesz arra, hogy minden felület sémát elhelyezzünk, és az uniójuk szerint keresünk utat (vagy bármelyik 2 uniója szerint). Így az elején már csak egy dolgot kell tisztázni, hol lesz a kapcsolat a gráf és a grafikus megoldás között? A felhasználó a grafikus felületet látja, amin külön pontok jelzik azon pixeleket, melyek gráf pontok is. Útkeresésnél a felhasználó dönthet, hogy melyik út jelenjen meg, vagy rábízza a készülékre a dolgot. Ha ez megvalósul, akkor a térképünk akár milliméter pontosan képes legrövidebb út meghatározására a grafikus felületen (a járda egyik szegélyéről folyamatosan megy át a másik szegélyre, ha ott már úgyis be kell kanyarodni, és ehhez hasonló dolgokra gondolok itt most, ami bár nem „életszerű”, ám az ember ezzel pontos információhoz jut. Természetesen az már részletkérdés, hogy mondjuk a fenti lehetőséget bekapcsolja-e az ember, vagy letiltja az ennyire precíz számításokat), és a lehető legjobban kihasználja a GPS-ben rejlő lehetőségeket.

Útkeresés

38/7.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/

„The problem we're trying to solve is to get a game object from the starting point to a goal”. Azaz azt a problémát járja körül az oldal, hogy egy játékban hogyan lehet egy adott objektumot egy másik (cél) pontba vinni. A téma így megfogalmazva, hogy 1 adott pontot hogy lehet eljutatni, teljes mértékben a térképprogram grafikus felületébe illik, hiszen ott is ugyanez a feladat. Az első szimulációs program: From Game To Map Terveim között szerepel a fent leírtak megvalósítása, de nem csupán 1 test esetére, hanem N testre. Valami olyasmi szimulációs programot képzeltem el, mely 1.0-ás verzióban 1 testre, és 2D-ben akadályokkal övezett területet ad megoldást különféle algoritmusok alapján. A 2.0-ás verziót akkor nevezem majd „kész”-nek, ha a fent leírt dolgokat N test esetére is megvalósítja. A következő (3.0) verzióban már 3D-ben szimulálva 1 testre, majd a végső verzióban N testre megoldva tálalnám a problémát. Amit ebből a térképprogramba fel tudunk majd használni, az a 3.0-ás verzió, ám roppant hasznos lehet egy jól működő 4.0-ás is, más feladatok megoldására. „.[…] avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.)” A probléma tehát adott, az esetet „játék” szempontjából tárgyalja az oldal, ettől még persze könnyű elvonatkoztatni ettől. Akadályokat el kell tudnia kerülni az algoritmusnak, szintúgy ellenségeket (mondjuk autókat: ha gyalog megyünk, nem mehetünk rá az útra sem). És ha lehet minimalizálni kell a költségeket. Ez egy összetett kérés, mivel adott utaknak különféle költségei lehetnek, attól függően, hogy milyen nézőpontból vizsgáljuk. Nézzünk erre egy egyszerű példát: van egy távolság, ami autópályán haladva 50 km távolságban van, de létezik egy földút is, amin haladva 20km alatt el tudjuk érni célunkat. Autópályán haladva 100 km/h-val tudunk haladni, míg földúton esetleg csak 30-al. A sok fékezés és rossz utak miatt a földúton járművünk kétszer annyit fogyaszt mint a kényelmes autópályán. Mindezek után ha a legrövidebb utat akarjuk, akkor a földutat választjuk, ismerve kocsink tulajdonságait, de a hosszabb autópálya a benzin, a kocsi állapota szempontjából megfelelőbb „költségekkel” rendelkezik. „At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm would find a path when the object begins to move and the object would follow that path, oblivious to everything else.” Bonyolultan szép az élet, azaz fel kell készülni arra az esetre is, hogy az objektumok – a későbbiekben nevezzük ezeket átvitt értelemben „ellenségnek” (de ide értve saját társainkat is, ha mondjuk egy RTS játékban gondolkozunk) – mozognak, így minden ilyen ellenség pontot újra kell vizsgálni minden megtett lépés után, és a legrövidebb pontot újra kiszámolni, és most már az alapján járni. Fontos dolog az is, hogy nehogy beragadjunk, és pár adott pont között mozogjunk, „emlékezet” segítségével erre előre fel kell készítenünk algoritmusunk. Az a memória változó méretű lehet, egy dinamikus lista segítségével a gyakorlatban az „élethez” lehet majd igazítani.

Útkeresés

38/8.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Csapdák

[Ábra 1 - HTTP://THEORY.STANFORD.EDU/~AMITP/GAMEPROGRAMMING/]

Az ábrán szürkével jelölt területet nevezhetjük csapdának. Ugyanis az első képen azt láthatjuk, hogy a kiinduló ponttól észleljük a célt, de mikor odaérünk, rájövünk, hogy akadály van előttünk. Amennyiben látjuk előre a teljes akadályt, avagy elérünk egy olyan pontot (detect obstacle here), ahonnan már látjuk, akkor a csapdát elkerülve sokkal rövidebb úton elérhetjük a célt. Természetesen, ha a cél a szürke részen belül van, akkor az nem csapda abban a szituációban. Algoritmusok alapja Számos útkereső algoritmus a lentebb látható képhez hasonló grid-et használ. A 2D-s képen jelölve vannak a kapcsolódási pontok, azaz hogy honnan hova lehet eljutni. A gyorsabb algoritmus érdekében ezt a módszert érdemes megfontolni, és felhasználni a térkép grafikus felületén, hogy ott sem minden pixelt veszünk figyelembe, hanem mesterségesen felosztott grid pontokat! (esetleg lehetőség van a teljesen pontos pixeles felosztásra is, ahol nemcsak derékszögű irányváltások léteznek, hanem 360 fokosak is, de elképzelhető ennek lassúsága)


Dijkstra's algoritmusa és a Best-First-Search (legjobbat először) „Dijkstra's algorithm is guaranteed to find a shortest path from the starting point to the goal, as long as none of the edges have a negative cost.”. Azaz Dijkstra algoritmusa garantálja nekünk a legrövidebb út megtalálását a start és cél pont között.

Útkeresés

38/9.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.


A képen látható a kiinduló pont középen, és a kék cél pont. A kékes színek azok a területek, amelyeket az algoritmus „szkennelt”. A Best FirstSearch (továbbiakban BFS) algoritmus ehhez nagyon hasonlóan működik, de tartalmaz számos heurisztikát, hogy pl. milyen messze van a cél. „BFS is not guaranteed to find a shortest path”, azaz a BFS nem garantálja a legrövidebb utat, de sokkal rövidebb idő alatt talál megoldást. Az alant lévő ábrán a sárga pont jelöli, hogy magas heurisztikus értéke van, azaz messze van a céltól, és fekete jelöli az alacsonyat:


Ez mind nagyon szép, de nézzük most olyan példát, amikor vannak a térképen akadályok: a bal oldali kép Dijkstra algoritmusát, míg a jobb oldali a BFS-t tartalmazza:


„The trouble is that BFS is greedy and tries to move towards the goal even if it's not the right path.” A lényeg, hogy bár a BFS egyszerű esetekben gyorsnak tűnhet, egy kis probléma esetén a futási idő már sokkal kevésbé szembetűnőbb, ám a megoldás „jósága” nem is hasonlítható Dijkstra útkereső algoritmusához. Nézzünk most egy olyan algoritmust, mely a fenti 2 algoritmus előnyeit egyesíti: Útkeresés

38/10.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Az A* algoritmus „A* can guarantee a shortest path”. Sőt, ezen kívül heurisztikákat is tartalmaz! Tehát lényegében teljesíti azt, amit fentebb írtam: előnyöket egyesít. Nemhiába: „A* is the most popular choice for pathfinding” (a legnépszerűbb algoritmus), mivel rendkívül rugalmas, és széles körben használható.


Egy kis magyarázat az ábrákhoz: a sárga (h) szín jelöli a céltól való távolságot, a cián (g) pedig a kezdő ponttól mért távolságot jelöli. N csúcs van a képen, g(n) reprezentálja az út súlyát a kezdő ponttól minden csúcsra. H(n) pedig a heurisztikus értékét képviseli minden pontnak. Így a legrövidebb út f(n) előáll g(n) és h(n) összegeként. A technikai, matematikai és implementálási részleteket a From Game To Map fejlesztői kézikönyvében olvashatóak.

Útkeresés

38/11.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

HTTP://WWW.CCG.LEEDS.AC.UK/JAMES/ASTAR/ AVAGY

A

HULLÁMTECHNIKÁS ÚTKERESÉS A most bemutatott technikákról Intelligens rendszerek II gyakorlaton esett szó, Molnár András előadásban. A fenti url is ezt az úgynevezett hullám algoritmus potenciálmezős megvalósítását mutatja be. Valójában két technikáról van szó, mely nagyon hasonló ötleten alapszik. Maga az előző fejezetben említett grid itt is létezik, és itt is hasonló elven tudjuk eldönteni az akadályok helyzetét. Ráadásul az előző fejezetben tárgyalt Dijkstra algoritmusa is ránézésre egyféle hullámterjedést mutatott be, és az is rögtön ki fog derülni, hogy az övé gyorsabban szolgáltat eredményt, mivel ott nem szükséges az egész területet előre ismerni, így szükségtelen bejárni is. Ellenben itt előre elkészítünk egy mátrixot a teljes térképre nézve. A mátrix elemei itt is bizonyos szempont szerinti heurisztikákat fognak tartalmazni. A hullám továbbterjesztéses algoritmus egy legrövidebb utat fog megtalálni, avagy 1 lehetséges ilyen utat, a legbiztonságosabb út algoritmus pedig azt az utat adja meg, ami a lehető legjobban elkerüli az akadályokat. Azon, hogy egy algoritmus heurisztikákat tartalmaz, azt értjük, hogy ráérzésre kipróbálunk egy lehetőséget a számunkra elérhető számos útból, majd ha megtéve ezt a lépést előrébb jutottunk célunk felé, akkor meghagyjuk, különben visszalépünk. A genetikus algoritmusok is valami hasonló módszert alkalmazhatnak. Legrövidebb út Nézzük, hogy is működnek ezek. A következő térképen fogunk vizsgálódni: 254 254

255

254 254 254 254 254

0 [Ábra 7 - QWAEVISZ]

A célunk az, hogy a lehető legmagasabb heurisztikus értékkel rendelkező ponttól (a kiinduló pont a legmagasabb értékű, hiszen ez van a legmesszebb a céltól a mi szempontunkból!) eljussunk a legalacsonyabb pontig, a 0-ig, azaz a célig. A cél távolsága a céltól 0. Az akadályokat egyel alacsonyabb értékkel jelöljük, mint a strat pontot, de ennek csak az algoritmus szempontjából van lényeges szerepe (minden cellaérték 1 byte-os adatot képes tárolni, ezért vannak így a határok).

Útkeresés

38/12.

Útkeresés

PPC LIVE MAP

IAR

Először a hullámterjedéses algoritmust nézzük. Legelső lépésben fel kell töltenünk a mátrixunk még üres mezőit. A céltól fogunk elindulni, és minden egyes pontra feljegyezzük, hogy milyen messze van a céltól, azaz mekkora a heurisztikus értéke. Így fog kialakulni a hullámunk:

2004. ÁPRILIS 22.

9 9 9 9 9 9 9 9 10 255

8 8 8 8 8 8 8 9 10 11

8 7 7 7 7 7 8 9 10 11

8 7 6 6 6 254 254 254 254 254

8 7 6 5 5 5 5 5 5 5

8 7 6 5 4 4 4 4 4 4

8 254 254 5 4 3 3 3 3 3

8 7 6 5 4 3 2 2 2 2

8 7 6 5 4 3 2 1 1 1

8 7 6 5 4 3 2 1 0 1

[Ábra 8 - QWAEVISZ]

Feltesszük természetesen hogy átlósan is tudunk menni, azaz minden esetben ha nincs akadály, 8 irány közül választhatunk. A lehetséges út esetében nincs garantálva az, hogy ez a legrövidebb út lesz, mivel ez fog függni a konvencióktól. Az út úgy fog felállni, hogy a kiindulási ponttól most elindulunk, és mindig a legalacsonyabb heurisztikus pont felé fogunk lépni. A hullám tulajdonsága miatt arra, hogy beakadjunk 2 pont között, nincs esély hiszen biztos, hogy lesz legalább egy 1-el alacsonyabb pont minden mező szomszédságában. Miért is van szükség járulékos szabályokra? Előfordulhat, ráadásul elég sűrűn, hogy egy adott pontból több irányba is tudunk menni! Ahhoz, hogy egyértelmű utat tudjunk meghatározni, ilyenkor meg kell tanítani az algoritmust arra, hogy melyik utat válassza. Ezért egy prioritási sorrendet érdemes felállítani a 8 lehetséges irány között: 4 3 2

5 1

6 7 8


Minél nagyobb a prioritása adott iránynak, az lesz a túlélőbb, ha dönteni kell. Ennek a táblázatnak a függvényében fog változni maga az út is, ezért nem garantálható, hogy a legrövidebb utat fogjuk megtalálni. Ezen prioritási kiosztásnak a lehetőségei végesek, így esetlegesen megoldás az, hogy minden lehetőségre megnézzük az utakat, és a legrövidebbet ebből ki tudjuk választani, de ez meglehetősen lassú megoldás. Esetleg ha még gyorsabb megoldást akarunk, nem alkalmazunk prioritási sort, hanem véletlenszerűen fogunk döntéshelyzetben választani. Így is biztos, hogy találunk utat a kiindulási pont és a cél között, és nincs szükség konvenciók meghatározására. Nézzük a fenti prioritási sor, és a térképünk által meghatározott utat:

Útkeresés

38/13.

Útkeresés

PPC LIVE MAP

IAR

9 9 9 9 9 9 9 9 10 255

8 8 8 8 8 8 8 9 10 11

8 7 7 7 7 7 8 9 10 11

8 7 6 6 6 254 254 254 254 254

8 7 6 5 5 5 5 5 5 5

8 7 6 5 4 4 4 4 4 4

8 254 254 5 4 3 3 3 3 3

2004. ÁPRILIS 22.

8 7 6 5 4 3 2 2 2 2

8 7 6 5 4 3 2 1 1 1

8 7 6 5 4 3 2 1 0 1


Példaképpen nézzünk meg egy másik megoldást is egy másik prioritási mátrix alapján: [Ábra 11 - QWAEVISZ]

9 9 9 9 9 9 9 9 10 255

8 8 8 8 8 8 8 9 10 11

8 7 7 7 7 7 8 9 10 11

8 1 2

7

6 5 4

3

8 7 6 6 6 254 254 254 254 254

8 7 6 5 5 5 5 5 5 5

8 7 6 5 4 4 4 4 4 4

8 254 254 5 4 3 3 3 3 3

8 7 6 5 4 3 2 2 2 2

8 7 6 5 4 3 2 1 1 1

8 7 6 5 4 3 2 1 0 1

A példából is jól látszik, hogy bár egyértelműen más utat találtunk meg, ez is 10 közbülső lépést tartalmaz. Ebből is látszik, hogy a prioritási mátrixok közötti különbség szinte mérhetetlen, így nem érdemes az összes lehetséges utat megkeresni, és kiválasztani belőlük a legrövidebbet. Még abban sincs különbség a két eset között, hogy hányszor léptünk átlósan, mindkét esetben 9x történt ez meg. Ezek után ki lehet jelenteni, hogy a hullámterjedéses algoritmus mégis tudja garantálni a legrövidebb utat.

Megjegyzések A fenti eredményeket tudjuk pontosítani, amennyiben a hullám terjedését nem 8 irányba követjük el, hiszen így az átlós iránynak megegyező súlya van a „vízszintes”, avagy „függőleges” iránnyal. Nézzünk egy olyan példát, mikor a hullám csak 4 irányban terjed: 17 16 15 14 13 14 15 16 17 255

16 15 14 13 12 13 14 15 16 17

15 14 13 12 11 12 13 14 15 16

14 13 12 11 10 254 254 254 254 254

13 12 11 10 12 11 254 9 11 10 254 8 10 9 8 7 9 8 7 6 8 7 6 5 7 6 5 4 6 5 4 3 5 4 3 2 6 5 4 3

9 8 7 6 5 4 3 2 1 2

8 7 6 5 4 3 2 1 0 1


Útkeresés

38/14.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Bár az rögtön szembetűnik, hogy a megoldást lassabban kapunk, mint az előző esetben (több súlyra volt szükség), de a megoldás valamivel életszerűbb (itt is a már sokszor használt 8 irányú prioritási sort alkalmazva): 17 16 15 14 13 14 15 16 17 255

16 15 14 13 12 13 14 15 16 17

15 14 13 12 11 12 13 14 15 16

14 13 12 11 10 254 254 254 254 254

13 12 11 10 12 11 254 9 11 10 254 8 10 9 8 7 9 8 7 6 8 7 6 5 7 6 5 4 6 5 4 3 5 4 3 2 6 5 4 3

9 8 7 6 5 4 3 2 1 2

8 7 6 5 4 3 2 1 0 1


Ebben az egyszerű példában a kapott megoldás egyetlen egy pontban tér el az első esettől, mégpedig a cél előtt 2 átlós lépés helyett itt 2 vízszintes mozgás is elég volt, ami azt jelenti, hogy rövidebb utat kaptunk! Ezek után lehet még jobban pontosítani a számításokat. Most 4+4 irányban fog terjedni a hullámunk, ahol a „vízszintes” és „függőleges” terjedés egységnyi súlyt kap, az átlós irányok pedig feltételezve a négyzet átlójának méretét, SQRT(2) súlyt kap. Ez egy nagyon csúnya irracionális szám, a számítógép megfelelően nagy térkép esetén nem adna elfogadható időn belül megoldást a számítások időigénye miatt (viszonyítva az előző algoritmusokhoz), így egy közelítő értékkel célszerű számolni, mondjuk 7/5-el (1.4 az ~1.4142 helyett): 12,20 11,80 11,40 11,00 10,60 11,00 11,40 11,80 12,80 255,00

11,20 10,80 10,40 10,00 9,60 10,00 10,40 11,40 12,40 13,40

10,80 9,80 9,40 9,00 8,60 9,00 10,00 11,00 12,00 13,00

10,40 9,40 8,40 8,00 7,60 254,00 254,00 254,00 254,00 254,00

10,00 9,00 8,00 7,00 6,60 6,20 5,80 5,40 5,00 5,40

9,60 9,80 8,80 8,40 8,00 8,60 254,00 7,80 7,40 7,00 7,60 254,00 6,80 6,40 6,00 6,60 6,20 5,80 5,40 5,00 5,60 5,20 4,80 4,40 4,00 5,20 4,20 3,80 3,40 3,00 4,80 3,80 2,80 2,40 2,00 4,40 3,40 2,40 1,40 1,00 4,00 3,00 2,00 1,00 0,00 4,40 3,40 2,40 1,40 1,00 [Ábra 14 - QWAEVISZ]

A számolás ebben az esetben lényegesen több időt vett igénybe számomra is (az elszámolások lehetségesek): 12,20 11,80 11,40 11,00 10,60 11,00 11,40 11,80 12,80 255,00

11,20 10,80 10,40 10,00 9,60 10,00 10,40 11,40 12,40 13,40

10,80 9,80 9,40 9,00 8,60 9,00 10,00 11,00 12,00 13,00

10,40 9,40 8,40 8,00 7,60 254,00 254,00 254,00 254,00 254,00

10,00 9,00 8,00 7,00 6,60 6,20 5,80 5,40 5,00 5,40

9,60 9,80 8,80 8,40 8,00 8,60 254,00 7,80 7,40 7,00 7,60 254,00 6,80 6,40 6,00 6,60 6,20 5,80 5,40 5,00 5,60 5,20 4,80 4,40 4,00 5,20 4,20 3,80 3,40 3,00 4,80 3,80 2,80 2,40 2,00 4,40 3,40 2,40 1,40 1,00 4,00 3,00 2,00 1,00 0,00 4,40 3,40 2,40 1,40 1,00 [Ábra 15 - QWAEVISZ]

Útkeresés

38/15.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

A megoldás megegyezik az előbb kapott eredménnyel, azonban ha összeadjuk az út során érintett súlyokat, akkor kisebb számot kapunk. Ez a kapott szám a súlyokra nézve pontosabb, bár az út fizikailag nem lesz rövidebb (ebben a példában). Az első pont amire „rálépünk” 12,40-es súlyú, míg az előző esetben ez 16 volt, ami nyilvánvalóan pontatlanabb távolság érték. Legbiztonságosabb út Nézzük most meg egy másik hullámterjedéses algoritmust. Ennek tehát a lényege a legbiztonságosabb út megkeresése. Itt a fentiek alapján már nem fogok kételkedni abban, hogy ez e a lehető legbiztonságosabb út. A módszer itt is nagyon hasonló, csak itt most úgy fogunk eljutni a célhoz, hogy mindig a lehető legnagyobb érétket választjuk. Ez azért lesz így, mivel most a hullámokat az akadályoktól (254-es pontoktól) fogjuk kezdeni terjeszteni, így a heurisztikus értékek az akadályoktól mért távolságot fogják jelenteni. Minél nagyobb ez a szám, annál messzebb vagyunk tőlük. Nézzük a mátrix feltöltését, figyelembe véve most azt is, hogy a térkép széle is akadálynak számít, így nekünk azt is a lehető legjobban el kell kerülnünk: 254 254 254 254 254 254 254 254 254 254 254 254 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 255

1 2 2 2 2 2 2 2 2 1

1 2 3 2 1 1 1 1 1 1

1 2 3 2 1 254 254 254 254 254

1 2 2 2 1 1 1 1 1 1

1 1 1 1 2 2 2 2 2 1

1 254 254 1 2 3 3 3 2 1

1 1 1 1 2 3 3 3 2 1

1 2 2 2 2 2 2 2 2 1

1 1 1 1 1 1 1 1 0 1

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254 [Ábra 16 - QWAEVISZ]

A prioritási mátrixunk legyen itt is a következő: 4 3 2

5 1

6 7 8


Útkeresés

38/16.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Mindezek után a lehető legbiztonságosabb út a következő lesz: 254 254 254 254 254 254 254 254 254 254 254 254 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 1 254 255

1 2 2 2 2 2 2 2 2 1

1 2 3 2 1 1 1 1 1 1

1 2 3 2 1 254 254 254 254 254

1 2 2 2 1 1 1 1 1 1

1 1 1 1 2 2 2 2 2 1

1 254 254 1 2 3 3 3 2 1

1 1 1 1 2 3 3 3 2 1

1 2 2 2 2 2 2 2 2 1

1 1 1 1 1 1 1 1 0 1

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254 [Ábra 18 - QWAEVISZ]

A fenti példából egy nagyon fontos dolog hiányzik! Mégpedig az, hogy a legbiztonságosabb út keresése közben mi nem egy utat kapunk (a fenti eset kivétel), hanem egy gráfot! Egy adott utat úgy kapunk, ha ennek a gráfnak egy adott (pl. mélységi) bejárását felírjuk. A kapott eredmények közül ha a legrövidebb utat keressük a gráfban, akkor a lehető legbiztonságosabb és legrövidebb utat fogjuk megkapni. Nézzünk egy példát a fentiekre: 254 254 254 254 254 254 254 254 254 254 254 254 254 255 1 1 1 1 1 1 1 1 254 1 2 2 2 1 254 1 1 1 254 1 2 3 2 1 254 254 254 254 254 1 2 2 1 1 254 1 1 1 254 1 1 1 1 254 254 1 2 2 254 1 254 254 254 254 254 1 2 2 254 1 1 254 1 1 1 1 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 0

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254 [Ábra 19 - QWAEVISZ]

A fenti esetben is prioritási sort használtam, az elején lévő kacifántos gráf a következő képpen adódott:


De ha gráfokról van szó, akkor nincs is szükség itt most prioritási sorra. Jól látszik, hogy a térképen lefelé haladva is van egy hasonlóan biztonságos út, azt mi mégsem találtuk meg. Nézzük prioritási sor nélkül:

Útkeresés

38/17.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

254 254 254 254 254 254 254 254 254 254 254 254 254 255 1 1 1 1 1 1 1 1 254 1 2 2 2 1 254 1 1 1 254 1 2 3 2 1 254 254 254 254 254 1 2 2 1 1 254 1 1 1 254 1 1 1 1 254 254 1 2 2 254 1 254 254 254 254 254 1 2 2 254 1 1 254 1 1 1 1 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 254 1 2 2 2 2 2 254 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 0

254 254 254 254 254 254 254 254 254 254

254 254 254 254 254 254 254 254 254 254 254 254 [Ábra 21 - QWAEVISZ]

Az így kapott gráfból bármely bejárással a legbiztonságosabb utat kapjuk meg. A színekkel azért jelültem az egyes lépéseket, hogy egyértelmű legyen, hogy a 255-ös mezőből gráf pont csak a 2-es mezőhöz vezet, így onnan nem is mehetünk egyik 1esre sem a gráf bejárása során. A keletkezett gráf:


Egyetlen egy járulékos szabályt vezettem be a gráf háló felépítése közben: ha egy pontra nézem a szomszédokat, hogy adott pontból merre lehet továbbhaladni, akkor 2 variáció van: 1. Van olyan pont, amin még nem jártam. 2. Nincs olyan pont, amin még nem jártam. Az első esetben a szabályom az volt, hogy akkor minden olyan ponthoz tartozik él, amin még nem jártam, és amin már jártam, ahhoz nem tartozik. A második esetben pedig minden olyanhoz vezet él, amin már jártam. A fenti járulékos szabályok bevezetésével a legrövidebb, legbiztonságosabb utak mindegyikét meg lehet határozni (megjegyzem, hogy a járulékos szabályokra biztosan más lehetőség is van, hogy hasonló eredményt kapjunk).

Útkeresés

38/18.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Megjegyzések A fent ismertetett legbiztonságosabb út megkeresésére biztosan létezik másféle algoritmus is, itt csak azért említettem meg, mert hasonlóan működik a legrövidebb utat szolgáltató algoritmushoz. Implementálás Kicsit rátérek arra, hogy ezen algoritmusok hogyan lesznek beépítve működő programokba. Felmerül a kérdés, hogy minden esetben szükségünk van-e arra, hogy a teljes térképet előre „kiszámoljuk”. Én úgy vélem nincs. Dijkstra algoritmusa alapján addig terjesztjük a hullámunkat, amíg a hullám egyik pontja el nem éri a kiindulási pontunkat (255). Ezek után az út keresése már egyértelmű. A hullám terjedését kell még valahogyan modellezni. A cél-nak létezik egy i, és j koordinátája. Ezen koordináták körül „koncentrikus” négyzetekkel végighaladunk, és minden esetben a környékén lévő kisebb koncentrikus kör elemeit vizsgálva a lehető legkisebb értékhez adunk hozzá 1-et, vagy a pontosabb eredmény érdekében az átlós értékekhez 1, 4-et, a többihez 1-et, és ezek után keressük meg a legkisebb új értéket, amit beírunk az aktuális helyre.

Útkeresés

38/19.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

GRÁFOK, MINIMÁLIS KÖLTSÉGTÉRÍTÉSŰ FESZÍTŐFA, ÉS A LEGRÖVIDEBB ÚT

A most leírt módszereket Prof. Öveges Ferenc tanár úrtól tanultam 1998 és 2002 között, mikor a Lovassy László Gimnáziumban tanultam Veszprémben. Néhány definíció Hurok él: olyan él, melynek kezdő és végpontja azonos csúcsból indul illetve érkezik. Szomszéd pontok: A és B szomszéd pontok, ha a gráfban van 1 él A és B között Fokszám: Megadja, hogy egy adott pontra hány él illeszkedik. Izolált pont: olyan pont, amelyre nem illeszkedik él, azaz fokszáma nulla. Többszörös élek: Ugyanazon kezdő és végpontokat tartalmazzák. Gráfok Sokféle gráf létezik (a gráf egy absztrakt adatszerkezet), és mindegyiknek megvan a maga felhasználási területe. Csak felsorolás szinten nézzük ezeket végig: • Egyszerű összefüggő gráf • Egyszerű nem összefüggő gráf • Irányított összefüggő gráf • Irányított nem összefüggő gráf • Súlyozott összefüggő gráf • Súlyozott nem összefüggő gráf • Irányított és súlyozott összefüggő gráf • Irányított és súlyozott nem összefüggő gráf • Speciális gráf (hurokmentes, minimum távolság limit, többszörös élek stb…) Természetesen a teljesség igényével azokat írtam fel, amelyekkel én már találkoztam. A térképprogramhoz nekünk egy súlyozott és irányított összefüggő gráfra lesz szükségünk, ami nem hurokmentes, tartalmaz többszörös éleket, és az összefüggősége néhány speciális esetben megbomolhat, de a hatékonyság miatt az ilyen helyzeteket kerülni kell. Gráfok ábrázolása Erre is többféle módszer létezik, és a legtöbb esetben függ a gráf típusától. Nézzünk először egy egyszerű gráfot, amit statikus adatstruktúrával tárolunk (nagyon redundáns megoldás). Tárolás kapcsolatmátrixszal: X 1 2 3 4 5 6 7

1 H I H I H H H

2 I H I H H I H

3 H I H I I H H

4 I H I H H H H

5 H H I H H I I

6 H I H H I H I

7 H H H H I I H


Útkeresés

38/20.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Talán jól látszik az ábráról pár dolog: • Egy adott i, j a mátrixban I (igaz) vagy H (hamis) érétket vehet fel. • Adott i, j igaz lesz, ha i és j között létezik él. • A főátlón lévő értékek mindig hamisak, amennyiben a gráfban nincsenek hurok élek. • A statikus mátrix a főátlóra szimmetrikus. Lehetőség van dinamikus tárolásra is, ezt a következőképpen lehet elképzelni:


Ezt a tárolási elemet nevezik szomszédsági listának. A harmadik lehetséges módszert már nem rajzolom fel, de könnyen el lehet képzelni egy teljesen dinamikus struktúrát, melynél a Statikus mutató vektort felváltja egy olyan dinamikus adatszerkezet, mely elemeinek 2 mutató mezeje van. Tegyük fel, hogy az új gráfunk súlyozott és irányított, vannak benne többszörös élek. Ekkor a kapcsolatmátrix a következőképpen fog kinézni (a gráf ábrája nem méretarányos): X 1 2 3 4 5 6 7

1 0 20 0 10 0 0 0

2 0 0 25 0 0 0 0

3 0 0 0 0 35 0 0

4 10 0 5 0 0 0 0

5 6 7 0 0 0 0 40 0 35 0 0 0 0 0 0 15 0 0 0 30 17 30 0


Ami látszik a kapcsolatmátrixról: • Megszűnt a szimmetria az irányítottság miatt. • Csak ott szimmetrikusak az értékek, ahol többszörös él van. • Ott, ahol nincs él, ott 0 szerepel. Megjegyzés: természetesen nem véletlen a fenti példa. Ez az az adatszerkezet, amit egy térképprogramban leginkább fel lehet majd használni. Ott, ahol többszörös élek vannak, az élek hossza egyenlő hosszúságú. Ez jelöli a kétirányú utcát, amit csupán 2 gráf-ponttal jelölünk meg (ha mondjuk 2x4 sáv van, akkor azt 4 gráf-ponttal előnyösebb megjelölni). Minden egyes gráf pontban 3 értéket tárolunk: 2 koordinátát, valamint egy tengerszinttől mért magasságot. A súlyokat egy segédprogram fogja Útkeresés

38/21.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

kiszámítani, figyelembe véve mind a 3 értéket. Az irányítottság adataira meg kell tanítani a programot. Minimális költségtérítésű feszítőfa A feszítőfa fogalma: Egy g gráfnak egy másik F gráf feszítőfája, ha F tartalmazza G összes pontját, további pontokat nem tartalmaz és G élei közül annyit tartalmaz amennyi F-et összefüggővé teszi de F körmentes (fa). A minimális költségű feszítőfa fogalma: Egy G gráf minimális költségű feszítő fája az a fa-gráf, amely feszítőfája G-nek, és G összes lehetséges feszítőfája közül éleinek összes hossza a legkisebb (elképzelhető több megoldás is). Algoritmusa MinfeszFa(i) PriSorInit(Sor) Segéd.pont:=i Segéd.súly:=0 PriSorBa(Sor,Segéd) Érintett(i):=0 Ciklus PriSorBól(Sor,Segéd) i:=Segéd.pont ÉletBeilleszt(Fa,Érintett(i),i) Ciklus j:=1-től N-ig Ha A(i,j)>0 akkor Ha Érintett(j)=NEMÉRINTETT akkor Segéd.pont:=j Segéd.súly:=A(i,j) PriSorba(Sor,Segéd) Érintett(j):=i különben VanRövidebb(Sor,j,A(i,j),Volt) Ha Volt akkor Érintett(j):=i elágazás vége elágazás vége elágazás vége Ciklus vége amíg nem(PriSorÜres(Sor)) Eljárás vége Megjegyzések: NEMÉRINTETT az az érték, amely jelzi, hogy egy adott pontot a bejárás során már érintettünk, vagy sem. Kezdetben Érintett() vektor minden eleme ezt tartalmazza.

Útkeresés

38/22.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Életbeilleszt (G,x,y) a G gráfba az x,y pontok közé élet illeszt be VanRövidebb (Sor,a,b,Volt) megvizsgálja, hogy szerepel-e az „a” pont a prioritási sorban, ha igen, akkor megvizsgálja, hogy a „b” súlynál nagyobb-e az ott szereplő pont súlya. Ha igen, akkor kicseréli ezt a pontot az „a” pontra, amelynek „b” a súlya. Ha a sor így módosul, akkor Volt=igaz lesz. Legrövidebb út A következő sorok Öveges Ferenc jegyzetéből vannak idézve. A legrövidebb út fogalma A legrövidebb út fogalmát kétféleképpen értelmezhetjük: • A kiindulópontból a végpontig milyen úton kell haladnunk, hogy kevesebb csomóponton lépjünk át, mint bármely más úton? Ennél a feladatnál akár súlyozatlan, akár súlyozott, kezelhetjük úgy a gráfot, mintha éleinek hosszúsága (súlya) egységnyi lenne. • A kiindulópontból a végpontig milyen úton kell haladnunk, hogy az utat alkotó élek összes hossza kisebb legyen, mint bármely más út esetén? Ennél a feladat természetesen súlyozott gráfot feltételez. Egyértelműen látszik, hogy a második eset sokkal általánosabb, ráadásul a térképprogramhoz is ez van közelebb, így ezzel foglalkozok a továbbiakban. A probléma megoldására számos algoritmust dolgoztak ki. Ezek közül alapvetőnek számít a neves holland matematikus Dijkstra 1959-ben közölt algoritmusa, ezért itt is ezt ismertetem. Az algoritmus lényege Lássuk el a gráf minden pontját egy címkével, amely a következő adatokat tartalmazza: • a pillanatnyilag ismert legrövidebb úton az adott pont milyen távolságra van a kiindulóponttól (kezdetben legyen ez az adat minden pont esetén végtelen nagy) • az adott pontnak melyik az a szomszédos pontja, amely felől haladva az előbbi távolságot kaptuk Egy csomópont címkéje kétféle lehet: • ideiglenes: még lehetséges, hogy más irányból rövidebb utat is találunk hozzá a kiindulópontból • állandó: a kiindulópontból már minden hozzá vezető utat megvizsgáltunk, s rövidebb út nem lehetséges Az algoritmus lényege az, hogy meghatározzuk minden pont legrövidebb távolságát a kiindulóponttól számítva, s mivel minden pont címkéje tartalmazza azt is, hogy ezen úton melyik pont előzi meg, a végponttól visszafelé haladva meghatározhatjuk a két pont közötti legrövidebb utat. Nézzük ezt most egy példán keresztül:

Útkeresés

38/23.

Útkeresés

PPC LIVE MAP

Útkeresés

IAR

38/24.

2004. ÁPRILIS 22.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

[Ábra 26 – PROF ÖVEGES FERENC]

Az algoritmus részletesebben 1. Inicializáljuk a gráf-pontok legrövidebb útjait tároló adatszerkezetet. 2. Az aktuális pont legyen a kiinduló pont 3. Járjuk be az aktuális pont minden ideiglenes szomszédját (szélességi bejárás). Ha találunk olyan szomszéd pontot, amelyhez az aktuális pont felől rálépve rövidebb úton jutnánk el a kiinduló ponttól, mint a címkében rögzített korábbi irányból, akkor e pont címkéjét módosítjuk. A módosítás: a kezdőponttól mért távolságnak beírjuk az új irányból mért távolságot, a megelőző pont helyére pedig az aktuális pontot. 4. A gráf összes ideiglenes címkéjét megvizsgálva kiválasztjuk azt a pontot, amely az ideiglenesek közül a legrövidebb úton érhető el a kezdőpontból, vagyis azt, amelyiknek a címkéjében a hosszúság értéke a legkisebb. E pont címkéjét véglegesre állítjuk, ezzel jelezve, hogy e ponthoz nem vezethet a már bejegyzettnél rövidebb út. 5. Legyen most az így kiválasztott pont az aktuális. 6. Ismételjük a 3. résztől a műveletet egészen addig, amíg az aktuális pont azonos nem lesz a végponttal. Az algoritmus pszeudokódja LegrövidebbÚt (A, kezdő, vég, N) Init(állapot) aktuális:=kezdő állapot[aktuális].hossz:=0 állapot[aktuális].címke:=VÉGLEGES ismétlés SzomszédokBejárása(A,N,aktuális,állapot) aktuális:=Minimum(állapot,N) állapot[aktuális].címke:=VÉGLEGES amíg aktuális=vég EredményKiírása(állapot,kezdő,vég) Eljárás vége

Útkeresés

38/25.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

SzomszédokBejárása(A,N,aktuális,állapot) Ciklus i:=1-től N-ig Ha (A[aktuális,i]<>0) és (állapot[i].címke=IDEINGLENES) akkor Ha (állapot[aktuális].hossz+A[aktuális,i])<állapot[i].hossz akkor állapot[i].előző:=aktuális állapot[i].hossz:=aktuális[k].hossz+A[aktuális,i] Elágazás vége Elágazás vége Ciklus vége Eljárás vége A második szimulációs program: Graphs and spanning trees Nem véletlenül gyűjtöttem össze a fenti algoritmusokat. Tervezem egy szépen kivitelezett gráf kezelő program készítését, mely ábrázolja, bejárja, generálja, követi a gráfokat, és a gráfokon végezhető műveleteket, algoritmusokat. Ezen program megírt algoritmusait a későbbiekben hatékonyan lehet beültetni a térképprogramba. Megjegyzések A példákban úgy szerepeltek a súlyozott gráfok, hogy minden élnek a súlya meghatározta az él által összekötött 2 gráf-pont távolságát. Ez mindenképpen fontos dolog, mindenképpen tárolva is lesz a térképprogramban, hiszen így lehet majd arányosan ábrázolni a térképet (maguk a számértékek pontos méréssel, és esetlegesen nagyon pontos GPS koordináták segítségével lesznek kiszámolva). Ezen felül minden egyes élnek lesz más súlya is! Például lesz egy olyan számérték, ami azt határozza meg, hogy az úton milyen gyorsan lehet közlekedni. Mondjuk az autópálya kap 1-es értéket méterenként, a földút meg mondjuk 3,5-öt méterenként (az értékek paraméterek, valószínűleg a tesztelés fogja véglegesíteni őket). Így amikor az ember utat keres, a program különféle utakat fog neki javasolni, és megmondja, hogy melyiket milyen célra szánta (legrövidebb út, legrövidebb idő alatt megtehető út, csúcsforgalmat elkerülő út, közlekedési lámpákat elkerülő út, stb…).

Útkeresés

38/26.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

A PPC LIVEMAP ÉS A GPS Bevezetés Programunk a GPS segítségével képes tudatni a felhasználóval az aktuális helyzetét. Ehhez szükséges egy olyan készülék, amiről le lehet kérdezni a szükséges adatokat. Vámossy Zoltán tanár úrtól kaptuk kipróbálásra két készüléktípust, egy Blox és egy Garmin gyártmányú vevőt. U-Blox MS1E GPS vevőmodul Rövid ismertető A készülék SiRFStar I/LX architektúrásra épül. Központi processzora egy Hitachi Risc CPU. Számítógéppel egy kétirányú Soros Interfészen keresztül lehet vele kommunikálni.

A SiRFStar architektúra elvi felépítése

A GPS modul méretei: 82,5*32mm. Lehetőséget ad teljes GPS jelfeldolgozásra a külső antenna és a soros interfész között. A vevőkészülék egy kívülről kapott +5V-os feszültségforrás segítségével működik. A készülék ezt belső feszültség-átalakító segítségével a működéséhez szükséges CMOS kompatibilis 3,3V-os szintre redukálja. Folyamatos üzemben teljesítményfelvétele: 0,75W. A készülék három működési módot támogat: Normál mód, TricklePower mód, Egyéni beállítási mód. A készülékhez egy kívülről csatlakoztatható alacsony fogyasztású aktív antenna kapcsolódik. Az antennához szükséges feszültséget (4,75V) a készülékből nyeri. A

Útkeresés

38/27.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Hitachi processzor lehetőséget ad egyéb felhasználó által szükségesnek ítélt funkcionalitás tulajdonságok hozzáadására. A készülék hitelessége A GPS hitelessége a GPS kialakításának egyik funkciója a szatellit elhelyezkedés és a kiválasztó lehetőség mellett.

A GPS panel műszaki paraméterei I Feléledési idők Egy GPS különböző feléledési módokat ismer, amik az un. Time-To-First-Fix (TTFF) idő nagyságában különböznek. A feléledési idők definíció szerint: Hideg indulás (Cold start), Meleg indulás (Warm start), Forró indulás (Hot start) és „Újra megszerzés” (Reacquisition). (Ebből a jelenleg használható mód a Hideg feléledés, mivel a többihez külső elem feszültsége szükséges, hogy a kallibrációs és egyéb adatok megmaradjanak a modul memóriájában.)

Útkeresés

38/28.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Technikai áttekintés

1. táblázat

Abszolút maximum értékek: FONTOS! A panel nincs túláram, feszültségtüskék és inverz áram ellen védve! Működési feltételek

2. táblázat

Ezek a feltételek hatással lehetnek a készülék megbízhatóságára. Kimeneti tüskék leírása

3. táblázat

Útkeresés

4. táblázat

38/29.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Soros Interfész Jel Az interfész ki- és bemenetei(TX_A, RX_A, TX_B, RX_B) működési feszültségszintje 3,3V CMOS kompatíbilis jelszint. Az RX_A és az RX_B bemenetek toleránsak a az 5V-os szinttel, és a kimenetek is 5V kompatibilisak. Ha RS-232-es jelszint szükséges, biztosítani kell egy jelszint-átalakítót (pl: MAX232 IC). Az soros A kimenten kerül küldésre a SiRF bináris poziciós adat, a B bemeneten a korrekciós adatokat lehet feltölteni. Az NMEA 0183 kódolású adat opcionális a SiRF helyett. A beállításokat SiRF kódolással lehet feltölteni, de a különleges beállításokhoz szükség van a készülék firmware-jének frissítésére. A nem használt soros portokat nyitva lehet hagyni.

5. táblázat

A soros port általános beállítása Speciális táp-tüskék Külső elemet kell kapcsolni a Vbat bemenetre, hogy engedélyezni lehessen az RTC műveletet, az SRAM frissítést, illetve a GPS meleg és forró indítását. Jel meghatározás

6. táblázat

A GPS készülék csatlakozótüskéinek számozása

Útkeresés

38/30.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Fizikai specifikáció

1. ábra

A GPS panel műszaki paraméterei II

[4. ábra (2/16. oldal)]

A GPS panel műszaki paraméterei III A feszültségszint-konvertáló áramkör Alapja egy MAX232 IC (vagy ezzel kompatibilis, pl. a 10. ábrán látható ICL232), amely tartalmaz két adat csatornát, és egy feszültség-átalakítót. A kapcsoláshoz kell még 4 db 2,2 F-os kondenzátort is. A kapcsolási rajz egy adatcsatornával megvalósítva:

Útkeresés

38/31.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

2. ábra

Az RS232-es csatlakozónak csak a 2-es és a 3-as tüskéjét kellett ehhez felhasználni. A GPS készülék vezetékének 2(Vcc), 3(Tx_A), 5(Rx_A), 8(GND) ereit használtam. A tápfeszültséget a számítógép tápegységéről vettem le, így nem kellett külön áramkört ehhez építeni, és megfelelően stabil és tüskementes feszültséget tudtam használni. A soros port (RS232) tűkiosztása Tű száma

Funkció

Leírás

1

CD

Carriel Data

2

RxD

Recieve Data

3

TxD

Transmit Data

4

DTR

Data Term. Ready

5

GND

Signal Ground

6

DSR

Data Set Ready

7

RTS

Request To Send

8

CTS

Clear To Send

9

RI

Ring Indicator 7. táblázat

3. ábra

A tesztszoftver A készülék gyártójának honlapjáról letöltött specifikáció alapján használtam a szintén onnan szerzett -Center nevű programot. A fenti kapcsolás segítségével működött a készülék 7 műholdat talált meg, ebből 5-ről tudott navigációs adatokat leolvasni. Útkeresés

38/32.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

A koordináták: •

19,035°

•

47,553°

Tengerszint feletti magasság: 168,4m Megjegyzés Az áramkör megépítésére azért volt szükség, mert a kapott csatlakozóval nem működött megfelelően, mint később kiderült, a benne lévő SMD IC egyik lábáról letört a forrasztás, valamint egy másik lába is levált. A Garmin eTrex Vista készülék Ez egy teljesen felhasználóbarát, kézi készülék beépített térképpel, útvonalkövetéssel, helymeghatározással és egyéb hasznos funkciókkal. A számunkra szükséges adatokat a egy speciális átalakító kábel segítségével tudjuk letölteni, szintén az RS-232-es port-on keresztül. Ez a készülék is támogatja többek közt az NMEA 0183-as protokollt is, aminek segítségével le tudjuk a készülékből kérdezni a szükséges GPS adatokat. A választott protokoll a GPS készülékkel való kommunikációhoz Az általam tesztelt GPS készülékekről a megfelelő adatokat többféle protokoll segítségével lehet lekérni. Mind a -Blox, mid a Garmin készülék támogatja az NMea 0183-as kommunikációs szabványt, valamint mindkettő támogat egyéb, a készülék speciális lehetőségeinek kihasználását segítő szabványokat (pl. GARMIN, GARMIN DGPS; SiRF). Az általánosan elfogadott szabvány az NMea 0183, amit minden GPS készülék ismer. Az adatokat karaktersorozatok, más néven mondatok formájában lehet lekérdezni. Minden mondat ’$’ jellel kezdődik, és a (<Soremelés>) jelekkel záródik. Általánosságban három mondatfajtát különböztetünk meg: ’Talker sentences’ – közlő mondatok, ’Proprietary sentences’ – gyártóspecifikus mondatok és ’Query sentences’ – lekérdező mondatok. Talker sentences – Közlő mondatok Általános formája: $ttsss,d1,d2,…, A mondat forrását és tartalomra vonatkozó azonosítót a ’$’ jel utáni öt karakter adja meg, ahol ’tt’ a ’talker’, a beszélő azonosítója, míg az ’sss’ a ’sentence identifier’, a mondat-azonosító. Az adatok ez után a vesszővel elválasztva követik egymást. Ha egy adat nem áll rendelkezésre, a helye üres lesz, azaz a megfelelő helyen nem lesz a vesszők között semmilyen karakter. A mondat tartalmazhat nyolcvannál több karaktert is plusz $, , . A mondat végén, a soremelés előtt van egy ellenőrző mező, ami egy ’*’ jelből és egy kétjegyű hexadecimális számból áll, ami a karakterek XOR (Exclusive OR) kapcsolatából áll elő. Ez a mező a mondat egészére vonatkozik, kivéve a ’$’ és a ’*’ jeleket.

Útkeresés

38/33.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Proprietary sentences – Gyártóspecifikus mondatok Általános formája: $Piii,d1,d2,…. A ’$P’ jelöli, hogy a mondat gyártóspecifikus. A ’iii’ jelöli a gyártó azonosítóját (pl. GRM – Garmin Corporation; SRF – -Blox SiRF protocol). Ezután következnek a gyártó által meghatározott adatok, majd a sorzáró jelek. Query sentences – Lekérdező mondatok Általános formája: $ttllQ,sss, A ’tt’ jelöli, hogy mi a ’talker’, közlő eszköz. Az ’ll’ jelzi, mi a ’listener’ hallgató eszköz. A ’Q’ mondja meg, hogy a mondat lekérdező típusú, az ’sss’ pedig, hogy melyik közlő mondatot várja hallgató eszköz. A GPS eszköz addig fogja ismételni 1 másodpercenként a kért mondatot, amíg más utasítást nem kap. Az adatok lekérdezésének megvalósítása A megfelelő NMEA mondatok: A mi feladatunk szempontjából a ’Talker sentences’, a közlő mondatfajta lesz a legfontosabb, mivel ennek segítségével lehet lekérdezni a GPS koordinátákat. A hosszúsági és szélességi fokok lekérdezésére a $GPGGA kódú mondatot, illetve a $GPGLL-lel kezdődőt tudjuk felhasználni. A $GPGGA a ’Global positioning system fixed data’ jelölése, vagyis a GPS javított adatokat küldi a készülék ebben az üzenetben. Formája:

8. táblázat

– lsd. köv. táblázat – ez a megvalósítás nem támogatja a geoid korrekciókat, az értékek WGS84 elliptikus magasság

a

b

9. táblázat

Útkeresés

38/34.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Pozíció-javítást jelző értékek (Position Fix Indicator) A $GPGLL ’Geographic Position - Latitude/Longitude’ adatokkal a GPS készülék a hosszúsági és szélességi fokot adja meg. Formája:

10. táblázat

Az utóbbi NMEA mondatot jobban tudjuk hasznosítani, mert ebben minden elégséges információ megtalálható.

11. táblázat

A checksum, azaz a hibaellenőrző kód segítségvel az esetleges hibás NMEA mondatokat ki lehet szűrni. Algoritmusa a következő: A soros port-ról történő olvasás Az általam tesztelt GPS készülékekkel soros porton keresztül lehet kommunikálni. Ennek a hardver szintű leírása e dokumentáció elején (5. oldal) található.

4. ábra

Az első tesztet a Windows Hyper Terminal-jával végeztem. Ennek segítségével meg tudtam vizsgálni az egymás után fogadott NMEA mondatokat. A soros port beállítását az NMEA szabványleírásból vettem: Második lépésként kerestem egy soros port komponenst a Delphi 7 fejlesztői környezethez. Több ilyen komponens kipróbálása után ’d3k's ComDrv32’ komponenst választottam, ugyanis ez tűnt a legegyszerűbben kezelhetőnek, és egyéni felhasználók számára ingyenesen felhasználható, így nincsenek benne korlátozások.

Útkeresés

38/35.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

A komponens ZIP állományba tömörítve lehet letölteni. A kitömörítés után a komponenst a ’CPDReg.dcu’ és a ’ComDrv32.dpk’ állományok betöltésével tudtam a Delphi komponensei közé installálni. Ezután a komponens ikonja megtalálható lesz a System komponenspalettán. (a komponens honlapja megtalálható a http://www.mdlive.com/d3k/delphi4 Internetes honlapon). A komponens a beállított COM port-ról a megjelenő adatot egy pufferbe írja. Ha ebben a pufferben van adat, a komponens OnRecievData, illetve az OnRecievePacket eseménye aktivizálódik, és ezek segítségével lehet a soros port-ra érkezett adatokat lekezelni. Jelen esetben ez egy string-kezelést jelent. A metódusok paraméterei: Sender: a metódust hívó osztály azonosítója DataPtr/PacketPtr: az adatfolyam elejére mutató pointer DataSize: Cardinal típusú adat, a pufferben lévő adatfolyam hossza

Útkeresés

38/36.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

IRODALOM JEGYZÉK Útkeresés 1. fejezet URL: http://www.aiguru.com/pathfinding.htm 2. fejezet Amit J. Patel: Game Programming Site URL: http://www.aiguru.com/pathfinding.htm Utolsó módosítás: 2004. január 30. Fő oldal: http://www-cs-students.stanford.edu/~amitp/gameprog.html 3. fejezet Molnár András: Intelligens rendszerek: Robotok (előadás, és diák) 4. fejezet Prof. Öveges Ferenc: Gráfok (előadás és gyakorlat) További információk a témához: http://www.policyalmanac.org/games/binaryHeaps.htm English: Describes using a binary heap to make A* more efficient. Magyar: Leírás a bináris verem eljárásról. http://www.policyalmanac.org/games/twoTiered.htm English: Describes using A* efficiently by using nodes of different densities. http://www.policyalmanac.org/games/aStarTutorial.htm English: Nice description of A* http://www.generation5.org/content/2000/astar.asp English: Another A* descripion - includes C++ source. http://www.geocities.com/SiliconValley/Lakes/4929/astar.html English: Another description of A* (you can never get too many points of view!) including source code. http://www.red3d.com/cwr/steer/gdc99/ English: Craig Reynolds' 1999 Game Developer's Conference presentation. Well worth reading. GPS Klaus Betke: ’The NMEA 0183 Standard’, PDF dokumentum, 2000. május, újraszerkesztve 2001. augusztus, (0183.pdf, letöltve: 2004. 03. 11.) -Blox Corp., ’Protocol Specification – µ-blox GPS-MS1 and GPS-PS1’, 2000. április 4., PDF dokumentum, http://www.u-blox.com/, (letöltve: 2004. 03. 04.) (1-6. ábra; 1-11. táblázat)

Blox Corporation: ’ -Center Evaluation Software User's Guide’, [GPS-SW01002], 2001. Március 15., PDF dokumentum, http://www.u-blox.com (letöltve: 2004. 03. 04.)

Útkeresés

38/37.

Útkeresés

PPC LIVE MAP

IAR

2004. ÁPRILIS 22.

Patrik Eggenberger ( Blox Corp.): ’ -Blox PS1E GPS Reciever Module Datasheet’, [GPS. G1-PS1-00002-B], 2002. Január 9., PDF dokumentum, http://www.u-blox.com/, (letöltve: 2004. 03. 04.)

Útkeresés

38/38.

Útkeresés

Irodalomkutatás. Munkacím: PPC Live Map. GPS & Útkeresés

Recommend Documents