streamalism.org

1. Introduktion

Pathfinding-algoritmer er teknikker til at navigere i kort, så vi kan finde en rute mellem to forskellige punkter. Forskellige algoritmer har forskellige fordele og ulemper, ofte med hensyn til effektiviteten af ​​algoritmen og effektiviteten af ​​den rute, den genererer.

2. Hvad er en stifindende algoritme?

En stifindende algoritme er en teknik til at konvertere en graf - bestående af noder og kanter - til en rute gennem grafen. Denne graf kan overhovedet være alt, hvad der skal traverseres. Til denne artikel vil vi forsøge at krydse en del af Londons undergrundssystem:

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

Dette har mange interessante komponenter til det:

• Vi har måske ikke en direkte rute mellem vores start- og slutpunkter. For eksempel kan vi gå direkte fra "Earl's Court" til "Monument", men ikke til "Angel".
• Hvert enkelt trin har en bestemt pris. I vores tilfælde er dette afstanden mellem stationer.
• Hvert stop er kun forbundet med en lille delmængde af de andre stop. For eksempel er "Regent's Park" direkte forbundet med kun "Baker Street" og "Oxford Circus".

Alle pathfinding-algoritmer tager som input en samling af alle noder - stationer i vores tilfælde - og forbindelser mellem dem og også de ønskede start- og slutpunkter. Outputtet er typisk det sæt noder, der får os fra start til slut, i den rækkefølge, vi skal bruge.

3. Hvad er A *?

A * er en bestemt pathfinding-algoritme, udgivet første gang i 1968 af Peter Hart, Nils Nilsson og Bertram Raphael. Det anses generelt for at være den bedste algoritme at bruge, når der ikke er nogen mulighed for at forhåndsberegne ruterne, og der ikke er begrænsninger for hukommelsesforbruget.

Både hukommelse og performance-kompleksitet kan være O (b ^ d) i værste tilfælde, så selvom det altid fungerer den mest effektive rute, er det ikke altid den mest effektive måde at gøre det på.

A * er faktisk en variation på Dijkstras algoritme, hvor der er yderligere oplysninger til rådighed for at hjælpe med at vælge den næste node, der skal bruges. Denne yderligere information behøver ikke at være perfekt - hvis vi allerede har perfekte oplysninger, er stedsøgning meningsløs. Men jo bedre det er, desto bedre bliver slutresultatet.

4. Hvordan fungerer A *?

A * -algoritmen fungerer ved iterativt at vælge, hvad der er den bedste rute hidtil, og forsøge at se, hvad det bedste næste trin er.

Når vi arbejder med denne algoritme, har vi flere stykker data, som vi har brug for at holde styr på. Det "åbne sæt" er alle de noder, som vi i øjeblikket overvejer. Dette er ikke hver knude i systemet, men i stedet er det hver knude, som vi måske tager det næste trin fra.

Vi holder også styr på den aktuelle bedste score, den anslåede samlede score og den nuværende bedste tidligere node for hver node i systemet.

Som en del af dette skal vi være i stand til at beregne to forskellige scores. Den ene er scoren for at komme fra en node til den næste. Den anden er en heuristik for at give et skøn over omkostningerne fra enhver knude til destinationen. Dette skøn behøver ikke at være nøjagtigt, men større nøjagtighed vil give bedre resultater. Det eneste krav er, at begge scores er i overensstemmelse med hinanden - det vil sige, at de er i de samme enheder.

I begyndelsen består vores åbne sæt af vores startknude, og vi har slet ingen oplysninger om andre noder.

Ved hver iteration vil vi:

• Vælg noden fra vores åbne sæt, der har den laveste estimerede samlede score
• Fjern denne node fra det åbne sæt
• Føj til det åbne sæt alle de noder, som vi kan nå fra det

Når vi gør dette, udarbejder vi også den nye score fra denne node til hver nye for at se, om det er en forbedring af, hvad vi hidtil har fået, og hvis det er, opdaterer vi, hvad vi ved om den node.

Dette gentages, indtil noden i vores åbne sæt, der har den laveste estimerede samlede score, er vores destination, på hvilket tidspunkt vi har vores rute.

4.1. Arbejdet eksempel

Lad os for eksempel starte fra "Marylebone" og forsøge at finde vej til "Bond Street".

Allerede i starten består vores åbne sæt kun af "Marylebone". Det betyder, at dette implicit er den knude, som vi har den bedste "estimerede samlede score" for.

Vores næste stop kan enten være "Edgware Road" med en pris på 0,4403 km eller "Baker Street" med en pris på 0,4153 km. Imidlertid er "Edgware Road" i den forkerte retning, så vores heuristik herfra til destinationen giver en score på 1.4284 km, mens "Baker Street" har en heuristisk score på 1.0753 km.

Det betyder, at vores åbne sæt efter denne iteration består af to poster - “Edgware Road” med en estimeret total score på 1.8687 km og “Baker Street” med en estimeret total score på 1.4906 km.

Vores anden iteration starter derefter fra "Baker Street", da dette har den laveste estimerede samlede score. Herfra kan vores næste stop enten være "Marylebone", "St. John's Wood "," Great Portland Street ", Regent's Park" eller "Bond Street".

Vi arbejder ikke igennem alle disse, men lad os tage “Marylebone” som et interessant eksempel. Omkostningerne ved at komme dertil er igen 0,4153 km, men det betyder, at de samlede omkostninger nu er 0,8306 km. Derudover giver heuristikken herfra til destinationen en score på 1.323 km.

Dette betyder, at den anslåede samlede score vil være 2,1536 km, hvilket er værre end den tidligere score for denne node. Dette giver mening, fordi vi har været nødt til at gøre ekstra arbejde for at komme ingen steder i dette tilfælde. Dette betyder, at vi ikke vil betragte dette som en levedygtig rute. Som sådan opdateres detaljerne for "Marylebone" ikke, og det føjes ikke tilbage til det åbne sæt.

5. Java-implementering

Nu hvor vi har diskuteret, hvordan dette fungerer, lad os faktisk implementere det. Vi bygger en generisk løsning, og så implementerer vi den nødvendige kode for at den kan fungere for London Underground. Vi kan derefter bruge det til andre scenarier ved kun at implementere de specifikke dele.

5.1. Repræsenterer grafen

For det første skal vi være i stand til at repræsentere vores graf, som vi ønsker at krydse. Dette består af to klasser - de enkelte noder og derefter grafen som helhed.

Vi repræsenterer vores individuelle noder med en kaldet grænseflade GraphNode:

offentlig grænseflade GraphNode {String getId (); }

Hver af vores knudepunkter skal have et ID. Alt andet er specifikt for denne graf og er ikke nødvendigt for den generelle løsning. Disse klasser er enkle Java Beans uden særlig logik.

Vores overordnede graf er derefter repræsenteret af en klasse, der simpelthen kaldes Kurve:

public class Graph {private final Sæt noder; privat endelig kort forbindelser; public T getNode (String id) {return nodes.stream () .filter (node ​​-> node.getId (). equals (id)) .findFirst () .orElseThrow (() -> new IllegalArgumentException ("Ingen node fundet med ID ")); } offentlig Indstil getConnections (T-node) {return forbindelser.get (node.getId ()). stream () .map (dette :: getNode) .collect (Collectors.toSet ()); }}

Dette gemmer alle knudepunkterne i vores graf og har viden om, hvilke knudepunkter der forbinder til hvilke. Vi kan derefter få en hvilken som helst node efter ID eller alle de noder, der er forbundet til en given node.

På dette tidspunkt er vi i stand til at repræsentere enhver form for graf, vi ønsker, med et vilkårligt antal kanter mellem et hvilket som helst antal noder.

5.2. Trin på vores rute

Den næste ting, vi har brug for, er vores mekanisme til at finde ruter gennem grafen.

Den første del af dette er en eller anden måde at generere en score mellem to noder. Vi gør det Scorer interface til både score til næste node og estimat til destination:

offentlig grænseflade Scorer {dobbelt computeCost (T fra, T til); }

Når vi får en start- og en slutknudepunkt, får vi en score for at rejse mellem dem.

Vi har også brug for en indpakning omkring vores noder, der indeholder nogle ekstra oplysninger. I stedet for at være en GraphNode, dette er en RouteNode - fordi det er en knude i vores beregnede rute i stedet for en i hele grafen:

klasse RouteNode implementerer Sammenlignelig {privat slutstrøm T; privat T forrige; privat dobbelt ruteScore; privat dobbelt estimeret score; RouteNode (T nuværende) {denne (nuværende, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode (T nuværende, T forrige, dobbelt rutescore, dobbelt estimeret score) {this.current = aktuel; this.previous = forrige; this.routeScore = ruteScore; this.estimatedScore = estimeret score; }}

Som med GraphNode, dette er enkle Java Beans, der bruges til at gemme den aktuelle tilstand for hver node til den aktuelle ruteberegning. Vi har givet dette en simpel konstruktør til den almindelige sag, når vi først besøger en knude og ikke har yderligere oplysninger om det endnu.

Disse skal også være Sammenlignelig dog, så vi kan bestille dem efter den estimerede score som en del af algoritmen. Dette betyder tilføjelsen af ​​en sammenligne med() metode til at opfylde kravene i Sammenlignelig grænseflade:

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

5.3. Find vores rute

Nu er vi i stand til faktisk at generere vores ruter på tværs af vores graf. Dette vil være en klasse kaldet RouteFinder:

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

Vi har grafen, som vi finder ruterne på tværs af, og vores to målscorer - en for den nøjagtige score for den næste node og en for den estimerede score til vores destination. Vi har også en metode, der tager en start- og slutknudepunkt og beregner den bedste rute mellem de to.

Denne metode skal være vores A * algoritme. Resten af ​​vores kode går ind i denne metode.

Vi starter med nogle grundlæggende opsætninger - vores "åbne sæt" af noder, som vi kan overveje som det næste trin, og et kort over hver node, som vi hidtil har besøgt, og hvad vi ved om det:

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

Vores åbne sæt har oprindeligt en enkelt knude - vores startpunkt. Der er ingen tidligere node for dette, der er en score på 0 for at komme derhen, og vi har et skøn over, hvor langt det er fra vores destination.

Brugen af ​​en PriorityQueue for det åbne sæt betyder, at vi automatisk får den bedste adgang til det, baseret på vores sammenligne med() metode fra tidligere.

Nu gentager vi, indtil vi enten løber tør for noder at se på, eller den bedste tilgængelige node er vores destination:

mens (! openSet.isEmpty ()) {RouteNode næste = openSet.poll (); if (next.getCurrent (). er lig med (to)) {List route = new ArrayList (); RouteNode nuværende = næste; gør {route.add (0, current.getCurrent ()); nuværende = allNodes.get (current.getPrevious ()); } mens (nuværende! = null); returrute } // ...

Når vi har fundet vores destination, kan vi bygge vores rute ved gentagne gange at se på den forrige knude, indtil vi når vores startpunkt.

Hvis vi derefter ikke har nået vores destination, kan vi finde ud af, hvad vi skal gøre næste:

 graph.getConnections (next.getCurrent ()). forEach (forbindelse -> {RouteNode nextNode = allNodes.getOrDefault (forbindelse, ny RouteNode (forbindelse)); allNodes.put (forbindelse, nextNode); dobbelt newScore = next.getRouteScore () + nextNodeScorer.computeCost (next.getCurrent (), forbindelse); hvis (newScore <nextNode.getRouteScore ()) {nextNode.setPrevious (next.getCurrent ()); nextNode.setRouteScore (newScore); nextNode.setEstimatedScore (newScore + targetScorer .computeCost (forbindelse, til)); openSet.add (nextNode);}}); smid ny IllegalStateException ("Ingen rute fundet"); }

Her gentager vi de tilsluttede noder fra vores graf. For hver af disse får vi RouteNode som vi har til det - at skabe en ny, hvis det er nødvendigt.

Vi beregner derefter den nye score for denne node og ser, om den er billigere end det, vi hidtil havde. Hvis det er, opdaterer vi det, så det matcher denne nye rute og føjer det til det åbne sæt til overvejelse næste gang.

Dette er hele algoritmen. Vi gentager dette, indtil vi enten når vores mål eller ikke når frem.

5.4. Specifikke detaljer for London Underground

Hvad vi hidtil har er en generisk A * pathfinder, men det mangler de detaljer, vi har brug for til vores nøjagtige brugssag. Det betyder, at vi har brug for en konkret implementering af begge dele GraphNode og Scorer.

Vores noder er stationer i undergrunden, og vi modellerer dem med Station klasse:

offentlig klasse Station implementerer GraphNode {privat endelig streng-id; privat endelig Navn på streng; privat endelig dobbelt bredde; privat endelig dobbelt længdegrad; }

Navnet er nyttigt til at se output, og bredde og længdegrad er for vores scoring.

I dette scenarie har vi kun brug for en enkelt implementering af Scorer. Vi skal bruge Haversine-formlen til dette til at beregne den lige linje afstand mellem to par bredde / længdegrad:

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 (til.getLatitude () - fra.getLatitude ()); dobbelt dLon = Math.toRadians (til.getLongitude () - fra.getLongitude ()); dobbelt lat1 = Math.toRadians (fra.getLatitude ()); dobbelt lat2 = Math.toRadians (to.getLatitude ()); dobbelt a = Math.pow (Math.sin (dLat / 2), 2) + Math.pow (Math.sin (dLon / 2), 2) * Math.cos (lat1) * Math.cos (lat2); dobbelt c = 2 * Math.asin (Math.sqrt (a)); returnere R * c; }}

Vi har nu næsten alt nødvendigt for at beregne stier mellem to par stationer. Det eneste der mangler er grafen over forbindelser mellem dem. Dette er tilgængeligt i GitHub.

Lad os bruge det til at kortlægge en rute. Vi genererer en fra Earl's Court op til Angel. Dette har en række forskellige muligheder for rejser på mindst to rørledninger:

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

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

Den åbenlyse rute, som mange mennesker ville have taget, ville sandsynligvis være Earls Count -> Monument -> Angel, fordi der er færre ændringer. I stedet, dette har taget en væsentlig mere direkte rute, selvom det betød flere ændringer.

6. Konklusion

I denne artikel har vi set, hvad A * -algoritmen er, hvordan den fungerer, og hvordan vi implementerer den i vores egne projekter. Hvorfor ikke tage dette og udvide det til eget brug?

Måske prøve at udvide det for at tage udvekslinger mellem rørledninger i betragtning og se, hvordan det påvirker de valgte ruter?

Og igen er den komplette kode for artiklen tilgængelig på GitHub.