Traženje putanje

Traženje putanje kompjuterskom aplikacijom je pronalazak najkraće putanje između dve tačke. To je praktičnija varijanta rešavanja lavirinata. Ovo polje istraživanja oslanja se na Dajkstrin algoritam za pronalaženje najkraće putanje na težinskom grafu .

Algoritmi

U suštini, metod traženja putanje traži graf počevši od jednog čvora i nastavlja pretraživanje na susedne čvorove dok se ne pronađe ciljni čvor, sa nameom da se pronađe najkraći put. Iako pretraživanja grafa, kao što su pretraga u širinu nalazi put za dato vreme, druge metode koje "istražuju" graf, imaju tendenciju da ranije stignu do odredišta. Analogija bi bila da osoba hoda po sobi, unapred ispituje svaki mogući put, osoba obično hoda u pravcu destinacije i odstupa od putanje da bi izbegla prepreke, i da odstupa što je manje moguće.

Dva osbnovna problema traženja putanje su (1) da pronađe put između dva čvora u grafu; i (2) pronaći optimalno najkraći put do problema. Osnovni algoritmi kao što su pretraga u širinu i pretraga u dubinu traženja odredišta je prvi problem iscrpljivanja svih mogućnosti; počev od datog čvora, oni prelaze preko svih mogućih puteva dok ne stignu do ciljnog čvora. Ovi algoritmi imaju $O(|V|+|E|)$ , ili linearno vreme, gde je V broj čvorova i E broj grana između čvorova.

Što je komplikovaniji problem pronalaženje putanje je optimalniji. Detaljan pristup u ovom slučaju poznat kao Belman-Fordov algoritam, koji daje složenost vremena $O(|V||E|)$ , ili kvadratno vreme. Međutim, nije neophodno ispitivati sve moguće puteve kako bi se pronašao jedan optimalan. Algoritmi kao što su A* algoritam i Dajkstrin algoritam strateški eliminišu putanju, heurostočki ili putem dinamičkog programiranja. Eliminisanje nemogućih puteva, ovi algoritmi mogu da postignu manju složenost vremena $O(|E|\log(|V|))$ .^[1]

Naredni algoritmi su među najboljim opštim algoritmima koji rade na grafu bez predprocesiranja. Međutim, u praktičnom usmerena-putanja sistemu, čak i bolje vreme složenosti može postići algoritam koji može pre-procesa postići bolje performanse.^[2]. Jedan takav algoritam je kontrakcija hijerarhije.

Dajkstrin algoritam

Uobičajeni primer grafa zasnovan na algoritmu traženja putanje je Dajkstrin algoritam. Ovaj algoritam počinje od početnog čvora i "otvorenog skupa" kandidata čvorova. Na svakom koraku, čvor n otvorenom skupu sa najmanjom udaljenosti se od samog početka ispitue. Čvor je označen kao "zatvoren", a svi susedni čvorovi se dodaju na otvoren skup ako nisu već razmatrani. Ovaj proces ponavlja se sve dok se ne pronađe put do cilja. Pošto su čvorovi sa najmanjom udaljenosti prvi put pregledani, prvi put je naći, put do njega će biti najraći put.^[3]

Dajkstrin algoritam ne postoji ako postoji grana sa negativnom težinom. Hipotetički, situacije u kojoj čvorovi A, B, i C formiraju povezan neusmeren graf sa granama AB = 3, AC = 4, i BC = −2, optimalnost puta od A do C košta 1, a optimalnost puta od A do B košta 2. Dajkstrin algoritam počev od A će prvo ispitati B, jer je on najbliži. To će dodeliti troškak 3 do njega, i označiti je zatvorenom, što znači da njegova cena nikada neće biti preispitana. Dakle, Dajkstrin ne može proceniti grane sa negativnim težinama. Međutim, pošto za mnoge praktične svrhe nikada neće biti grana sa negativnim težinama, Dajkstrin algoritam je uglavnom pogodan za potrebe traženja putanje.

A* algoritam

A* je varijanta Dajkstrin algoritma koji se najčešće koristi u igrama. A* dodeljuje težinu svakom otvorenom čvoru na težini grane tog čvora plus približno rastojanje između tog čvora i završne obrade. Ovo približno rastojanje je heuristika, i predstavlja najmanju moguću udaljenost između tog čvora i kraja. Ovo omogućava eliminisanje dugih puteva kada se nađe početni put. Ako postoji put dužine x između početnog i krajnjeg čvora, kao i minimalna razdaljina između čvora i krajnjeg čvora veća od x, taj čvor ne mora biti pregledan.^[4]

A* koristi heuristiku da poboljša odnos sa Dajkstrin algoritmom. Kada je heuristika procenjena na nulu, A* je ekvivalentan sa Dajkstrin algoritmom. Heuristička procena se povećava i približava pravoj razdaljini, A* nastavlja da pronalazi optimalne putanje, ali radi brže (na osnovu ispitivanja manje čvorova). Kada je heuristička vrednost tačno udaljena od odredišta, A* ispituje najmanje čvorove. (Međutim, generalno je nepraktično da se napiše heuristička funkcija koja uvek izračunava pravu putanju). Kad se vrednost heuristike povećava, A* istražuje manje čvorova, ali ne garantuje optimalnu putanju. U mnogim aplikacijama, kao što su video igre, to je prihvatljivo pa čak i poželjno, kako bi zadržali da algoritam radi brzo.

Uzorak algoritma

Ovo je prilično jednostavan i lak za razumevanje algoritam traženja putanje za mape bazirane na pločicama. Za početak, imate mapu, početak koordinata i destinaciju koordinata. Mapa će izgledati ovako, X je zid, S početak, 0 je kraj i postoji otvoreni prostor, brojevi duž vrha i desne grae su kolone i redovi brojeva:

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Prvo napraviti listu koordinata, koju ćemo koristiti kao red. Red će biti pokrenut sa jednom koordinaom, kraj koordinata. Svaka koordinata će imati privrženu kontra promenljivu (svrha ovoga će uskoro postati evidentna). Tako da red počinje sa ((3,8,0)).

Zatim, idite kroz svaki element u redu, uključujući i elemente dodate na kraju tokom algoritma, i za svaki element, uraditi sledeće:

Napraviti listu sa 4 susedne ćelije, sa kontra promenljivom aktuelnog elementa brojača promenljive + 1 (u našem primeru četiri ćelije su ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
Proveriti sve ćelije u svakoj listi za sledeća dva uslova:
1. Ako je ćelija zid, uklonite ga iz liste
2. Ako postoji element u glavnoj listi sa istim koordinatama i jedan jednak ili veći brojač, uklonite ga iz liste
Dodaj sve preostale ćelije na listi do kraja glavne liste
Prelazak na sledeću stavku na listi

Tako, nakon poteza 1, lista elemenata je ovo: ((3,8,0),(2,8,1),(4,8,1))

Nakon 2 poteza:((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
Nakon 3 poteza:(...(1,7,3),(4,6,3),(5,7,3))
Nakon 4 poteza: (...(1,6,4),(3,6,4),(6,7,4))
Nakon 5 poteza: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
Nakon 6 poteza: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
Nakon 7 poteza: ((1,3,7)) - problem rešen, završiti ovu fazu algoritma - na umu da ako imate više jedinica jure isti cilj (kao u mnogim igrama - kraj za početak pokrenuti pristpu algoritmima namerno da tu olakša), možete nastaviti sve dok se čitava mapa ne prenese, dok se ne dostigne da su sve jedinice ili kontra granica.

Сада, мапа бројача на мапи, узима ово:

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Sada se kreće od S (7) i ide na obližnje ćelije sa najmanjim brojem (neproverene ćelije se mogu premestiti). Put je (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0). U slučaju da su dva broja podjednako mala (npr. S je bio (2,5))), odabrati slučajan smer - dužine su iste. Algoritam je sada završen.

U video igrama

Traženje putanje u kontekstu video igara tiče se načina na koji pokretno lice pronalazi put oko prepreke; najčešći kontekst strategija u realnom vremenu igre (u kojoj igrač usmerava jedinice oko prostora koji sadrži prepreke), ali ovi oblici se mogu naći u većini modernih igara. Porastao je značaj traženja putanje kao igre i njihove okoline su postale složenije, i kao rezultat toga, mnogi AI softverski paketi su razvijeni da reše problem.

Igre strategije obično sadrže velike površine otvorenih terena koji su često relativno jednostavni za prelaženje, mada je zajedničko za više od jedne jedinice da se prelazi istovremeno: ovo stvara potrebu za različitim i često značajno više složenim algoritmom da bi se izbegle gužve u saobraćaju na zakrčenim mestima na terenu, ili kada jedinice dolaze u kontakt jedna sa drugom. U strateškim igrama sa kartama normalno je podeljen na pločice, kao čvorovi u algoritmu traženja putanje.

Više otvorenih završnih struktura kao što su Pucačka igra iz prvog lica često imaju više zatvorenih (ili mešavinu zatvorenih i otvorenih) oblasti koje nisu samo podeljene u čvorove, i koja je dala povode za korišćenje navigacije mreža. Oni su konstruisani predstavljanjem čvorova u svetu igara koji čuvaju detalje koji su čvorovi pristupačni iz njega.

Algoritmi koji se koriste za traženje putanje

A* algoritam
Dajkstrin algoritam, neinformisani, manje moćni poseban slučaj A* algoritma
D*, porodica postepenog heurističkog pretraživanja algoritama za probleme u kojima se razlikuju ograničenja tokom vremena ili nisu u potpunosti poznati kada agent prvi put planira svoju putanju
Algoritam bilo koji ugao planiranja putanje, porodica algoritama za planiranje putanje koje nisu ograničene na kretanje duž grana u pretrazi grafa, namenjen da bude u stanju da preuzme ugao i na taj način pronađe kraće putanje.

Reference

^ „7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm[[Kategorija:Botovski naslovi]]”. Arhivirano iz originala 04. 03. 2016. g. Pristupljeno 26. 01. 2016. Sukob URL—vikiveza (pomoć)
^ Delling, D.; Sanders, P.; Schultes, D.; Wagner, D. (2009). "Engineering route planning algorithms". Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. str. 117–139. . doi:10.1007/978-3-642-02094-0_7. Nedostaje ili je prazan parametar |title= (pomoć)
^ 5.7.1 Dijkstra Algorithm
^ Introduction to A* Pathfinding

[1] „7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm[[Kategorija:Botovski naslovi]]”. Arhivirano iz originala 04. 03. 2016. g. Pristupljeno 26. 01. 2016. Sukob URL—vikiveza (pomoć)

[2] Delling, D.; Sanders, P.; Schultes, D.; Wagner, D. (2009). "Engineering route planning algorithms". Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. str. 117–139. . doi:10.1007/978-3-642-02094-0_7. Nedostaje ili je prazan parametar |title= (pomoć)

[3] 5.7.1 Dijkstra Algorithm

[4] Introduction to A* Pathfinding

[1]

[2]

[3]

[4]