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 nadju 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 dodje 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).[1]

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 dodju 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 .[2]

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).[3]

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 ponovno koristite u različitim kontekstima, jer je primetilo da "rade" u jednom kontekstu, bez da je matematički dokazano 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.

Reference[уреди]

  1. ^ Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. стр. 11. 
  2. ^ Allen Newell and Herbert A. Simon (1976). „Computer Science as Empirical Inquiry: Symbols and Search“. Comm. of the ACM 19: 113–126. 
  3. ^ Stuart Russell and Peter Norvig (2010). Artificial Intelligence: A Modern Approach. Prentice Hall. 

Literatura[уреди]

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