streamalism.org

1. Uvod

Algoritmi pronalaženja puta su tehnike za navigaciju kartama, omogućavajući nam da pronađemo rutu između dvije različite točke. Različiti algoritmi imaju različite prednosti i nedostatke, često u smislu učinkovitosti algoritma i učinkovitosti rute koju generira.

2. Što je algoritam za pronalaženje puta?

Algoritam pronalaženja puta je tehnika za pretvaranje grafa - koji se sastoji od čvorova i bridova - u rutu kroz graf. Ovaj graf može biti sve što treba prijeći. Za ovaj ćemo članak pokušati preći dio londonskog podzemnog sustava:

(„Londonska podzemna nadzemna DLR Crossrail karta“ istog čamca licencirana je pod CC BY-SA 4.0)

Ovo ima puno zanimljivih komponenti:

• Možemo ili ne moramo imati izravan put između početne i završne točke. Na primjer, možemo prijeći izravno s "Earl's Court" na "Monument", ali ne i na "Angel".
• Svaki pojedini korak ima određeni trošak. U našem slučaju to je udaljenost između stanica.
• Svaka stanica je povezana samo s malim podskupom ostalih stanica. Na primjer, "Regent's Park" izravno je povezan samo s "Baker Street" i "Oxford Circus".

Svi algoritmi za traženje puta uzimaju kao ulaz zbirku svih čvorova - stanica u našem slučaju - i veza između njih, kao i željene početne i završne točke. Izlaz je obično skup čvorova koji će nas dovesti od početka do kraja, redoslijedom kojim trebamo ići.

3. Što je A *?

A * je jedan specifičan algoritam za pronalaženje puta, koju su 1968. prvi objavili Peter Hart, Nils Nilsson i Bertram Raphael. Općenito se smatra najboljim algoritmom za upotrebu kada nema mogućnosti za predračun ruta i kada nema ograničenja u korištenju memorije.

I memorija i složenost performansi mogu biti O (b ^ d) u najgorem slučaju, pa iako će uvijek izraditi najučinkovitiji put, to nije uvijek najučinkovitiji način.

A * je zapravo varijacija Dijkstrinog algoritma, gdje se pružaju dodatne informacije koje pomažu u odabiru sljedećeg čvora koji će se koristiti. Ove dodatne informacije ne moraju biti savršene - ako već imamo savršene informacije, onda je traženje puta besmisleno. Ali što je bolji, to će i krajnji rezultat biti bolji.

4. Kako djeluje A *?

Algoritam A * djeluje tako što iterativno odabire koja je najbolja ruta do sada i pokušava vidjeti koji je najbolji sljedeći korak.

Kada radimo s ovim algoritmom, imamo nekoliko podataka koje moramo pratiti. "Otvoreni skup" su svi čvorovi koje trenutno razmatramo. Ovo nije svaki čvor u sustavu, već je svaki čvor iz kojeg bismo mogli napraviti sljedeći korak.

Također ćemo pratiti trenutni najbolji rezultat, procijenjeni ukupni rezultat i trenutačno najbolji prethodni čvor za svaki čvor u sustavu.

Kao dio toga, moramo biti u mogućnosti izračunati dvije različite ocjene. Jedan je rezultat koji dolazi od jednog čvora do drugog. Druga je heuristika koja daje procjenu troškova od bilo kojeg čvora do odredišta. Ova procjena ne mora biti točna, ali veća točnost dat će bolje rezultate. Jedini uvjet je da obje ocjene budu međusobno u skladu - to jest, nalaze se u istim jedinicama.

Na samom početku, naš otvoreni skup sastoji se od našeg početnog čvora, a mi uopće nemamo informacije o bilo kojim drugim čvorovima.

Na svakoj ćemo iteraciji:

• Odaberite čvor iz našeg otvorenog skupa koji ima najnižu procijenjenu ukupnu ocjenu
• Uklonite ovaj čvor iz otvorenog skupa
• Dodajte otvorenom skupu sve čvorove do kojih možemo doći

Kada to učinimo, razrađujemo i novi rezultat od ovog čvora do svakog novog kako bismo provjerili radi li se o poboljšanju onoga što smo do sada dobili, a ako jest, tada ažuriramo ono što znamo o tom čvoru.

To se zatim ponavlja sve dok čvor u našem otvorenom skupu koji ima najnižu procijenjenu ukupnu ocjenu nije naše odredište, u kojem trenutku imamo rutu.

4.1. Obrađeni primjer

Na primjer, krenimo od "Marylebone" i pokušajmo pronaći put do "Bond Street".

Na samom početku, naš otvoreni set sastoji se samo od "Marylebone". To znači da je ovo implicitno čvor za koji imamo najbolji "procijenjeni ukupni rezultat".

Naše slijedeće stanice mogu biti „Edgware Road“ s cijenom od 0,4403 km ili „Baker Street“ s cijenom od 0,4153 km. Međutim, "Edgware Road" je u pogrešnom smjeru, pa naša heuristika odavde do odredišta daje ocjenu 1,4284 km, dok "Baker Street" ima heurističku ocjenu 1,0753 km.

To znači da se nakon ove iteracije naš otvoreni set sastoji od dva unosa - „Edgware Road“, s procijenjenom ukupnom ocjenom 1,88687 km, i „Baker Street“, s procijenjenom ukupnom ocjenom 1,4906 km.

Naša druga iteracija tada započinje od "Baker Street", jer ovo ima najnižu procijenjenu ukupnu ocjenu. Odavde, naša slijedeća stajališta mogu biti „Marylebone“, „St. John's Wood ”,„ Great Portland Street ”, Regent's Park” ili „Bond Street”.

Nećemo raditi kroz sve ovo, ali uzmimo "Marylebone" kao zanimljiv primjer. Trošak dolaska opet je 0,4153 km, ali to znači da ukupni trošak sada iznosi 0,8306 km. Uz to, heuristika odavde do odredišta daje ocjenu 1,332 km.

To znači da bi procijenjeni ukupni rezultat bio 2,1536 km, što je gore nego prethodni rezultat za ovaj čvor. To ima smisla jer smo u ovom slučaju morali napraviti dodatni posao da ne bismo stigli nikamo. To znači da ovo nećemo smatrati održivim putem. Kao takvi, detalji za "Marylebone" nisu ažurirani i nisu dodani natrag na otvoreni set.

5. Implementacija Jave

Sad kad smo razgovarali o tome kako ovo funkcionira, zapravo ga provedimo. Izgradit ćemo generičko rješenje, a zatim ćemo implementirati kôd potreban da bi radio za London Underground. Tada ga možemo koristiti za druge scenarije primjenom samo tih specifičnih dijelova.

5.1. Predstavljanje grafikona

Prvo, moramo biti u stanju predstaviti svoj graf koji želimo preći. To se sastoji od dvije klase - pojedinačnih čvorova, a zatim grafa u cjelini.

Predstavljat ćemo naše pojedinačne čvorove sa sučeljem tzv GraphNode:

javno sučelje GraphNode {String getId (); }

Svaki naš čvor mora imati ID. Sve ostalo je specifično za ovaj određeni graf i nije potrebno za opće rješenje. Ove su klase jednostavni Java Beans bez posebne logike.

Naš ukupni graf tada je predstavljen klasom koja se jednostavno naziva Grafikon:

javna klasa Graph {privatni konačni čvorovi Set; privatna konačna karta veze; javni T getNode (String id) {return nodes.stream () .filter (node ​​-> node.getId (). jednako (id)) .findFirst () .orElseThrow (() -> new IllegalArgumentException ("Nije pronađen čvor sa ISKAZNICA")); } public Set getConnections (T čvor) {return connections.get (node.getId ()). stream () .map (this :: getNode) .collect (Collectors.toSet ()); }}

Ovo pohranjuje sve čvorove u našem grafu i ima znanje koji se čvorovi s kojima povezuju. Tada možemo dobiti bilo koji čvor pomoću ID-a ili sve čvorove povezane s danim čvorom.

U ovom smo trenutku sposobni predstaviti bilo koji oblik grafa koji želimo, s bilo kojim brojem rubova između bilo kojeg broja čvorova.

5.2. Koraci na našoj ruti

Sljedeće što nam treba je naš mehanizam za pronalaženje ruta kroz grafikon.

Prvi dio ovoga je neki način generiranja rezultata između bilo koja dva čvora. Mi ćemo Zapisničar sučelje i za rezultat do sljedećeg čvora i za procjenu do odredišta:

javno sučelje Scorer {double computeCost (T od, T do); }

S obzirom na početni i krajnji čvor, tada dobivamo rezultat za putovanje između njih.

Također nam je potreban omot oko naših čvorova koji sadrži neke dodatne informacije. Umjesto da bude a GraphNode, ovo je RouteNode - jer je to čvor u našoj izračunatoj ruti umjesto jednog u cijelom grafikonu:

klasa RouteNode implementira Usporedivu {privatnu konačnu T struju; privatni T prethodni; privatni dvostruki routeScore; privatni dvostruki procijenjeniScore; RouteNode (T trenutna) {this (current, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode (T trenutni, T prethodni, dvostruki routeScore, dvostruki procijenjeniScore) {this.current = current; this.previous = prethodno; this.routeScore = routeScore; this.estimatedScore = procijenjeniScore; }}

Kao i sa GraphNode, ovo su jednostavni Java Beans koji se koriste za spremanje trenutnog stanja svakog čvora za trenutni izračun rute. Dali smo ovo jednostavni konstruktor za uobičajeni slučaj kada prvi put posjećujemo čvor i još nemamo dodatne informacije o njemu.

To također trebaju biti Usporedive ipak, tako da ih možemo poredati prema procijenjenom rezultatu kao dijelu algoritma. To znači dodavanje a compareTo () metoda za ispunjavanje zahtjeva Usporedive sučelje:

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

5.3. Pronalaženje naše rute

Sada smo u mogućnosti generirati svoje rute na našem grafikonu. Ovo će biti razred koji se zove RouteFinder:

javna klasa RouteFinder {privatni konačni graf grafa; privatni konačni strijelac nextNodeScorer; privatni konačni strijelac targetScorer; javni popis findRoute (T od, T do) {baciti novi IllegalStateException ("Ruta nije pronađena"); }}

Imamo grafikon kojim pronalazimo rute i naša dva strijelca - jedan za točan rezultat za sljedeći čvor i jedan za procijenjeni rezultat do našeg odredišta. Također smo dobili metodu koja će uzeti početni i završni čvor i izračunati najbolju rutu između njih dvije.

Ova metoda treba biti naš A * algoritam. Sav ostatak našeg koda ulazi unutar ove metode.

Počinjemo s nekim osnovnim postavljanjem - našim „otvorenim skupom“ čvorova koje možemo smatrati sljedećim korakom i mapom svakog čvora koji smo do sada posjetili i što o njemu znamo:

Red čekanja openSet = novi PriorityQueue (); Karta allNodes = nova HashMap (); RouteNode start = novi RouteNode (od, null, 0d, targetScorer.computeCost (od, do)); openSet.add (početak); allNodes.put (od, početak);

Naš otvoreni set u početku ima jedan čvor - našu početnu točku. Ne postoji prethodni čvor za to, do rezultata je 0, a mi imamo procjenu koliko je udaljen od našeg odredišta.

Upotreba a PriorityQueue jer otvoreni set znači da automatski dobivamo najbolji unos s njega, na temelju našeg compareTo () metoda od ranije.

Sada ponavljamo dok ili ne ostanemo bez čvorova koje ćemo pogledati ili je najbolje dostupno čvorište naše odredište:

while (! openSet.isEmpty ()) {RouteNode next = openSet.poll (); if (next.getCurrent (). equals (to)) {Popis rute = novi ArrayList (); RouteNode current = next; do {route.add (0, current.getCurrent ()); current = sviNodovi.get (current.getPrevious ()); } while (trenutno! = null); put povratka; } // ...

Kad pronađemo odredište, možemo izgraditi rutu ponovnim gledanjem prethodnog čvora dok ne dođemo do početne točke.

Dalje, ako nismo stigli na odredište, možemo smisliti što dalje:

 graph.getConnections (next.getCurrent ()). forEach (veza -> {RouteNode nextNode = allNodes.getOrDefault (veza, novi RouteNode (veza)); allNodes.put (veza, nextNode); dvostruki newScore = next.getRouteScore () + nextNodeScorer.computeCost (next.getCurrent (), veza); if (newScore <nextNode.getRouteScore ()) {nextNode.setPrevious (next.getCurrent ()); nextNode.setRouteScore (newScore); nextNode.setEstimatedScore (newScore + targetScorer .computeCost (veza, do)); openSet.add (nextNode);}}); baciti novi IllegalStateException ("Ruta nije pronađena"); }

Ovdje vršimo iteraciju preko povezanih čvorova iz našeg grafa. Za svaku od njih dobivamo RouteNode što imamo za to - stvaranje novog ako je potrebno.

Zatim izračunavamo novi rezultat za ovaj čvor i vidimo je li jeftiniji od onoga što smo imali do sada. Ako je to slučaj, ažuriramo ga tako da odgovara novoj ruti i dodamo ga otvorenom skupu za razmatranje sljedeći put.

Ovo je cijeli algoritam. To ponavljamo sve dok ili ne postignemo svoj cilj ili ne uspijemo doći do njega.

5.4. Posebni detalji za londonsko podzemlje

Do sada imamo generički A * tragač, ali nedostaju nam specifičnosti potrebne za naš točan slučaj upotrebe. To znači da trebamo konkretnu provedbu oba GraphNode i Zapisničar.

Naši čvorovi su stanice u podzemlju, a mi ćemo ih modelirati s Stanica razred:

javna klasa Station implementira GraphNode {private final String id; privatni konačni naziv niza; privatna konačna dvostruka širina; privatna konačna dvostruka dužina; }

Ime je korisno za gledanje rezultata, a zemljopisna širina i dužina su za naše bodovanje.

U ovom scenariju potrebna nam je samo jedna implementacija Zapisničar. Za to ćemo upotrijebiti formulu Haversine za izračunavanje ravne udaljenosti između dva para geografske širine / dužine:

javna klasa HaversineScorer implementira Scorer {@Override public double computeCost (Stanica od, Stanica do) {double R = 6372,8; // Zemljin radijus, u kilometrima dvostruko dLat = Math.toRadians (to.getLatitude () - from.getLatitude ()); dvostruki dLon = Math.toRadians (to.getLongitude () - from.getLongitude ()); dvostruki lat1 = Math.toRadians (from.getLatitude ()); dvostruki lat2 = Math.toRadians (to.getLatitude ()); dvostruki a = Math.pow (Math.sin (dLat / 2), 2) + Math.pow (Math.sin (dLon / 2), 2) * Math.cos (lat1) * Math.cos (lat2); dvostruki c = 2 * Math.asin (Math.sqrt (a)); povrat R * c; }}

Sad imamo gotovo sve što je potrebno za izračunavanje putova između bilo koja dva para stanica. Jedino što nedostaje je grafikon veza između njih. Ovo je dostupno na GitHubu.

Upotrijebimo ga za mapiranje rute. Generirat ćemo jedan od Earl's Courta do Angela. Ovo ima niz različitih mogućnosti putovanja, na najmanje dvije cijevne linije:

javna praznina findRoute () {Popis rute = routeFinder.findRoute (underground.getNode ("74"), underground.getNode ("7")); System.out.println (route.stream (). Map (Station :: getName) .collect (Collectors.toList ())); }

Ovo generira put Earl's Courta -> Južni Kensington -> Green Park -> Euston -> Angel.

Očiti put kojim bi krenuli mnogi ljudi vjerojatno bi bio Earlov grof -> Spomenik -> Angel, jer je to imalo manje promjena. Umjesto toga, ovo je krenulo znatno izravnijim putem, iako je značilo više promjena.

6. Zaključak

U ovom smo članku vidjeli što je A * algoritam, kako funkcionira i kako ga implementirati u vlastite projekte. Zašto ovo ne biste uzeli i proširili za svoje potrebe?

Možda ga pokušati proširiti kako bi se uzele u obzir izmjene između cijevnih vodova i vidjelo kako to utječe na odabrane rute?

I opet, cjeloviti kôd članka dostupan je na GitHubu.