Heuristika i funkcija cijene

Faktor grananja i heuristika

Kvalitet pojedine strategije usmjerenog pretraživanja zavisiti od kvaliteta heurističke funkcije koju ta strategija koristi. Što je heuristička funkcija bolja procjena stvarne odaljenosti do ciljnog čvora, to će manji biti broj čvorova generisanih u toku usmjerenih pretraživanja.

Sve strategije heurističkog tipa rade na principu otkrivanja najperspektivnijeg čvora i kasnijeg testiranja da li je dostignut ciljni čvor.

Za ocjenu kvaliteta heurističkih funkcija se stoga koristi broj generisanih čvorova, kada se ona koristi. Heurističke funkcije se najčešće porede na osnovu efektivnog faktora grananja:

Ukoliko se nekom strategijom pretraživanja generiše N čvorova, a dubina rješenja je d, efektivni faktor grananja se određuje kao faktor grananja b* koji bi moralo imati drvo sa uniformnim grananjem da bi na dubini d imalo N generisanih čvorova (plus korijen):

Efektivni faktor grananja može varirati od jedne do druge realizacije.

Efektivni faktor grananja b* se može izmjeriti eksperimentalno na malom skupu problema i koristiti za ocjenu upotrijebljene heuristike. Pokazuje se da dobre heuristike imaju b* približno jednak jedinici, što ukazuje da su dobro usmjerene i da je njima moguće riješiti znatno velike probleme.

Metodi pretraživanja u dubinu i širinu predstavljaju trivijalne slučajeve algoritama uređenog pretraživanja Heuristička funkcija ocjene u tom slučaju predstavlja rastojanje od početnog čvora za pretragu u dubinu, i recipročnu vrijednost u slučaju pretrage u širinu. U oba slučaja se teži maksimizaciji heurističke funkcije pri izboru sljedećeg čvora.

Cilj heuristike je da se brzo dođe do rješenja koje je dovoljno dobro za problem koji se rješava. To rješenje ne mora biti nužno najbolje , ili čak može biti samo aproksimacija tačnog rešenja.
Heuristika može da da rezultat sama po sebi, ili se može koristiti u sprezi sa optimizacionim algoritmima radi unapređenja njihove efikasnosti.
Kod NP-teških problema u teoriji računarstva heuristike su jedina moguća opcija za široku lepezu kompleksnih problema optimizacije koji se rutinski sreću u realnom svetu.

U početnom momentu heuristika pokušava sve mogućnosti u svakom koraku, slično potpunoj pretrazi. Međutim algortam može u svakom koraku da zaustavi pretragu ako se se desi da je trenutna mogućnost (solution) lošija od najboljeg rješenja koje je već pronađeno (vidi UCS). Kod takvih problema pretrage, heuistika može pružiti dobre prve izbore tako da se lošije putanje eliminišu rano.