Хеуристика (информатика)

У информатици, вештачкој интелигенцији, и математичкој оптимизацији, хеуристика је техника решавања или брже од класичних метода, или налажења приближног решења када класични методи не могу да нађу тачно решење. Код хеуристика се мења оптималност, комплетност, тачност, и / или прецизност за брзину.

Дефиниција и Мотивација

Циљ хеуристике је да се брзо дође до решења које је довољно добро за проблем који се решава. То решење не мора бити нужно најбоље , или чак може бити само апроксимација тачног решења. I поред тога такво решење је вредно зато што за његово налажење није потрошено претерано много времена.

Хеуристика може да да резултат сама по себи, или се може користити у спрези са оптимизационим алгоритмима ради унапређења њихове ефикасности.

Код НП-тешких проблема у теорији рачунарства хеуристике су једина могућа опција за широку лепезу комплексних проблема оптимизације који се рутински срећу у реалном свету.

Компромис

Критеријум компромиса се користи да би одлучило за или против коришћења хеуристике за дати проблем и он укључује следеће:

• Оптималност: Кад постоји више решења за дати проблем, да ли хеуристика гарантује налажење најбољег решења? Да ли нам најбоље решење упоште треба?

• Комплетност: Кад постоји више решења за дати проблем, да ли хеуристика налази сва решења? Да ли нам уопште требају сва решења? Многе хеуристике налазе само једно решење.

• Прецизност и тачност: Може ли хеуристика да пружи интервал поверења за наводно решење? Да ли је у решењу грешка сувише велика?

• Време извршавања: Да ли је ово најбоља хеуристика за овај тип проблема? Неке хеуристике конвергијају брже од осталих док неке само су маргинално брже од класичних метода.

У неком случајевима показује се да је тешко оценити да ли је решење које је нашла хеуристика довољно добро, зато што теорија на којој је заснована та хеуристика није веома разрађена.

Примери

Једноставнији Проблем

Један начин постизања рачунских перформанси у хеуристици је решавање једноставнијег проблема чије решење је уједно и решење почетног проблема. Таква хеуристика не може наћи сва решења почетног проблема, али може наћи решење брже јер је једноставнији проблем лакше решити.

Проблем путујућег трговца

Један пример апроксимације је описан од стране Jon Bentley за решавање проблема путујућег трговца (TSP) је избор редоследа цртања користећи плотер. (TSP) је НП-комплетан проблем тако да опмтимално решење чак и за проблем умерене величине је тежак за решавање. Могуће је користити похлепни алгоритам за добро али ипак неооптимално решење које је заправо апроксимација оптималног решења и то за разумно време.Хеуристика похлепног алгоритма диктира да се изабере тренутно најбољи следећи корак , исључујући касније кораке који би били можда бољи. Практично то је довољно добро решење , док теорија каже да постоје боља (у неким случајевима и колико боља).

Претрага

Још један добар пример убрзања алгортима може се применити у неким проблемима претраге. Иницијално, хеуристика покушава све могућности у сваком кораку, налик потпуној претраги. Међутим алгортам може у сваком кораку да заустави претрагу ако се се деси да тренутна могучност је лошија од најбољег решења које је већ пронађено. Код таквих проблема претраге, хеуистика може пружити добре прве изборе тако да се лошије путање елиминишу рано.

Newell и Simon: Хипотеза хеуристичког претраживања

У њиховом говору поводом примања Тјурингове награде , Allen Newell и Herbert A. Simon расправљају о о Хипотези хеуристичког претраживања: физички систем симбола који ће више пута ће генерисати и модификовати познате структуре симбола док се не створи структура која одговара решењу. Свака следећа итерација зависи од претходног корака , и на тај начин хеуристичка претрага учи које путеве да користи а које да одбацује мерећи колико је близу је тренутна итерација решењу. Самим тим неке могућности се неће генерисати јер ће бити измерено да је мање могуће да дођу до решења.

Хеуристички метод постиже тај задатак користећи дрвета претраге. Међутим,уместо да генерише све гране , хеуристика бира гране које ће вероватније доћи до решења од осталих. Селективна је у свакој тачки одлуке, бирајући гране које че пре довести до решења .

Скенирање вируса

Многи антивируси у реалном времену користе хеуристичке сигнатуре за детекцију вируса и осталих облика злонамераних програма.

Russell и Norvig

Више примера хеуристика могу се наћи у (Russell и Norvig 2010).

Замке

Како људи измисле хеуристику? Неке хеуристике имају снажну основну теорију, они су или изведене у одозго-надоле начин из теорије или из закључака добијених на основу експерименталних података. До осталих се долази емпријски без икакве теорије. Ове друге су изложени бројним замкама.

Када се хеуристике поново користите у различитим контекстима, јер је приметило да "раде" у једном контексту, без математичког доказа да задовољавају одређени скуп захтева, могуће је да је тренутни скуп података не представља нужно будуће скупове података и да је наводно "решење" сличније буци него решењу.

Статистичка анализа може бити спроведена при примени хеуристика ради процене вероватноће погрешних резултата. Да би се користила хеуристика за решавања проблема претраге или проблема ранца, неопходно је проверити да ли је хеуристика допустива. Ако нам је дата хеуристичка функција $h(v_{i},v_{g})$ која апроксимира стварну оптималну дистанцу $d^{\star }(v_{i},v_{i})$ до циљног чвора $v_{g}$ у усмереном графу $G$ који садржи укупно $n$ чворова или темена означених са $v_{0},v_{1},\cdots ,v_{n}$, "допустиво" значи да важи $h(v_{i},v_{g})\leq d^{\star }(v_{i},v_{g})$ за све $(v_{i},v_{g})$ где је ${i,g}\in [0,1,...,n]$.

Ако хеуристика није допустива, могуће је да никада неће доћи до циља, или тако што би завршила у неком мртвом крају графа или $G$ тако што би прескакала натраг и напријед између два чвора $v_{i}$ анд $v_{j}$ wхере ${i,j}\neq g$.

Литература

• Јон Лоуис Бентлеy (1982). Wритинг Еффициент Програмс. Прентице Халл. стр. 11. 
• Стуарт Русселл анд Петер Норвиг (2010). Артифициал Интеллигенце: А Модерн Аппроацх. Прентице Халл.