Heuristika (informatika)

U informatici, veštačkoj inteligenciji, i matematičkoj optimizaciji, heuristika je tehnika rešavanja ili brže od klasičnih metoda, ili nalaženja približnog rešenja kada klasični metodi ne mogu da nađu tačno rešenje. Kod heuristika se menja optimalnost, kompletnost, tačnost, i / ili preciznost za brzinu.

Definicija i Motivacija

Cilj heuristike je da se brzo dođe do rešenja koje je dovoljno dobro za problem koji se rešava. To rešenje ne mora biti nužno najbolje , ili čak može biti samo aproksimacija tačnog rešenja. I pored toga takvo rešenje je vredno zato što za njegovo nalaženje nije potrošeno preterano mnogo vremena.

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.

Kompromis

Kriterijum kompromisa se koristi da bi odlučilo za ili protiv korišćenja heuristike za dati problem i on uključuje sledeće:

• Optimalnost: Kad postoji više rešenja za dati problem, da li heuristika garantuje nalaženje najboljeg rešenja? Da li nam najbolje rešenje upošte treba?

• Kompletnost: Kad postoji više rešenja za dati problem, da li heuristika nalazi sva rešenja? Da li nam uopšte trebaju sva rešenja? Mnoge heuristike nalaze samo jedno rešenje.

• Preciznost i tačnost: Može li heuristika da pruži interval poverenja za navodno rešenje? Da li je u rešenju greška suviše velika?

• Vreme izvršavanja: Da li je ovo najbolja heuristika za ovaj tip problema? Neke heuristike konvergijaju brže od ostalih dok neke samo su marginalno brže od klasičnih metoda.

U nekom slučajevima pokazuje se da je teško oceniti da li je rešenje koje je našla heuristika dovoljno dobro, zato što teorija na kojoj je zasnovana ta heuristika nije veoma razrađena.

Primeri

Jednostavniji Problem

Jedan način postizanja računskih performansi u heuristici je rešavanje jednostavnijeg problema čije rešenje je ujedno i rešenje početnog problema. Takva heuristika ne može naći sva rešenja početnog problema, ali može naći rešenje brže jer je jednostavniji problem lakše rešiti.

Problem putujućeg trgovca

Jedan primer aproksimacije je opisan od strane Jon Bentley za rešavanje problema putujućeg trgovca (TSP) je izbor redosleda crtanja koristeći ploter. (TSP) je NP-kompletan problem tako da opmtimalno rešenje čak i za problem umerene veličine je težak za rešavanje. Moguće je koristiti pohlepni algoritam za dobro ali ipak neooptimalno rešenje koje je zapravo aproksimacija optimalnog rešenja i to za razumno vreme.Heuristika pohlepnog algoritma diktira da se izabere trenutno najbolji sledeći korak , isljučujući kasnije korake koji bi bili možda bolji. Praktično to je dovoljno dobro rešenje , dok teorija kaže da postoje bolja (u nekim slučajevima i koliko bolja).

Pretraga

Još jedan dobar primer ubrzanja algortima može se primeniti u nekim problemima pretrage. Inicijalno, heuristika pokušava sve mogućnosti u svakom koraku, nalik potpunoj pretragi. Međutim algortam može u svakom koraku da zaustavi pretragu ako se se desi da trenutna mogučnost je lošija od najboljeg rešenja koje je već pronađeno. Kod takvih problema pretrage, heuistika može pružiti dobre prve izbore tako da se lošije putanje eliminišu rano.

Newell i Simon: Hipoteza heurističkog pretraživanja

U njihovom govoru povodom primanja Tjuringove nagrade , Allen Newell i Herbert A. Simon raspravljaju o o Hipotezi heurističkog pretraživanja: fizički sistem simbola koji će više puta će generisati i modifikovati poznate strukture simbola dok se ne stvori struktura koja odgovara rešenju. Svaka sledeća iteracija zavisi od prethodnog koraka , i na taj način heuristička pretraga uči koje puteve da koristi a koje da odbacuje mereći koliko je blizu je trenutna iteracija rešenju. Samim tim neke mogućnosti se neće generisati jer će biti izmereno da je manje moguće da dođu do rešenja.

Heuristički metod postiže taj zadatak koristeći drveta pretrage. Međutim,umesto da generiše sve grane , heuristika bira grane koje će verovatnije doći do rešenja od ostalih. Selektivna je u svakoj tački odluke, birajući grane koje če pre dovesti do rešenja .

Skeniranje virusa

Mnogi antivirusi u realnom vremenu koriste heurističke signature za detekciju virusa i ostalih oblika zlonameranih programa.

Russell i Norvig

Više primera heuristika mogu se naći u (Russell i Norvig 2010).

Zamke

Kako ljudi izmisle heuristiku? Neke heuristike imaju snažnu osnovnu teoriju, oni su ili izvedene u odozgo-nadole način iz teorije ili iz zaključaka dobijenih na osnovu eksperimentalnih podataka. Do ostalih se dolazi emprijski bez ikakve teorije. Ove druge su izloženi brojnim zamkama.

Kada se heuristike ponovo koristite u različitim kontekstima, jer je primetilo da "rade" u jednom kontekstu, bez matematičkog dokaza da zadovoljavaju određeni skup zahteva, moguće je da je trenutni skup podataka ne predstavlja nužno buduće skupove podataka i da je navodno "rešenje" sličnije buci nego rešenju.

Statistička analiza može biti sprovedena pri primeni heuristika radi procene verovatnoće pogrešnih rezultata. Da bi se koristila heuristika za rešavanja problema pretrage ili problema ranca, neophodno je proveriti da li je heuristika dopustiva. Ako nam je data heuristička funkcija $h(v_{i},v_{g})$ koja aproksimira stvarnu optimalnu distancu $d^{\star }(v_{i},v_{i})$ do ciljnog čvora $v_{g}$ u usmerenom grafu $G$ koji sadrži ukupno $n$ čvorova ili temena označenih sa $v_{0},v_{1},\cdots ,v_{n}$, "dopustivo" znači da važi $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ za sve $(v_{i},v_{g})$ gde je ${i,g}\in [0,1,...,n]$.

Ako heuristika nije dopustiva, moguće je da nikada neće doći do cilja, ili tako što bi završila u nekom mrtvom kraju grafa ili $G$ tako što bi preskakala natrag i naprijed između dva čvora $v_{i}$ and $v_{j}$ where ${i,j}\neq g$.

Literatura

• Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. стр. 11. 
• Stuart Russell and Peter Norvig (2010). Artificial Intelligence: A Modern Approach. Prentice Hall.