Implementácia A * Pathfinding v Jave

1. Úvod

Algoritmy hľadania trasy sú techniky navigácie v mapách, čo nám umožňuje nájsť trasu medzi dvoma rôznymi bodmi. Rôzne algoritmy majú rôzne výhody a nevýhody, často z hľadiska efektívnosti algoritmu a efektívnosti trasy, ktorú generuje.

2. Čo je to algoritmus hľadania cesty?

Pathfinding Algorithm je technika na konverziu grafu pozostávajúceho z uzlov a hrán na trasu cez graf.. Tento graf môže byť čokoľvek, čo potrebuje prechod. V tomto článku sa pokúsime prekonať časť systému londýnskeho metra:

(„Mapa London Underground Overground DLR Crossrail“ spoločnosťou sameboat má licenciu podľa CC BY-SA 4.0)

Má veľa zaujímavých súčastí:

  • Medzi východiskovým a konečným bodom môžeme alebo nemusíme mať priamu cestu. Napríklad môžeme ísť priamo z „Earl's Court“ do „Monument“, ale nie do „Angel“.
  • Každý jeden krok má osobitné náklady. V našom prípade ide o vzdialenosť medzi stanicami.
  • Každá zastávka je spojená iba s malou podskupinou ostatných zastávok. Napríklad „Regent's Park“ je priamo spojený iba s „Baker Street“ a „Oxford Circus“.

Všetky algoritmy hľadania cesty berú ako vstup súbor všetkých uzlov - v našom prípade staníc - a spojení medzi nimi, ako aj požadované počiatočné a konečné body. Výstupom je zvyčajne sada uzlov, ktoré nás dostanú od začiatku do konca v poradí, v akom musíme ísť.

3. Čo je to A *?

A * je jeden špecifický algoritmus hľadania cesty, ktoré prvýkrát publikovali v roku 1968 Peter Hart, Nils Nilsson a Bertram Raphael. Všeobecne sa považuje za najlepší algoritmus, ktorý sa má použiť, keď nie je možné vopred vypočítať trasy a neexistujú žiadne obmedzenia týkajúce sa využitia pamäte..

Zložitosť pamäte aj výkonu môže byť O (b ^ d) v najhoršom prípade, takže aj keď vždy vypracuje najefektívnejšiu trasu, nie vždy je to najefektívnejší spôsob.

A * je vlastne variácia Dijkstrovho algoritmu, kde sú poskytované ďalšie informácie, ktoré pomôžu pri výbere ďalšieho uzla, ktorý sa má použiť. Tieto ďalšie informácie nemusia byť dokonalé - ak už máme dokonalé informácie, potom je hľadanie cesty zbytočné. Ale čím to bude lepšie, tým lepší bude konečný výsledok.

4. Ako A * funguje?

Algoritmus A * funguje tak, že iteratívne vyberá najlepšiu doterajšiu trasu a pokúša sa zistiť, aký je najlepší ďalší krok.

Pri práci s týmto algoritmom máme niekoľko údajov, ktoré musíme sledovať. „Otvorená množina“ sú všetky uzly, ktoré momentálne zvažujeme. Toto nie je každý uzol v systéme, ale je to každý uzol, z ktorého by sme mohli urobiť ďalší krok.

Budeme tiež sledovať aktuálne najlepšie skóre, odhadované celkové skóre a aktuálny najlepší predchádzajúci uzol pre každý uzol v systéme.

V rámci toho musíme byť schopní vypočítať dve rôzne skóre. Jedným je skóre, ktoré sa dostanete z jedného uzla do druhého. Druhá je heuristická, aby poskytla odhad nákladov z ktoréhokoľvek uzla do cieľového miesta. Tento odhad nemusí byť presný, ale vyššia presnosť prinesie lepšie výsledky. Jedinou požiadavkou je, aby obe skóre boli navzájom konzistentné - to znamená, že sú v rovnakých jednotkách.

Na samom začiatku sa naša otvorená množina skladá z nášho štartovacieho uzla a o žiadnych ďalších uzloch nemáme vôbec žiadne informácie.

Pri každej iterácii budeme:

  • Vyberte uzol z našej otvorenej množiny, ktorý má najnižšie odhadované celkové skóre
  • Odstráňte tento uzol z otvorenej množiny
  • Pridajte do otvorenej množiny všetky uzly, na ktoré sa z nej dostaneme

Keď to urobíme, tiež vypracujeme nové skóre z tohto uzla do každého nového, aby sme zistili, či ide o zlepšenie toho, čo sme doposiaľ dosiahli, a ak je, potom aktualizujeme to, čo o tomto uzle vieme.

Toto sa potom opakuje, kým uzol v našej otvorenej množine s najnižším odhadovaným celkovým skóre nie je našim cieľom. V tom okamihu sme dostali našu trasu.

4.1. Spracovaný príklad

Začnime napríklad od „Marylebone“ a pokúsme sa nájsť cestu na „Bond Street“.

Na začiatku sa naša otvorená sada skladá iba z „Marylebone“. To znamená, že toto je implicitne uzol, pre ktorý máme najlepšie „odhadované celkové skóre“.

Naše ďalšie zastávky môžu byť buď „Edgware Road“, s cenou 0,4403 km, alebo „Baker Street“, s cenou 0,4153 km. „Edgware Road“ je však nesprávnym smerom, takže naša heuristika odtiaľto do cieľa dáva skóre 1,4284 km, zatiaľ čo „Baker Street“ má heuristické skóre 1,0753 km.

To znamená, že po tejto iterácii sa naša otvorená sada skladá z dvoch položiek - „Edgware Road“ s odhadovaným celkovým skóre 1,8687 km a „Baker Street“ s odhadovaným celkovým skóre 1,4906 km.

Naša druhá iterácia potom začne od „Baker Street“, pretože má najnižšie odhadované celkové skóre. Odtiaľto môžu byť naše ďalšie zastávky buď „Marylebone“, „St. John's Wood “,„ Great Portland Street “, Regent's Park” alebo “Bond Street”.

Nebudeme pracovať cez všetky tieto, ale vezmime si „Marylebone“ ako zaujímavý príklad. Náklady na cestu tam sú opäť 0,4153 km, čo však znamená, že celkové náklady sú teraz 0,8306 km. Heuristika odtiaľto do cieľa navyše dáva skóre 1,323 km.

To znamená, že odhadované celkové skóre by bolo 2,1536 km, čo je horšie ako predchádzajúce skóre pre tento uzol. To dáva zmysel, pretože v tomto prípade sme museli urobiť ďalšiu prácu, aby sme sa nikam nedostali. To znamená, že to nebudeme považovať za životaschopnú cestu. Z tohto dôvodu sa podrobnosti pre položku „Marylebone“ neaktualizujú a nepridajú sa späť do otvorenej množiny.

5. Implementácia Java

Teraz, keď sme diskutovali o tom, ako to funguje, poďme to vlastne implementovať. Chystáme sa vytvoriť všeobecné riešenie a potom implementujeme kód potrebný na to, aby fungoval pre londýnske metro. Potom ho môžeme použiť pre ďalšie scenáre implementáciou iba týchto konkrétnych častí.

5.1. Predstavujúci graf

Najskôr musíme byť schopní znázorniť náš graf, ktorým chceme prechádzať. Skladá sa z dvoch tried - jednotlivých uzlov a potom z grafu ako celku.

Zastúpime svoje jednotlivé uzly pomocou rozhrania s názvom GraphNode:

verejné rozhranie GraphNode {String getId (); }

Každý z našich uzlov musí mať ID. Všetko ostatné je špecifické pre tento konkrétny graf a nie je potrebné na všeobecné riešenie. Tieto triedy sú jednoduché Java Beans bez špeciálnej logiky.

Náš celkový graf potom predstavuje trieda, ktorá sa jednoducho nazýva Graf:

verejná trieda Graph {private final Set node; súkromná záverečná Mapa pripojenia; public T getNode (String id) {return nodes.stream () .filter (node ​​-> node.getId (). equals (id)) .findFirst () .orElseThrow (() -> new IllegalArgumentException („No node found with ID ")); } public Set getConnections (T node) {return connections.get (node.getId ()). stream () .map (this :: getNode) .collect (Collectors.toSet ()); }}

Toto ukladá všetky uzly do nášho grafu a má vedomosti o tom, ktoré uzly sa ku ktorým pripájajú. Potom môžeme získať akýkoľvek uzol podľa ID alebo všetky uzly pripojené k danému uzlu.

V tomto okamihu sme schopní reprezentovať akúkoľvek formu grafu, ktorú si želáme, s ľubovoľným počtom hrán medzi ľubovoľným počtom uzlov.

5.2. Kroky na našej trase

Ďalšou vecou, ​​ktorú potrebujeme, je náš mechanizmus na hľadanie trás cez graf.

Prvá časť je nejakým spôsobom, ako vygenerovať skóre medzi ľubovoľnými dvoma uzlami. Budeme Strelec rozhranie pre skóre do nasledujúceho uzla aj pre odhad do cieľa:

verejné rozhranie Strelec {double computeCost (T od, T do); }

Na základe počiatočného a koncového uzla potom dostaneme skóre za cestovanie medzi nimi.

Potrebujeme tiež obal okolo našich uzlov, ktorý nesie nejaké ďalšie informácie. Namiesto toho, aby ste boli GraphNode, toto je RouteNode - pretože je to uzol na našej vypočítanej trase namiesto jedného v celom grafe:

trieda RouteNode implementuje Comparable {private final T current; súkromný T predchádzajúci; súkromné ​​dvojité routeScore; súkromné ​​dvojité odhadované skóre; RouteNode (T current) {this (current, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode (T súčasné, T predchádzajúce, dvojité routeScore, dvojité odhadnuté skóre) {this.current = current; this.previous = predchádzajúca; this.routeScore = routeScore; this.estimatedScore = scheduledScore; }}

Ako s GraphNode, jedná sa o jednoduché Java Beans používané na ukladanie aktuálneho stavu každého uzla pre výpočet súčasnej trasy. Dali sme tento jednoduchý konštruktor pre bežný prípad, keď sme pri prvej návšteve uzla a zatiaľ o ňom nemáme ďalšie informácie.

Aj také musia byť Porovnateľné aby sme ich mohli usporiadať podľa odhadovaného skóre ako súčasť algoritmu. To znamená pridanie a porovnať s() metóda na splnenie požiadaviek Porovnateľné rozhranie:

@Override public int compareTo (RouteNode other) {if (this.estimatedScore> other.estimatedScore) {return 1; } else if (this.estimatedScore <other.estimatedScore) {return -1; } else {návrat 0; }}

5.3. Nájdenie našej trasy

Teraz sme v pozícii, aby sme skutočne generovali naše trasy v celom našom grafe. Bude to trieda s názvom RouteFinder:

verejná trieda RouteFinder {súkromná konečná Grafový graf; súkromný konečný strelec nextNodeScorer; súkromný konečný strelec targetScorer; public List findRoute (T od, T do) {throw new IllegalStateException ("No route found"); }}

Máme graf, ktorý nachádzame, cez ktoré cesty prechádzame, a našich dvoch strelcov - jeden pre presné skóre pre nasledujúci uzol a jeden pre odhadované skóre pre náš cieľ. Máme tiež metódu, ktorá prevezme počiatočný a konečný uzol a vypočíta najlepšiu cestu medzi týmito dvoma bodmi.

Táto metóda má byť naším algoritmom A *. Celý zvyšok nášho kódu je súčasťou tejto metódy.

Začíname základným nastavením - našou „otvorenou sadou“ uzlov, ktorú môžeme považovať za ďalší krok, a mapou každého uzla, ktorý sme doteraz navštívili, a čo o ňom vieme:

Fronta openSet = nová PriorityQueue (); Mapa allNodes = nový HashMap (); RouteNode start = nový RouteNode (od, null, 0d, targetScorer.computeCost (od, do)); openSet.add (štart); allNodes.put (od, štart);

Naša otvorená množina má spočiatku jediný uzol - náš východiskový bod. Neexistuje pre to žiadny predchádzajúci uzol, je tam skóre 0 a máme odhad, ako ďaleko je to od nášho cieľa.

Použitie a PriorityQueue otvorená množina znamená, že z nej automaticky dostaneme najlepší vstup na základe našich porovnať s() metóda z predchádzajúcej.

Teraz iterujeme, až kým nám nedôjde, aby sme sa pozreli na uzly, alebo kým naším cieľom nebude najlepší dostupný uzol:

while (! openSet.isEmpty ()) {RouteNode next = openSet.poll (); if (next.getCurrent (). equals (to)) {List route = new ArrayList (); RouteNode current = next; do {route.add (0, current.getCurrent ()); current = allNodes.get (current.getPrevious ()); } while (aktualne! = null); spiatočná trasa; } // ...

Keď nájdeme náš cieľ, môžeme vytvoriť našu trasu opakovaným pozeraním na predchádzajúci uzol, kým sa nedostaneme k nášmu východiskovému bodu.

Ďalej, ak sme sa nedostali do cieľa, môžeme zistiť, čo robiť ďalej:

 graph.getConnections (next.getCurrent ()). forEach (connection -> {RouteNode nextNode = allNodes.getOrDefault (connection, new RouteNode (connection)); allNodes.put (connection, nextNode); double newScore = next.getRouteScore () + nextNodeScorer.computeCost (next.getCurrent (), pripojenie); if (newScore <nextNode.getRouteScore ()) {nextNode.setPrevious (next.getCurrent ()); nextNode.setRouteScore (newScore); nextNode.setEstimatedScore (newScore + newScore + .computeCost (pripojenie, do)); openSet.add (nextNode);}}); hodiť novú IllegalStateException ("Nenašla sa žiadna trasa"); }

Tu iterujeme cez pripojené uzly z nášho grafu. Za každú z nich dostaneme RouteNode ktoré na to máme - v prípade potreby vytvorenie nového.

Potom vypočítame nové skóre pre tento uzol a zistíme, či je lacnejšie ako to, čo sme mali doteraz. Ak je, aktualizujeme ho tak, aby zodpovedal tejto novej trase, a pridáme ho do otvorenej množiny na zváženie nabudúce.

Toto je celý algoritmus. Stále to opakujeme, až kým nedosiahneme svoj cieľ alebo sa nám nepodarí dostať sa tam.

5.4. Konkrétne podrobnosti o londýnskom metre

To, čo zatiaľ máme, je všeobecný A * pathfinder, ale chýbajú mu podrobnosti, ktoré potrebujeme pre náš presný prípad použitia. To znamená, že potrebujeme konkrétnu implementáciu oboch GraphNode a Strelec.

Naše uzly sú stanice v podzemí a my ich vymodelujeme pomocou Stanica trieda:

stanica verejnej triedy implementuje GraphNode {private final String id; súkromné ​​konečné meno reťazca; konečná dvojitá zemepisná šírka; konečná dvojitá zemepisná dĺžka; }

Názov je užitočný na zobrazenie výstupu a zemepisná šírka a dĺžka sú určené pre naše skórovanie.

V tomto scenári potrebujeme iba jednu implementáciu Strelec. Použijeme na to Haversinov vzorec na výpočet priamkovej vzdialenosti medzi dvoma pármi zemepisnej šírky a dĺžky:

verejná trieda HaversineScorer implementuje Scorer {@Override public double computeCost (stanica od, stanica do) {double R = 6372.8; // Polomer Zeme, v kilometroch double dLat = Math.toRadians (to.getLatitude () - from.getLatitude ()); double dLon = Math.toRadians (to.getLongitude () - od.getLongitude ()); double lat1 = Math.toRadians (from.getLatitude ()); double lat2 = Math.toRadians (to.getLatitude ()); double a = Math.pow (Math.sin (dLat / 2), 2) + Math.pow (Math.sin (dLon / 2), 2) * Math.cos (lat1) * Math.cos (lat2); dvojité c = 2 * Math.asin (Math.sqrt (a)); návrat R * c; }}

Teraz máme takmer všetko potrebné na výpočet trás medzi ľubovoľnými dvoma pármi staníc. Chýba už len graf súvislostí medzi nimi. To je k dispozícii na GitHub.

Použime to na mapovanie trasy. Vygenerujeme jeden od Earl's Court po Angel. Má niekoľko rôznych možností cestovania, minimálne na dvoch hadičkách:

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

To generuje trasu Earl's Court -> South Kensington -> Green Park -> Euston -> Angel.

Zrejmá cesta, ktorou by sa mnoho ľudí vydalo, by pravdepodobne bola Earl's Count -> Monument -> Angel, pretože je tu menej zmien. Namiesto toho toto sa uberalo podstatne priamejšou cestou, aj keď to znamenalo viac zmien.

6. Záver

V tomto článku sme videli, čo je to algoritmus A *, ako funguje a ako ho implementovať do našich vlastných projektov. Prečo to nevyužiť a rozšíriť si to pre svoje vlastné použitie?

Možno sa pokúsite rozšíriť ho tak, aby zohľadňoval prestupy medzi rúrkovými vedeniami, a uvidíte, ako to ovplyvní vybrané trasy?

Kompletný kód článku je opäť k dispozícii na stránkach GitHub.


$config[zx-auto] not found$config[zx-overlay] not found