Евристика (информатика)

Во компјутерската наука, вештачката интелигенција и математичката оптимизација, евристиката (од грчки εὑρίσκω „Пронаоѓам, откривам“) е техника дизајнирана за побрзо решавање на проблем кога класичните методи се премногу бавни или пак за наоѓање приближно решение кога класичните методи не успеваат да изнајдат точно решение. Ова се постигнува со оптималност, комплетност, точност или прецизност на трговијата со брзината. На некој начин, може да се смета за кратенка.

Евристичка функција, е функција што ги рангира алтернативите во пребарувачките алгоритми на секој чекор на разгранување врз основа на достапните информации за да се одлучи која гранка да се следи. На пример, може да го приближи точното решение.^[1]

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

Целта на евристиката е да се произведе решение во разумна временска рамка, кое ќе биде доволно добро за решавање на проблемот што го има. Ова решение можеби не е најдобро од сите решенија за овој проблем, но можеби ќе може да ни го приближи точното решение.Сепак тој е сè уште вреден затоа што за негово пронаоѓање не ни е потребно долго време.

Евристиката може да произведе резултати сама по себе, или може да се користи заедно со некои алгоритми за оптимизација за да се подобри нивната ефикасност (на пример, може да се користат за да се генерираат добри вредности на семето).

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

Евристиката е основа на целото поле на вештачка интелигенција и компјутерска симулација на размислување, бидејќи тие можат да се користат во ситуации кога не постојат познати алгоритми.^[2]

Размена

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

• Оптималност: Кога постојат неколку решенија за даден проблем, дали евристиката гарантира дека ќе се најде најдоброто решение? Дали е всушност потребно да се најде најдоброто решение?
• Комплетност: Кога постојат неколку решенија за даден проблем, дали евристиката може да ги најде сите? Дали навистина ни требаат сите решенија? Многу евристички податоци имаат за цел да најдат само едно решение.
• Точност и прецизност: Дали евристиката може да обезбеди интервал на доверба за наводното решение? Дали лентата за грешки на решението е неразумно голема?
• Време на извршување : Дали е ова најдобро познат евристички начин за решавање на овој вид на проблем? Некои евристики се спојуваат побрзо од другите. Некои евристички податоци се само маргинално побрзи од класичните методи.

Во некои случаи, може да биде тешко да се одлучи дали решението пронајдено од евристичарот е доволно добро, бидејќи теоријата што лежи во основата на евристиката не е многу елаборирана.

Примери

Поедноставен проблем

Еден начин за постигнување на добивка во пресметката на перформансите што се очекува од евристиката се состои во решавање на поедноставен проблем чие решение е исто така решение за почетниот проблем.

Проблем со продавачот што патува

Пример за приближување е опишан од Џон Бентли за решавање на проблемот со продавачот што патува (TSP):

• „Со оглед на списокот на градови и растојанијата помеѓу секој пар градови, која е најкратката можна рута што го посетува секој град и се враќа во градот на тргнување?

за да се избере редоследот за цртање со употреба на плотер-плотер. Познато е дека TSP е НП-тврд, така што е тешко да се реши оптимално решение за проблем дури и со умерена големина. Наместо тоа, алчниот алгоритам може да се искористи за да се даде добро, но не и оптимално решение (тоа е апроксимација на оптималниот одговор) за разумно кратко време. Евристичкиот алчен алгоритам вели да изберете што е во моментов најдобриот следен чекор, без оглед дали тоа спречува (или дури и ги прави невозможни) добрите чекори подоцна. Тоа е евристичко во таа практика, вели дека тоа е доволно добро решение, теоријата вели дека постојат подобри решенија (па дури и може да каже колку е подобро во некои случаи).^[3]

Пребарување

Друг пример за евристичко правење алгоритам побрз се јавува кај одредени проблеми со пребарувањето. Првично, евристиката ја обидува секоја можност на секој чекор, како алгоритам за пребарување со целосен простор. Но, може да го запре пребарувањето во кое било време, ако моменталната можност е веќе полоша од веќе пронајденото најдобро решение. Во вакви проблеми со пребарување, евристички може да се искористи за да се испробаат првиот избор прво, така што лошите патеки можат рано да се елиминираат (видете алфа-бета градинарски ). Во случај на алгоритми за најдобро пребарување, како што е пребарување А *, евристиката ја подобрува конвергенцијата на алгоритмот, истовремено задржувајќи ја нејзината точност, сè додека евидистичката е дозволена .

Њуел и Симон: хипотеза за евристичко пребарување

Во својот говор за прифаќање на наградата Туринг, Ален Њуел и Херберт А. Симон дискутираат за хипотезата за евристичко пребарување: систем на физички симбол постојано генерира и модифицира познати структури на симболи додека создадената структура не одговара на структурата на решението. Секој следен чекор зависи од чекор пред него, со што евристичкото пребарување учи кои патишта треба да се следат и кои не треба да се земат предвид со мерење колку тековниот чекор е близу до решението. Затоа, некои можности никогаш нема да бидат генерирани, бидејќи се мери дека е помала веројатноста да се заврши решението.

Евристичкиот метод може да ја заврши својата задача со користење дрва за пребарување. Сепак, наместо да ги генерира сите можни гранки на решенија, евристиката избира гранки со поголема веројатност да произведат резултати од другите гранки. Селективно е во секоја точка на одлука, избира гранки за кои постои поголема веројатност да произведат решенија.^[4]

Антивирусен софтвер

Антивирусниот софтвер често користи евристички правила за откривање на вируси и други форми на малициозен софтвер. Евристичкото скенирање бара код и/или модели на однесување заеднички за класа или семејство на вируси, со различни групи правила за различни вируси. Ако се открие дека податотека или процес на извршување содржи соодветни шеми на кодови и / или го извршува тој сет на активности, тогаш скенерот заклучува дека податотеката е заразена. Најнапредниот дел од евристичкото скенирање засновано на однесување е тоа што може да работи против високо рандомизирани само-модифицирачки/мутирачки (полиморфни) вируси кои не можат со сигурност да се детектираат со поедноставни методи за скенирање на низи. Евристичкото скенирање има потенцијал да открие идни вируси без да бара вирусот најпрво да се открие на друго место, да се достави до развивачот на скенер за вируси, да се анализира и да се ажурира откривање за скенерот доставен до корисниците на скенерот.

Стапици

Некои евристички податоци имаат силна основна теорија; или тие се изведени на начин одгоре надолу од теоријата или се доаѓа до нив врз основа на експериментални или реални податоци. Другите се само правилни правила засновани на набљудување или искуство во реалниот свет, дури и без поглед на теоријата. Вторите се изложени на поголем број стапици.

Кога евристиката повторно се користи во различни контексти затоа што се виде дека „работи“ во еден контекст, без математички докажано дека исполнува даден пакет на барања, можно е тековниот сет на податоци не мора да претставува иден сет на податоци и дека наводните „решенија“ се покажаа слични на бучавата.

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

Ако евристикот не е допуштен, тој никогаш нема да ја најде целта, или со тоа што ќе заврши во ќорсокак на графиконот ${\displaystyle G}$ или со прескокнување напред и назад помеѓу два јазли ${\displaystyle v_{i}}$ и ${\displaystyle v_{j}}$ каде ${\displaystyle {i,j}\neq g}$ .

Етимологија

Зборот „евристички“ влезе во употреба на почетокот на 19 век. Тоа е неправилно формирано од грчкиот збор хеурискеин, што значи „да се најде“.^[5]

Поврзано

• Алгоритам
• Конструктивен евристички
• Генетски алгоритам
• Евристика
• Евристичко рутирање
• Еуристичка проценка : Метод за идентификување на проблеми со употребливоста во корисничките интерфејси.
• Метаевристички : Методи за контрола и прилагодување на основните евристички алгоритми, обично со употреба на меморија и учење.
• Матевристика : Алгоритми за оптимизација направени со интероперација на техниките за метатеуристика и математичко програмирање (МП).
• Реактивно оптимизирање на пребарувањето: Методи со користење на принципи за машинско учење преку Интернет за самостојно прилагодување на евристиката
• Рекурзија (компјутерски науки)
• Макро (компјутерски науки)

Наводи

1. Pearl, Judea (1984). Heuristics: intelligent search strategies for computer problem solving. United States: Addison-Wesley Pub. Co., Inc., Reading, MA. стр. 3. OSTI 5127296.
2. Apter, Michael J. (1970). The Computer Simulation of Behaviour. London: Hutchinson & Co. стр. 83. ISBN 9781351021005.
3. Jon Louis Bentley (1982). Writing Efficient Programs. Prentice Hall. стр. 11.
4. Allen Newell and Herbert A. Simon (1976). „Computer Science as Empirical Inquiry: Symbols and Search“ (PDF). Comm. ACM. 19 (3): 113–126. doi:10.1145/360018.360022.
5. „Definition of heuristic in English“. Oxford University Press. Архивирано од изворникот на 23 October 2016. Посетено на 22 October 2016.