„PgRouting” változatai közötti eltérés

A lap 2016. május 22., 20:44-kori változata

Tartalomjegyzék

1 Bevezetés
2 Telepítés, Architektúra
3 Használat
4 Algoritmusok
5 Kapcsolódó alkalmazások
6 Hivatkozások

Bevezetés

A pgRouting egy nyílt forráskódú, C++-ban írt bővítmény a PostGIS/PostgreSQL térinformatikai adatbázisokhoz. Gráf szerkezetek kezelését teszi lehetővé, így például legrövidebb utakat, csomópontok távolságát és egyéb hálózati elemzést igénylő feladatokat oldatunk meg vele.

Telepítés, Architektúra

A PostGIS újabb verziói (2.0+) már tartalmazzák a pgRoutingot, így nem szükséges külön telepíteni, csak aktiválni kell:

CREATE EXTENSION pgrouting;

A pgRouting két fő összetevőből áll:

Egy C modul, amely egy PostgreSQL-ben átadott lekérdezést használ a gráf felépítéséhez
C++ modulok, amelyek a lekérdezést úgynevezett boost gráffá alakítják, és futtatják az útvonal-választást.

Hogy mely összetevőt használja a program futása során, az az algoritmus fajtájától függ.

A függvénykönyvtár szerkezete pedig a következőképp néz ki: cmake/ - cmake fájlok

 CMakeLists.txt         - Top level cmake 
 doc/                   - Top level doc, a nem forráslgoritmus-specifikus dokumentáció helye
   themes/              - Sphinx téma a doc-nak
   static/              - dokumentáció képei
 src/                  
   astar/               - A* algoritmus
   common/              - pgRouting projektekben szükséges közös fájlok
   dijkstra/            - Dijkstra algoritmus
   driving_distance/    - Vezetési távolság
   trsp/                - Legrövidebb utak kanyarodási korlátokkal
   tsp/                 - Utazó ügynök
 tools/                 - Tesztelési eszközök

Használat

Adatok betöltése

A vektoros térképi adatok adatbázis-táblába betöltésére számos eszköz áll rendelkezésre, például:

osm2po: OpenStreetMap (OSM) adatok konvertálása SQL formátumba, pgRouting-nak megfelelő formátumban
shp2pgsql: PostgreSQL shapefile betöltője
ogr2ogr: vektoros adatok konverziója
osm2pgsql: OSM adat betöltése postgreSQL-be

Előfeldolgozás

Amikor egy GIS fájlt olvasunk be az adatbázisunkba a pgRouting számára, nem feltétlenül követnek alkalmas topológiát a rekordok. A helytelen topológia hibás útvonalakhoz vezetne. Hogy használható adattáblát kapjunk, csomópontokra van szükségünk minden egyes útkereszteződésnél. Az útvonalhálózat megfelelő topológiájának kialakítását segítheti a pgr_createTopology vagy a pgr_nodeNetwork parancs. Működésük hasonló. Az utóbbi beolvassa a „csúcstalan” hálózat adatbázis-tábláját, majd egy új táblába írja a már felcsúcsozott éleket. Paraméterei

éltábla neve,
tolerancia: a toleranciaértéken belüli csomópontok egy csomópontot fognak alkotni
id, az éltábla elsődleges kulcsa,
geometriát tartalmazó oszlop
kimeneti tábla szuffixe. Alapértelmezetten edge_table_noded.

Lekérdezés szintaxis

Minden pgRouting lekérdezés az alábbi formátumot követi:

SELECT pgr_<algorithm>(<SQL for edges>, start, end, <additonal options>),

ahol a pgr_előtaggal hívjuk meg a lentebb ismertetett algoritmusok egyikét. A belső SQL lekérdezéssel adjuk meg a táblát, amelyre az algoritmust futtatjuk, a kezdő- és végponto(ka)t, valamint opcionális további szűrési feltételeket. Például, ha a pgRouting dokumentációjában bemutatott mintaadatokkal dolgozunk, az alábbi lekérdezéssel a 2. csúcsból a 3. sorszámúba vezető legrövidebb utat kapjuk meg:

SELECT * FROM pgr_dijkstra(
     'SELECT id, source, target, cost, reverse_cost 
     FROM edge_table', 2, 3);

Algoritmusok

Dijkstra algoritmus

A Dijkstra algoritmus egy súlyozott élű, irányított Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G=(V,E)} gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w} . Az algoritmus mohó módszert használ. Legyen a kiindulási pont Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} , a célállomás pedig Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} . Az algoritmus egy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az $s$ -ből hozzájuk vezető legrövidebb út hosszát. Ezen kívül minden Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u} csúcsról nyilvántartunk az algoritmus futása során egy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[u]} értéket, ami az $s$ -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u} -ba vezető addig megismert legrövidebb út hossza.

Kezdetben Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} üres, $D[s]=0$ és minden más Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} csúcsra Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[v]=\infty} . Ezután minden iterációban kiválasztunk a $V\setminus H$ halmazból egy olyan Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x} csúcsot, amelyre Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[x]} minimális, áttesszük $x$ -et Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} -ba, majd Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x} minden olyan $v$ szomszédjára, amely nincs Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} -ban frissítjük a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[v]} értéket: $D[v]=\min\{D[v],D[x]+w(x,v)\}$ . Az algoritmus véget ér, amikor Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} átkerül Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} -ba, ekkor Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[t]} egy legrövidebb $s$ -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be vezető út hossza. Az algoritmus kis módosítással egy legrövidebb utat is megad Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be.

Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén $O(|V|^{2})$ , szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(|E|+|V|\log |V|)} .

Kétirányú Dijkstra algoritmus

A kétirányú Dijkstra algoritmus szintén egy súlyozott élű, irányított Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G=(V,E)} gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont $s$ , a célállomást pedig Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} . A Dijkstra algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} csúcs mindkét irányból bekerül a Dijkstra algoritmusnál definiált $H$ halmazba (pontosabban a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H_s} és a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H_t} halmazba is). Egy alternatív lehetőség, hogy a $H_{s}$ és a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H_t} halmazok közül minden egyes iterációban csak azt bővítjük, amelyiknél Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[x]} kisebb. Az algoritmus kis módosítással egy legrövidebb utat is megad $s$ -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be.

k-Dijkstra algoritmus

A Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k} -Dijkstra algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából több adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Valójában a Dijkstra algoritmus a gráf egy adott csúcsából az összes többi csúcsba vezető legrövidebb utat megtalálja, így akárhány célállomást megadhatunk. Az algoritmus akkor fejeződik be, amikor minden egyes célállomás bekerült a Dijkstra algoritmusnál definiált Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} halmazba. Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége szomszédsági mátrixos gráfábrázolás esetén Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(|V|^2)} , szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva $O(|E|+|V|\log |V|)$ .

A* algoritmus

Az $A^{\ast }$ algoritmus egy súlyozott élű, irányított Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G=(V,E)} gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle A^\ast} algoritmus a Dijkstra algoritmus általánosítása, és szintén csak nem negatív élsúlyok esetén működik. Jelölje a súlyfüggvényt Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w} . Az algoritmus mohó módszert használ. Legyen a kiindulási pont $s$ , a célállomás pedig Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} . Az algoritmus egy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} halmazban tárolja azon csúcsokat, amelyeknek már ismerjük az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből hozzávezető legrövidebb út hosszát, egy $M$ halmazban pedig azokat, amelyeket már elértünk Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből, de az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből hozzájuk vezető legrövidebb út hosszát még nem ismerjük. Minden Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u} csúcsról nyilvántartunk az algoritmus futása során három értéket: $D[u]$ az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u} -ba vezető addig megismert legrövidebb út hossza, Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle C[u]} egy nem negatív heurisztikus alsó becslés az $u$ -ból Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be vezető legrövidebb út hosszára, amelyre az is teljesül, hogy az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u} -ból bármely Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} csúcsba vezető legrövidebb út hosszára $C[u]-C[v]$ alsó korlát (például egy térkép esetén Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle u} és Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} légvonalban mért távolsága), végül Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle B[u]=D[u]+C[u]} .

Kezdetben $H$ üres, Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle M} -ben csak az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} csúcs van, és $B[s]=0$ . Ezután minden iterációban kiválasztunk az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle M} halmazból egy olyan Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x} csúcsot, amelyre Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle B[x]} minimális, áttesszük $x$ -et Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} -ba, majd Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle x} minden olyan Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} szomszédjára, amely nincs $H$ -ban frissítjük először a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[v]} értéket: Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[v]=\min\{D[v],D[x]+w(x,v)\}} , majd a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle B[v]} értéket: $B[v]=\min\{B[v],D[v]+C[v]\}$ , végül áttesszük Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} -t Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle M} -be. Az algoritmus véget ér, amikor Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} átkerül $M$ -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H} -ba, ekkor Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle B[t]} egy legrövidebb Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből $t$ -be vezető út hossza. Az algoritmus kis módosítással egy legrövidebb utat is megad Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} -ből Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle t} -be.

A tapasztalat azt mutatja, hogy az $A^{\ast }$ algoritmus számos esetben hatékonyabb, mint a Dijkstra algoritmust.

Kétirányú $A^{\ast }$ algoritmus

A kétirányú $A^{\ast }$ algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út megtalálására szolgáló módszer. Az algoritmus csak nem negatív élsúlyok esetén működik. Legyen a kiindulási pont $s$ , a célállomást pedig $t$ . Az $A^{\ast }$ algoritmust futtatjuk a kiindulási pontból az eredeti gráfon, és párhuzamosan a célállomásból a transzponált gráfon (amelyet úgy kapunk az eredeti gráfból, hogy az élek irányítását megfordítjuk). Akkor állunk meg, ha egy $v$ csúcs mindkét irányból bekerül az $A^{\ast }$ algoritmusnál definiált $H$ halmazba (pontosabban a $H_{s}$ és a $H_{t}$ halmazba is). Az algoritmus kis módosítással egy legrövidebb utat is megad s-ből t-be.

Yen algoritmus

A Yen algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf egy adott csúcsából egy adott másik csúcsába vezető legrövidebb út mellett megtalálja a második, harmadik, …, $k$ -adik legrövidebb (egyszerű) utat is. Az algoritmus csak nem negatív élsúlyok esetén működik.

Az algoritmus költsége $O(k|V|(|E|+|V|\log |V|))$ .

Floyd-Warshall algoritmus

A Floyd-Warshall algoritmus egy súlyozott élű, irányított $G=(V,E)$ gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt $w$ . Az algoritmus dinamikus programozást használ. Legyen a gráf csúcshalmaza $\{v_{1},v_{2},\ldots ,v_{n}\}$ . Az algoritmus minden $0\leqslant k\leqslant n$ esetén meghatározza a $v_{i}$ -ből $v_{j}$ -be menő legrövidebb olyan (egyszerű) út $T_{k}[v_{i},v_{j}]$ hosszát, amelyen a közbülső csúcsok a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \{v_1,v_2,\ldots,v_k\}} halmazból kerülnek ki: Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T_0[v_i,v_j]=w(v_i,v_j)} , és Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle T_k[v_i,v_j]=\min\{T_{k-1}[v_i,v_j],T_{k-1}[v_i,v_k]+T_{k-1}[v_k,v_j]\}} ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k>0} . Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(|V|^3)} .

Johnson algoritmus

A Johnson algoritmus egy súlyozott élű, irányított Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G=(V,E)} gráf bármely két csúcsa közötti legrövidebb út megtalálására szolgáló módszer. Az algoritmus negatív élsúlyok esetén is működik, ha a gráf nem tartalmaz negatív összhosszúságú irányított kört. Jelölje a súlyfüggvényt Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w} . Az algoritmus ritka gráfokon teljesít igazán jól.

Vegyünk fel egy új Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} csúcsot, és vezessünk $s$ -ből nulla súlyú éleket Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G} csúcsaiba. Jelölje az így kapott gráfot Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G'} . Futtassuk le Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G'} -re a Bellman-Ford algoritmust az Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle s} kezdőcsúccsal. Az algoritmus által szolgáltatott távolságérték a gráf egy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} csúcsára legyen Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle D[v]} . Átsúlyozzuk a $G$ gráf éleit: legyen Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w'(u,v)=w(u,v)+D[u]-D[v]} minden Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (u,v)} élre. Most $w'$ egy nem negatív súlyfüggvény Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G} -n. Futtassuk ezzel a súlyfüggvénnyel a Dijkstra algoritmust a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G} gráf minden csúcsából. Egy legrövidebb $u$ -ból Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle v} -be vezető út hossza ezután a kapott érték mínusz $D[u]-D[v]$ . Az algoritmus kis módosítással magukat a legrövidebb utakat is megadja.

Az algoritmus költsége szomszédsági listás gráfábrázolás esetén Fibonacci kupacot használva Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(|V|(|E|+|V|\log |V|))} .

Utazó ügynök probléma

Az utazó ügynök probléma a következő. Adott városoknak egy listája, és adott bármely két város között a távolság. Határozzunk meg egy olyan körutat, amely minden városon pontosan egyszer halad át, és a hossza minimális. A problémára nem ismert polinomiális költségű algoritmus. A program ún. simulated annealing technikán alapuló algoritmust használ egy jó közelítő megoldás meghatározására.

Legrövidebb utak kanyarodási korlátokkal

Az algoritmus egy súlyozott élű, irányított Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G=(V,E)} gráf adott csúcsából egy másik adott csúcsába vezető legrövidebb út meghatározásakor képes figyelembe venni, hogy két csatlakozó él egymás utáni bejárása extra költséggel bírhat. Ezeket a megszorításokat egy külön táblában adhatjuk meg. Tapasztalat szerint az algoritmus közel olyan gyors, mint az $A^{\ast }$ algoritmus.

Vezetési távolság

Egy súlyozott élű, irányított Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle G=(V,E)} gráfban a Dijkstra algoritmus felhasználásával megadja azon csúcsokat, melyekbe egy vagy több adott csúcsból egy adott értéknél rövidebb úton el lehet jutni.

Kapcsolódó alkalmazások

Útvonal-meghatározásra alkalmas adathalmazt például OpenStreetMap (OSM) térképekből nyerhetünk ki. Ehhez egyik alkalmas segédeszköz az OSM2PO alkalmazás, amely megfelelő topológiájú SQL fájlt állít elő a megadott térképrészlethez, amely egyből alkalmas a pgRouting-gal vagy QGIS-szel való feldolgozásra. Az OSM2PO révén vizualizálhatjuk is a legrövidebb utakat. A programmal előállított SQL táblákban minden útkereszteződéshez tartozik egy rekord, melyben a következőket tároljuk:

koordináták

Útvonal megjelenítése OSM2PO webszolgáltatásként
név
csomópont azonosító
lehetséges továbbhaladási irány (élek)
útszakasz hossza
megengedett sebesség
költség

A demo.bat fájl szerkesztésével specifikálhatjuk térképünk paramétereit, például, hogy mely térképrészleten dolgozzunk. A Mapzen oldalán kész .pbf formátumú városrészleteket találhatunk, melyeket kompatibilisek az Osm2Po-val. A fájl futtatásával előáll egy .sql fájl is, melyet importálhatunk a postGIS adatbázisunkba, és akár pgRouting lekérdezéseket is futtathatunk rajta. Amíg fut a program, helyi webszerveren (localhost:8888/Osm2poService) jeleníthető meg az importált térképrészlet, melyen az útkeresést is kipróbálhatjuk.

Hivatkozások

Fejlesztőkörnyezet telepítési útmutató

pgRouting Manual

pgRouting Workshop

Loading OpenStreetMap with Osm2Po and route querying