streamalism.org

1. Introduksjon

Pathfinding-algoritmer er teknikker for å navigere i kart, slik at vi kan finne en rute mellom to forskjellige punkter. Ulike algoritmer har forskjellige fordeler og ulemper, ofte når det gjelder effektiviteten til algoritmen og effektiviteten til ruten den genererer.

2. Hva er en pathfinding algoritme?

En stifinnende algoritme er en teknikk for å konvertere en graf - bestående av noder og kanter - til en rute gjennom grafen. Denne grafen kan være hva som helst som trenger kryssing. For denne artikkelen skal vi prøve å krysse en del av Londons undergrunnssystem:

(“London Underground Overground DLR Crossrail map” av sameboat er lisensiert under CC BY-SA 4.0)

Dette har mange interessante komponenter:

• Vi har kanskje ikke en direkte rute mellom start- og sluttpunktet. For eksempel kan vi gå direkte fra "Earls Court" til "Monument", men ikke til "Angel".
• Hvert eneste trinn har en bestemt kostnad. I vårt tilfelle er dette avstanden mellom stasjonene.
• Hvert stopp er bare koblet til en liten delmengde av de andre stoppene. For eksempel er "Regent's Park" direkte koblet til bare "Baker Street" og "Oxford Circus".

Alle banesøkingsalgoritmer tar som inngang en samling av alle noder - stasjoner i vårt tilfelle - og forbindelser mellom dem, og også ønsket start- og sluttpunkt. Utgangen er vanligvis settet med noder som får oss fra start til slutt, i den rekkefølgen vi trenger å gå.

3. Hva er A *?

A * er en spesifikk pathfinding-algoritme, første gang utgitt i 1968 av Peter Hart, Nils Nilsson og Bertram Raphael. Det anses generelt å være den beste algoritmen å bruke når det ikke er mulighet til å forhåndsberegne rutene og det ikke er begrensninger for minnebruk..

Både minne og ytelseskompleksitet kan være O (b ^ d) i verste fall, så selv om det alltid vil fungere som den mest effektive ruten, er det ikke alltid den mest effektive måten å gjøre det på.

A * er faktisk en variant av Dijkstras algoritme, hvor det er tilleggsinformasjon gitt for å velge neste node som skal brukes. Denne tilleggsinformasjonen trenger ikke å være perfekt - hvis vi allerede har perfekt informasjon, er stifinnings meningsløs. Men jo bedre det er, desto bedre blir sluttresultatet.

4. Hvordan fungerer A *?

A * -algoritmen fungerer ved å velge iterativt hva som er den beste ruten så langt, og prøve å se hva som er det beste neste trinnet.

Når vi jobber med denne algoritmen, har vi flere data som vi trenger å holde rede på. Det "åpne settet" er alle nodene vi vurderer for øyeblikket. Dette er ikke hver node i systemet, men i stedet er det hver node som vi kan gjøre neste trinn fra.

Vi vil også holde oversikt over gjeldende beste poengsum, estimert totalpoengsum og nåværende beste forrige node for hver node i systemet.

Som en del av dette trenger vi å kunne beregne to forskjellige poeng. Den ene er poengsummen for å komme fra en node til den neste. Den andre er en heuristikk for å gi et estimat av kostnaden fra hvilken som helst node til destinasjonen. Dette estimatet trenger ikke å være nøyaktig, men større nøyaktighet vil gi bedre resultater. Det eneste kravet er at begge poengene stemmer overens med hverandre - det vil si at de er i de samme enhetene.

Helt på begynnelsen består vårt åpne sett av startnoden vår, og vi har ingen informasjon om andre noder i det hele tatt.

Ved hver iterasjon vil vi:

• Velg noden fra vårt åpne sett som har den laveste estimerte totale poengsummen
• Fjern denne noden fra det åpne settet
• Legg til det åpne settet alle nodene vi kan nå fra det

Når vi gjør dette, regner vi også ut den nye poengsummen fra denne noden til hver nye for å se om det er en forbedring av det vi har så langt, og hvis det er, oppdaterer vi det vi vet om den noden.

Dette gjentas til noden i vårt åpne sett som har den laveste estimerte totale poengsummen, er målet vårt, på hvilket tidspunkt vi har ruten vår.

4.1. Arbeidet eksempel

La oss for eksempel starte fra "Marylebone" og prøve å finne veien til "Bond Street".

Helt i begynnelsen består vårt åpne sett bare av "Marylebone". Det betyr at dette implisitt er noden vi har den beste "estimerte totale poengsummen" for.

Våre neste stopp kan være enten "Edgware Road", med en kostnad på 0,4403 km, eller "Baker Street", med en kostnad på 0,4153 km. Imidlertid er "Edgware Road" i feil retning, så vår heuristikk herfra til destinasjonen gir en poengsum på 1.4284 km, mens "Baker Street" har en heuristisk poengsum på 1.0753 km.

Dette betyr at vårt åpne sett etter denne iterasjonen består av to oppføringer - “Edgware Road”, med en estimert totalpoengsum på 1,8687 km, og “Baker Street”, med en estimert totalpoengsum på 1,4906 km.

Den andre iterasjonen vår starter da fra "Baker Street", siden dette har den laveste estimerte totalpoengsummen. Herfra kan våre neste stopp være enten "Marylebone", "St. John's Wood "," Great Portland Street ", Regent's Park" eller "Bond Street".

Vi vil ikke jobbe gjennom alle disse, men la oss ta "Marylebone" som et interessant eksempel. Kostnaden for å komme dit er igjen 0,4153 km, men dette betyr at den totale kostnaden nå er 0,8306 km. I tillegg gir heuristikken herfra til destinasjonen en poengsum på 1.323 km.

Dette betyr at den estimerte totale poengsummen vil være 2,1536 km, altså verre enn forrige poengsum for denne noden. Dette er fornuftig fordi vi har måttet gjøre ekstra arbeid for å komme oss ingen vei i dette tilfellet. Dette betyr at vi ikke vil betrakte dette som en levedyktig rute. Som sådan oppdateres ikke detaljene for "Marylebone", og den legges ikke tilbake på det åpne settet.

5. Java-implementering

Nå som vi har diskutert hvordan dette fungerer, la oss faktisk implementere det. Vi skal bygge en generisk løsning, og så implementerer vi koden som er nødvendig for at den skal fungere for London Underground. Vi kan deretter bruke den til andre scenarier ved å implementere bare de spesifikke delene.

5.1. Representerer grafen

For det første må vi være i stand til å representere grafen vår som vi ønsker å krysse. Dette består av to klasser - de enkelte nodene og deretter grafen som en helhet.

Vi representerer våre individuelle noder med et grensesnitt som heter GraphNode:

offentlig grensesnitt GraphNode {String getId (); }

Hver av nodene våre må ha en ID. Alt annet er spesifikt for denne grafen og er ikke nødvendig for den generelle løsningen. Disse klassene er enkle Java Beans uten spesiell logikk.

Vår samlede graf er deretter representert av en klasse som bare heter Kurve:

public class Graph {private final Sett noder; privat finale Kart tilkoblinger; public T getNode (String id) {return nodes.stream () .filter (node ​​-> node.getId (). equals (id)) .findFirst () .orElseThrow (() -> new IllegalArgumentException ("Ingen node funnet med ID ")); } offentlig Sett getConnections (T-node) {retur forbindelser.get (node.getId ()). stream () .map (dette :: getNode) .collect (Collectors.toSet ()); }}

Dette lagrer alle nodene i grafen vår og har kunnskap om hvilke noder som kobles til hvilke. Vi kan da få en hvilken som helst node etter ID, eller alle nodene som er koblet til en gitt node.

På dette punktet er vi i stand til å representere enhver form for graf vi ønsker, med et hvilket som helst antall kanter mellom et hvilket som helst antall noder.

5.2. Trinn på ruten vår

Det neste vi trenger er vår mekanisme for å finne ruter gjennom grafen.

Den første delen av dette er en måte å generere en poengsum mellom to noder. Vi vil Scorer grensesnitt for både poengsummen til neste node og estimatet til destinasjonen:

offentlig grensesnitt Scorer {dobbel computeCost (T fra, T til); }

Gitt en start- og en sluttnode, får vi en poengsum for å reise mellom dem.

Vi trenger også en innpakning rundt nodene våre som inneholder litt ekstra informasjon. I stedet for å være en GraphNode, dette er en RouteNode - fordi det er en node i den beregnede ruten vår i stedet for en i hele grafen:

klasse RouteNode implementerer Sammenlignbar {privat sluttstrøm; privat T forrige; privat dobbel rute; privat dobbel estimert score; RouteNode (T gjeldende) {dette (gjeldende, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode (T gjeldende, T forrige, dobbel rutescore, dobbelt estimert score) {this.current = gjeldende; this.previous = forrige; this.routeScore = rutescore; this.estimatedScore = estimert score; }}

Som med GraphNode, dette er enkle Java Beans som brukes til å lagre den nåværende tilstanden til hver node for gjeldende ruteberegning. Vi har gitt dette en enkel konstruktør for det vanlige tilfellet når vi først besøker en node og ikke har ytterligere informasjon om det ennå.

Disse må også være Sammenlignelig skjønt, slik at vi kan bestille dem etter estimert poengsum som en del av algoritmen. Dette betyr tillegg av en sammenligne med() metoden for å oppfylle kravene i Sammenlignelig grensesnitt:

@ Override public int CompareTo (RouteNode annet) {if (this.estimatedScore> other.estimatedScore) {retur 1; } annet hvis (dette.estimatedScore <other.estimatedScore) {retur -1; } annet {retur 0; }}

5.3. Finne vår rute

Nå er vi i posisjon til å faktisk generere våre ruter på tvers av grafen vår. Dette blir en klasse som heter RouteFinder:

offentlig klasse RouteFinder {privat endelig Grafgraf; privat final Scorer nextNodeScorer; privat final Scorer targetScorer; public List findRoute (T from, T to) {throw new IllegalStateException ("Ingen rute funnet"); }}

Vi har grafen som vi finner rutene over, og våre to målscorere - en for den nøyaktige poengsummen for neste node, og en for den estimerte poengsummen til målet vårt. Vi har også en metode som tar en start- og sluttnode og beregner den beste ruten mellom de to.

Denne metoden skal være vår A * algoritme. Resten av koden vår går inn i denne metoden.

Vi starter med noen grunnleggende oppsett - vårt "åpne sett" av noder som vi kan vurdere som neste trinn, og et kart over hver node som vi har besøkt så langt, og hva vi vet om det:

Kø openSet = ny PriorityQueue (); Kart allNodes = ny HashMap (); RouteNode start = ny RouteNode (fra, null, 0d, targetScorer.computeCost (fra, til)); openSet.add (start); allNodes.put (fra, start);

Vårt åpne sett har i utgangspunktet en enkelt node - vårt startpunkt. Det er ingen tidligere node for dette, det er poengsummen 0 for å komme dit, og vi har et estimat på hvor langt det er fra målet vårt.

Bruken av en PriorityQueue for det åpne settet betyr at vi automatisk får den beste inngangen av det, basert på vårt sammenligne med() metode fra tidligere.

Nå gjentas vi til enten vi går tom for noder å se på, eller den beste tilgjengelige noden er målet vårt:

mens (! openSet.isEmpty ()) {RouteNode neste = openSet.poll (); if (next.getCurrent (). tilsvarer (to)) {List route = new ArrayList (); RouteNode gjeldende = neste; gjør {route.add (0, current.getCurrent ()); gjeldende = allNodes.get (current.getPrevious ()); } mens (nåværende! = null); returrute; } // ...

Når vi har funnet destinasjonen vår, kan vi bygge ruten vår ved å gjentatte ganger se på den forrige noden til vi når utgangspunktet.

Neste, hvis vi ikke har nådd målet, kan vi finne ut hva vi skal gjøre videre:

 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 (), tilkobling); hvis (newScore <nextNode.getRouteScore ()) {nextNode.setPrevious (next.getCurrent ()); nextNode.setRouteScore (newScore); nextNode.setEstimatedScore (newScore + targetScorer .computeCost (forbindelse, til)); openSet.add (nesteNode);}}); kaste nye IllegalStateException ("Ingen rute funnet"); }

Her gjentas vi over de tilkoblede nodene fra grafen vår. For hver av disse får vi RouteNode som vi har for det - å lage en ny om nødvendig.

Deretter beregner vi den nye poengsummen for denne noden og ser om den er billigere enn det vi hadde hittil. Hvis det er, oppdaterer vi det for å matche denne nye ruten og legger det til det åpne settet for vurdering neste gang.

Dette er hele algoritmen. Vi fortsetter å gjenta dette til vi enten når målet vårt eller ikke kommer dit.

5.4. Spesifikke detaljer for London Underground

Det vi har hittil er en generisk A * pathfinder, men det mangler detaljene vi trenger for vår eksakte brukssak. Dette betyr at vi trenger en konkret implementering av begge deler GraphNode og Scorer.

Nodene våre er stasjoner på undergrunnen, og vi modellerer dem med Stasjon klasse:

offentlig klasse Station implementerer GraphNode {private final String id; privat slutt Strengnavn; privat endelig dobbelt bredde; privat endelig dobbelt lengdegrad; }

Navnet er nyttig for å se utdataene, og breddegrad og lengdegrad er for vår poengsum.

I dette scenariet trenger vi bare en enkelt implementering av Scorer. Vi skal bruke Haversine-formelen for dette, for å beregne den rette linjeavstanden mellom to par breddegrad / lengdegrad:

offentlig klasse HaversineScorer implementerer Scorer {@Override public double computeCost (Station from, Station to) {double R = 6372.8; // Jordens radius, i kilometer dobbelt dLat = Math.toRadians (to.getLatitude () - from.getLatitude ()); dobbelt dLon = Math.toRadians (to.getLongitude () - fra.getLongitude ()); dobbel lat1 = Math.toRadians (fra.getLatitude ()); dobbel lat2 = Math.toRadians (to.getLatitude ()); doble a = Math.pow (Math.sin (dLat / 2), 2) + Math.pow (Math.sin (dLon / 2), 2) * Math.cos (lat1) * Math.cos (lat2); dobbel c = 2 * Math.asin (Math.sqrt (a)); retur R * c; }}

Vi har nå nesten alt som er nødvendig for å beregne stier mellom to par stasjoner. Det eneste som mangler er grafen over forbindelsene mellom dem. Dette er tilgjengelig i GitHub.

La oss bruke den til å kartlegge en rute. Vi genererer en fra Earls Court og opp til Angel. Dette har en rekke forskjellige muligheter for reise, på minst to rørledninger:

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

Dette genererer en rute av Earl's Court -> South Kensington -> Green Park -> Euston -> Angel.

Den åpenbare ruten som mange mennesker ville ha tatt, ville sannsynligvis være Earls Count -> Monument -> Angel, fordi det har færre endringer. I stedet, dette har tatt en betydelig mer direkte rute selv om det betydde flere endringer.

6. Konklusjon

I denne artikkelen har vi sett hva A * -algoritmen er, hvordan den fungerer og hvordan vi implementerer den i våre egne prosjekter. Hvorfor ikke ta dette og utvide det til eget bruk?

Kanskje prøve å utvide den for å ta hensyn til utvekslinger mellom rørlinjer, og se hvordan det påvirker de valgte rutene?

Og igjen, den komplette koden for artikkelen er tilgjengelig på GitHub.