Pretraga o jedinstvenom trošku
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
U informatici, pojam pretraga o jedinstvenom trošku predstavlja pretraživački algoritam koji se koristi za posećivanje i pretraživanje stabla, strukture u obliku stabla ili grafa. Pretraga počinje od korena. Pretraga se nastavlja posećivanjem sledećeg najbližeg čvora sa najnižim ukupnim troškom u odnosu na koren. Čvorovi se jedan za drugim posećuju na ovaj način sve dok se ne dostigne zadato stanje.
Algoritam za pretraživanje obično podrazumeva proširivanje čvorova dodavanjem svih neproširenih susednih čvorova koji su direktnim putanjama povezani sa prioritetnim nizom. U ovom nizu, svakom čvoru se dodeljuje njegov ukupni trošak putanje od korena, a putanje sa najnižim troškom imaju prioritet. Čvor sa vrha niza se tako proširuje, dodavanjem narednog seta povezanih čvorova ukupnom trošku putanje od korena do odgovorajućeg čvora. Pretraga o jedinstvenom trošku je kompletna i optimalna samo ako trošak svakog od koraka prevazilazi neku pozitivnu granicu ε.[1]Najgori vid kompleksnosti vremena i prostora je O(b1 + C*/ε), gde C* predstavlja trošak optimalnog rešenja, a b faktor grananja. Kada su troškovi svih koraka jednaki, ovo postaje O(bd + 1).[2]
Pseudokod[уреди | уреди извор]
procedure UniformCostSearch(Graph, root, goal)
node := root, cost = 0
frontier := priority queue containing node only
explored := empty set
do
if frontier is empty
return failure
node := frontier.pop()
if node is goal
return solution
explored.add(node)
for each of node's neighbors n
if n is not in explored
if n is not in frontier
frontier.add(n)
else if n is in frontier with higher cost
replace existing node with n
Prikaz istraženih setova i granice (prioritetni niz):
Početni čvor: A
Krajnji čvor (cilj): G
| Korak | Granica: set (čvor, njegov trošak) objekata | Proširiti [*] | Proširen: set čvorova |
|---|---|---|---|
| 1 | {(A,0)} | A | ∅ |
| 2 | {(D,3),(B,5)} | D | {A} |
| 3 | {(B,5),(E,5),(F,5)} | B | {A,D} |
| 4 | {(E,5),(F,5),(C,6)} | E | {A,D,B} |
| 5 | {(F,5),(C,6)}[**] | F | {A,D,B,E} |
| 6 | {(C,6),(G,8)} | C | {A,D,B,E,F} |
| 7 | {(G,8)} | G | {A,D,B,E,F,C} |
| 8 | ∅ |
^ * Čvor izabran za proširenje u narednom koraku.
^ ** B nije dodat granici zato što se nalazi u istraženom setu.
Pronađena putanja: A do D do F do G.
Povezanost sa drugim algoritmima[уреди | уреди извор]
Dijkstrin algoritam, koji je verovatno poznatiji, može se posmatrati kao varijanta pretrage o jedinstvenom trošku, koja nema ciljano stanje i gde se proces nastavlja sve dok se svi čvorovi ne uklone iz prioritetnog niza, to jest, dok se ne ustanovi najkraća putanja do svih čvorova (a ne samo do krajnjeg (ciljnog) čvora). Kao i Dijkstrin algoritam, pretraga o jedinstvenom trošku takođe garantuje (pod uslovom da težine ivica nisu negativne) pronalaženje najkraće putanje do određenog čvora nakon što se čvor izdvoji iz prioritetnog niza.
Pretraga o jedinstvenom trošku je poseban slučaj |A* algoritma čija je heuristika konstantna funkcija. Ukoliko se A* koristi sa monotonom heuristikom, onda ga možemo pretvoriti u pretragu o jedinstvenom trošku oduzimanjem sa svake ivice troška umanjenja heurističke vrednosti na toj ivici. Pretraga u širinu (BFS) je poseban primer pretrage o jedinstvenom trošku gde su troškovi svih ivica pozitivni i identični. Gde se primenom BFS tehnike prvo posećuje čvor sa najkraćom putanjom (brojem čvorova) od korena, pretraga o jedinstvenom trošku tehnika prvo posećuje čvor sa najkraćim troškom putanje (zbir težina ivica) od korena. Pretraga o jedinstvenom trošku predstavlja jednu od varijanata pretrage za prvim najboljim rešenjem.
Референце[уреди | уреди извор]
- ^ Russell, Stuart; Peter Norvig (2003). Artificial Intelligence: A Modern Approach (2nd изд.). Upper Saddle River, New Jersey: Prentice Hall. ISBN 978-0-13-790395-5.
- ^ Russell, Stuart; Peter Norvig (2010). Artificial Intelligence: A Modern Approach (3rd изд.). Prentice Hall. ISBN 978-0-13-604259-4.
Литература[уреди | уреди извор]
- Russell, Stuart; Peter Norvig (2010). Artificial Intelligence: A Modern Approach (3rd изд.). Prentice Hall. ISBN 978-0-13-604259-4.
- Russell, Stuart; Peter Norvig (2003). Artificial Intelligence: A Modern Approach (2nd изд.). Upper Saddle River, New Jersey: Prentice Hall. ISBN 978-0-13-790395-5.