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.

Референце

  1. ^ Russell, Stuart; Peter Norvig (2003). Artificial Intelligence: A Modern Approach (2nd изд.). Upper Saddle River, New Jersey: Prentice Hall. ISBN 978-0-13-790395-5. 
  2. ^ Russell, Stuart; Peter Norvig (2010). Artificial Intelligence: A Modern Approach (3rd изд.). Prentice Hall. ISBN 978-0-13-604259-4. 

Литература