streamalism.org

1. Bemutatkozás

Az útvonalkereső algoritmusok a térképek navigálásának technikái, amely lehetővé teszi számunkra, hogy megtaláljuk az útvonalat két különböző pont között. A különböző algoritmusoknak különböző előnyei és hátrányai vannak, gyakran az algoritmus hatékonysága és az általa generált útvonal hatékonysága szempontjából.

2. Mi az útkereső algoritmus?

A Pathfinding Algorithm egy olyan technika, amellyel a csomópontokból és élekből álló gráfot a grafikonon keresztüli útvonalává konvertálhatjuk. Ez a grafikon egyáltalán bármi lehet, amelyet be kell vonni. Ehhez a cikkhez megkíséreljük átjárni a londoni metró rendszer egy részét:

(A sameboat „London Underground Overground DLR Crossrail térképe” a CC BY-SA 4.0 engedélyével rendelkezik)

Ez sok érdekes elemet tartalmaz:

• Lehet, hogy nincs közvetlen útvonalunk a kiinduló és a végpont között. Például elmehetünk közvetlenül az „Earl's Court” -tól a „Monument” -ig, de nem az „Angel” -ig.
• Minden egyes lépésnek külön költsége van. Esetünkben ez az állomások közötti távolság.
• Minden megálló csak a többi megálló kis részhalmazához kapcsolódik. Például a „Regent's Park” csak a „Baker Street” és az „Oxford Circus” -hoz kapcsolódik.

Valamennyi útkereső algoritmus az összes csomópont - esetünkben állomás - és a közöttük lévő kapcsolatok, valamint a kívánt kezdő és végpontok gyűjteményét veszi be. A kimenet tipikusan az a csomópontkészlet, amely az elejétől a végéig elér minket abban a sorrendben, amelyre mennünk kell.

3. Mi az A *?

Az A * egy specifikus útkereső algoritmus, először 1968-ban jelentette meg Peter Hart, Nils Nilsson és Bertram Raphael. Általában azt tartják a legjobb algoritmusnak, amelyet akkor kell használni, ha nincs lehetőség az útvonalak előzetes kiszámítására, és nincsenek korlátozások a memória használatára.

A memória és a teljesítmény összetettsége egyaránt lehet O (b ^ d) legrosszabb esetben, tehát bár ez mindig a leghatékonyabb útvonalat fogja kidolgozni, ez nem mindig a leghatékonyabb módja ennek.

Az A * valójában a Dijkstra algoritmusának egy változata, ahol további információk állnak rendelkezésre a következő használni kívánt csomópont kiválasztásához. Ennek a kiegészítő információnak nem kell tökéletesnek lennie - ha már tökéletes információval rendelkezünk, akkor az útkeresés értelmetlen. De minél jobb, annál jobb lesz a végeredmény.

4. Hogyan működik az A *?

Az A * algoritmus úgy működik, hogy iteratív módon választja ki az eddigi legjobb útvonalat, és megpróbálja megnézni, mi a legjobb következő lépés.

Ha ezzel az algoritmussal dolgozunk, több adatunk van, amelyeket nyomon kell követnünk. A „nyitott halmaz” az összes olyan csomópont, amelyet jelenleg figyelembe veszünk. Ez nem minden csomópont a rendszerben, hanem minden csomópont, amelyből megtehetjük a következő lépést.

Ezenkívül nyomon követjük az aktuális legjobb pontszámot, a becsült összpontszámot és a jelenlegi legjobb előző csomópontot a rendszer egyes csomópontjaihoz.

Ennek részeként képesnek kell lennünk két különböző pontszám kiszámítására. Az egyik az egyik csomópontról a másikra jutás pontszáma. A második egy heurisztika, amely becsüli a költségeket bármelyik csomóponttól a célig. Ennek a becslésnek nem kell pontosnak lennie, de a nagyobb pontosság jobb eredményeket fog hozni. Az egyetlen követelmény az, hogy mindkét pontszám összhangban legyen egymással - vagyis ugyanazokban az egységekben legyenek.

A kezdet kezdetén nyitott halmazunk a kezdő csomópontunkból áll, és egyáltalán nincs információnk más csomópontokról.

Minden iteráción:

• Válassza ki a nyitott halmazunkból azt a csomópontot, amelynek a becsült összpontszáma a legalacsonyabb
• Távolítsa el ezt a csomópontot a nyitott készletből
• Adja hozzá a nyitott halmazhoz az összes olyan csomópontot, amelyet elérhetünk belőle

Amikor ezt megtesszük, az új pontszámot is kidolgozzuk ettől a csomóponttól az egyes új pontokig, hogy lássuk, javul-e ez az eddigieken, és ha igen, akkor frissítjük, mit tudunk erről a csomópontról.

Ez akkor ismétlődik, amíg a nyitott halmazunkban lévő csomópont, amelynek a becsült összpontszáma a legalacsonyabb, nem az úti célunk lesz, amikor elérjük az utunkat.

4.1. Dolgozott példa

Kezdjük például a „Marylebone” -tól, és próbáljuk meg megtalálni az utat a „Bond Street” felé.

Kezdetben nyitott készletünk csak a „Marylebone” -ból áll.. Ez azt jelenti, hogy implicit módon ez az a csomópont, amelyre a legjobb „becsült összpontszámot” kaptuk.

A következő megállóink ​​lehetnek vagy „Edgware Road”, 0,4403 km költséggel, vagy „Baker Street”, 0,4153 km költséggel. Az „Edgware Road” azonban rossz irányba mutat, ezért az innen a célig tartó heurisztikánk 1,4284 km-es pontszámot ad, míg a „Baker Street” 1,0753 km-es heurisztikus pontszámot ad.

Ez azt jelenti, hogy az iteráció után a nyitott készletünk két bejegyzésből áll - az „Edgware Road”, amelynek becsült összpontszáma 1,8687 km, és a „Baker Street”, a becsült összpontszám 1,4906 km.

Második iterációnk akkor kezdődik a „Baker Street” -től, mivel ennek a legalacsonyabb a becsült összpontszáma. Innen következő állomásaink lehetnek „Marylebone”, „St. John's Wood ”, a„ Great Portland Street ”, a Regent's Park” vagy a “Bond Street”.

Mindezeket nem fogjuk feldolgozni, de vegyük érdekes példaként a „Marylebone” -t. Az odaérkezés költsége ismét 0,4153 km, de ez azt jelenti, hogy a teljes költség már 0,8306 km. Ezenkívül az innen a célig tartó heurisztika 1.323 km-es eredményt ad.

Ez azt jelenti, hogy a becsült összpontszám 2,1536 km lenne, vagyis rosszabb mint a csomópont előző pontszáma. Ennek azért van értelme, mert ebben az esetben többletmunkát kellett végeznünk, hogy sehova se érjünk. Ez azt jelenti, hogy ezt nem tartjuk életképes útnak. Mint ilyen, a „Marylebone” részletei nem frissülnek, és nem kerülnek vissza a nyitott készletbe.

5. Java implementáció

Most, hogy megbeszéltük, hogyan működik ez, valósítsuk meg valóban. Építeni fogunk egy általános megoldást, majd végrehajtjuk a kódot, amely ahhoz szükséges, hogy működjön a londoni metró számára. Ezután más forgatókönyvekhez is felhasználhatjuk, csak az adott részek megvalósításával.

5.1. A grafikon ábrázolása

Először is képesnek kell lenniünk arra, hogy ábrázoljuk a grafikonunkat, amelyet be akarunk haladni. Ez két osztályból áll - az egyes csomópontokból, majd a grafikon egészéből.

Az egyes csomópontjainkat egy úgynevezett interfésszel képviseljük GraphNode:

nyilvános felület GraphNode {String getId (); }

Minden csomópontunknak rendelkeznie kell azonosítóval. Minden más csak erre a grafikonra vonatkozik, és nincs szükség az általános megoldáshoz. Ezek az osztályok egyszerű Java-babok, különösebb logika nélkül.

A teljes grafikonunkat ezután egy egyszerűen nevezett osztály képviseli Grafikon:

public class Graph {private final Set csomópontok; privát végleges térkép kapcsolatok; public T getNode (String id) {return nodes.stream () .filter (node ​​-> node.getId (). egyenlő (id)) .findFirst (). vagyElseThrow (() -> new IllegalArgumentException ("Nem található csomópont Azonosító ")); } public set getConnections (T csomópont) {return links.get (node.getId ()). stream () .map (this :: getNode) .collect (Collectors.toSet ()); }}

Ez eltárolja a gráfunk összes csomópontját, és tudja, hogy melyik csomópont melyikhez kapcsolódik. Ezután bármelyik csomópontot megszerezhetjük azonosító szerint, vagy az összes csomópontot egy adott csomóponthoz csatlakoztatjuk.

Ezen a ponton képesek vagyunk ábrázolni a kívánt grafikonformákat, tetszőleges számú éllel, tetszőleges számú csomópont között.

5.2. Lépések az útvonalunkon

A következő dologra szükségünk van, a mechanizmusunk az útvonalak megtalálásához a grafikonon keresztül.

Ennek első része valamilyen módon hozható létre pontszám bármely két csomópont között. Majd a Gólszerző interfész mind a ponthoz a következő csomópontig, mind a becslésig a célig:

nyilvános felület Scorer {double computeCost (T from, T to); }

Ha megadjuk a kezdő és a végpontot, akkor kapunk egy pontszámot a közöttük való utazásért.

Szükségünk van egy csomópontunk körüli burkolatra, amely további információkat tartalmaz. Ahelyett, hogy a GraphNode, ez egy RouteNode - mert ez egy csomópont a számított útvonalunkon, nem pedig a teljes grafikonon:

osztály RouteNode megvalósítja összehasonlítható {privát végső T áram; magán T előző; privát kettős útvonalScore; privát dupla becsültScore; RouteNode (T current) {this (current, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode (T aktuális, T előző, dupla routeScore, dupla becsültScore) {this.current = aktuális; ez.korábbi = előző; this.routeScore = routeScore; this.estimatedScore = becsült pontszám; }}

Mint GraphNode, ezek egyszerű Java-babok, amelyeket az egyes csomópontok aktuális állapotának tárolására használnak az aktuális útvonal-számításhoz. Egy egyszerű konstruktort adtunk ennek az általános esetnek, amikor először meglátogattunk egy csomópontot, és még nincsenek további információink róla.

Ezeknek is lenniük kell Hasonló bár azért, hogy az algoritmus részeként a becsült pontszám alapján tudjuk őket rendezni. Ez azt jelenti, hogy a összehasonlítani() módszer a KÖV követelményeinek teljesítésére Hasonló felület:

@Orride public int CompareTo (RouteNode other) {if (this.estimatedScore> other.estimatedScore) {return 1; } else if (this.estimatedScore <other.estimatedScore) {return -1; } else {return 0; }}

5.3. Útvonalunk megtalálása

Most abban a helyzetben vagyunk, hogy valóban generálhassuk útvonalainkat a grafikonon keresztül. Ez egy osztály lesz RouteFinder:

public class RouteFinder {private final Graph graph; privát végső gólszerző nextNodeScorer; privát végső gólszerző targetScorer; public List findRoute (T from, T to) {dobja be az új IllegalStateException szolgáltatást ("Nem található útvonal"); }}

Megvan a grafikon, amelyen megtaláljuk az útvonalakat, és a két pontszerzőnk - egyet a következő csomópont pontos pontszámához, egyet pedig az úti célunkra becsült pontszámhoz. Van egy módszerünk is, amely egy kezdő és egy végső csomópontot vesz fel, és kiszámítja a kettő közötti legjobb útvonalat.

Ez a módszer az A * algoritmusunk. A kódunk többi része belemegy a módszerbe.

Kezdjük néhány alapvető beállítással - a csomópontok „nyitott készletével”, amelyet a következő lépésnek tekinthetünk, valamint térképet minden eddig felkeresett csomópontról és arról, amit tudunk róla:

Queue openSet = új PriorityQueue (); Térkép allNodes = új HashMap (); RouteNode start = új RouteNode (from, null, 0d, targetScorer.computeCost (from, to)); openSet.add (start); allNodes.put (from, start);

A nyitott halmazunknak kezdetben egyetlen csomópontja van - a kiindulási pontunk. Erre nincs korábbi csomópont, 0-s pontszám van az odajutáshoz, és becslést kaptunk arról, hogy milyen messze van az úti célunktól.

Az a PriorityQueue mert a nyitott halmaz azt jelenti, hogy automatikusan a lehető legjobb belépést kapjuk belőle, a összehasonlítani() módszer korábbi.

Most addig ismételjük, amíg vagy elfogynak a csomópontok, hogy megnézzük, vagy a legjobb elérhető csomópont a célunk:

while (! openSet.isEmpty ()) {RouteNode next = openSet.poll (); if (next.getCurrent (). egyenlő (to)) {List route = new ArrayList (); RouteNode current = következő; do {út.add (0, aktuális.getCurrent ()); current = allNodes.get (current.getPrevious ()); } while (aktuális! = null); visszaút; } // ...

Ha megtaláltuk az úti célt, akkor megépíthetjük az útvonalat úgy, hogy többször megnézzük az előző csomópontot, amíg el nem érjük a kiindulási pontot.

Ezután, ha még nem értük el a célunkat, kidolgozhatjuk a következő lépéseket:

 graph.getConnections (next.getCurrent ()). forEach (kapcsolat -> {RouteNode nextNode = allNodes.getOrDefault (kapcsolat, új RouteNode (kapcsolat)); allNodes.put (kapcsolat, nextNode); dupla newScore = next.getRouteScore () + nextNodeScorer.computeCost (next.getCurrent (), kapcsolat); if (newScore <nextNode.getRouteScore ()) {nextNode.setPrevious (next.getCurrent ()); nextNode.setRouteScore (newScore); nextNode.setEstimatedScore (newScore + targetScore + targetScore + targetScore + targetScore + targetScore .computeCost (connection, to)); openSet.add (nextNode);}}); dobja az új IllegalStateException szolgáltatást ("Nem található útvonal"); }

Itt iterálunk a grafikonunk kapcsolt csomópontjain. Ezek mindegyikéhez megkapjuk a RouteNode hogy megvan rá - szükség esetén újat hozhatunk létre.

Ezután kiszámoljuk ennek a csomópontnak az új pontszámát, és megnézzük, olcsóbb-e, mint amit eddig rendelkeztünk. Ha igen, akkor frissítjük, hogy megfeleljen ennek az új útvonalnak, és a következő alkalommal megfontolás céljából hozzáadjuk a nyitott készlethez.

Ez a teljes algoritmus. Addig ismételjük ezt, amíg vagy el nem érjük a célunkat, vagy nem sikerül odaérnünk.

5.4. Részletes információk a londoni metróról

Amit eddig rendelkezünk, az egy általános A * útkereső, de hiányzik a pontos felhasználási esetünkhöz szükséges sajátosságoktól. Ez azt jelenti, hogy mindkettőnek konkrét megvalósítására van szükségünk GraphNode és Gólszerző.

Csomópontjaink a földalatti állomásai, és ezeket a Állomás osztály:

public class Station megvalósítja a GraphNode {private final String id; privát végleges karakterlánc neve; magán végső kettős szélesség; magán végső kettős hosszúság; }

A név hasznos a kimenet megtekintéséhez, a szélesség és hosszúság pedig a pontszámainkhoz.

Ebben a forgatókönyvben csak a Gólszerző. Ehhez a Haversine képletet fogjuk használni, hogy kiszámoljuk a két szélességi és hosszúsági pár közötti egyenes távolságot:

public class HaversineScorer végrehajtja a Scorer {@Override public double computeCost (Station from, Station to) {double R = 6372.8; // Föld sugara, kilométerben dupla dLat = Math.toRadians (to.getLatitude () - from.getLatitude ()); dupla dLon = Math.toRadians (to.getLongitude () - from.getLongitude ()); kettős lat1 = Math.toRadians (from.getLatitude ()); kettős lat2 = Math.toRadians (to.getLatitude ()); dupla a = Math.pow (Math.sin (dLat / 2), 2) + Math.pow (Math.sin (dLon / 2), 2) * Math.cos (lat1) * Math.cos (lat2); dupla c = 2 * Math.asin (Math.sqrt (a)); visszatér R * c; }}

Most már szinte minden megvan, hogy kiszámítsuk az útvonalakat bármely két állomáspár között. Csak az hiányzik a közöttük lévő kapcsolatok grafikonja. Ez elérhető a GitHub-ban.

Használjuk az útvonal feltérképezéséhez. Generálunk egyet Earl's Court-tól Angelig. Ennek számos különböző lehetősége van az utazáshoz, legalább két csővezetéken:

public void findRoute () {List route = routeFinder.findRoute (underground.getNode ("74"), underground.getNode ("7")); System.out.println (route.stream (). Map (Station :: getName) .collect (Collectors.toList ())); }

Ez generálja az Earl's Court -> South Kensington -> Green Park -> Euston -> Angel útvonalát.

A nyilvánvaló út, amelyet sokan tettek volna, valószínűleg Earl grófja -> Emlékmű -> Angyal lesz, mert ez kevesebb változtatást eredményezett. Helyette, ez lényegesen közvetlenebb utat tett meg, annak ellenére, hogy több változást jelentett.

6. Következtetés

Ebben a cikkben megnéztük, mi az A * algoritmus, hogyan működik és hogyan lehet ezt saját projektjeinkben megvalósítani. Miért ne venné ezt el és bővítené saját használatra?

Esetleg megpróbálja kiterjeszteni, hogy figyelembe vegye a csővezetékek közötti váltásokat, és megnézze, hogy ez hogyan befolyásolja a kiválasztott útvonalakat?

És ismét, a cikk teljes kódja elérhető a GitHubon.