Pretraga po najboljim osobinama

Pretraga po najboljim osobinama je algoritam za pretraživanje koji istražuje graf tako što širi pretragu na sledeći najbolji čvor koji je izabran pomoću nekog navedenog pravila.

Jude Perl je opisao ovaj algoritam kao procenu obećavanja jednog čvora n pomoću „heuristične funkcije procene F(n) koja u opštem slučaju može da zavisi od opisa n, opisa cilja, informacija koje su prikupljene pomoću pretrage do tog trenutka i najvažnije, zavise od bilo kog dodatnog znanja o domenu problema“. 

Neki autori koriste ovaj algoritam da bi definisali pretagu sa heuristikom koja pokušava da predvidi koliko je blizu kraj putanje od rešenja, tako da bi se putanje za koje se proceni da su bliže  i prve produžene. Ovaj specifični tip pretrage se naziva i pohlepna pretraga po najboljim osobinama ili čista heuristička pretraga.

Efikasno određivanje najboljeg kandidata za priduživanje putanji je obično implementirano preko reda sa čekanjem.

A* algoritam je primer pretraga po najboljim osobinama, kao što je i B* algoritam . Ovi algoritmi se najčešće koriste za pronalazak putanje u kombinatorialnim pretragama. (Napomena: Ni A* ni B* nisu željna pretraga po najboljim osobinama jer oni uračunavaju udaljenost od početka kao i procenu distance do cilja).

Algoritam

Algoritam koji implementira pretragu po najboljim osobinama izgleda ovako:

OPEN = [initial state]
while OPEN is not empty or until a goal is found
do
 1. Remove the best node from OPEN, call it n.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. Evaluate each successor, add it to OPEN, and record its parent.

done

Napomena: Ova verzija algoritma nije završena, tj. ne nalazi uvek najbolju putanju između dva čvora, čak iako takva putanja postoji. Na primer, ulazi u beskonačnu petlju ako dođe do čvora koji je ponor (nema izlaznih grana). Onda bi se vratio nazad, dodao naslednika u listu opet i tako dalje.

Sledeća verzija proširuje algoritam da koristi još jednu listu, koja sadrži sve čvorove koji su procenjeni i neće biti prelaženi opet. Pošto neće gledati isti čvor više puta neće ulaziti i u beskonačnu petlju.

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
       a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent.
       b. Otherwise, if this new path is better than previous one, change its recorded parent.
          i.  If it is not in OPEN add it to OPEN.
          ii. Otherwise, adjust its priority in OPEN using this new evaluation.

done

Takođe treba napomenuti da se pseudo kod oba algoritma završava kada nije u stanju da nađe bilo kakvu putanju. Stvarna implementacija u nekom programskom jeziku bi zahtevala i obraćanje ovoj situaciji.

Pohlepna pretraga po najboljim osobinama

Koristeći pohlepni algoritam, proširi prvoh naslednika roditelja. Pošto je naslednik generisan:

1. Ako je heuristika naslednika bolja od roditeljeve, naslednik se stavlja na početak reda sa čekanjem (sa roditeljem ponovo ubačenim u red odmah iza njega), i petlja se obavlja ispočetka.
2. U suprotnom, naslednik se ubacuje u red (na lokaciju koja određuje njegova heuristika). Procedura će zatim proveriti i ostale naslednike ako postoje.

Vidi još

• Pretraga bima
• A* algoritam
• Dajkstrin algoritam