Евристика

Фон

Евристиката е изкуството да се намери адекватно решение на даден проблем, като се използват ограничени знания и малко време. По-формално евристиката се основава на опита; тя може да ускори търсенето на решение, като използва прости правила. Пълното търсене може да отнеме твърде много време или да е твърде трудно за изпълнение.

По-точно казано, евристиките са стратегии, използващи лесно достъпна, макар и слабо приложима информация, за да контролират решаването на проблеми при хората и машините.

Евристиката може да се използва в някои области на науката, но не и в други: В икономиката решение с грешка от един процент често е приемливо; телескоп с грешка от един градус вероятно е неизползваем, ако е насочен към далечен обект. Същият телескоп, насочен към прозореца от другата страна на улицата, вероятно ще допусне тази грешка; пропускът от един градус няма да окаже голямо влияние на малко разстояние.

Евристиката може да се използва за оценка на отговора, който след това се изяснява чрез изпълнение на точното решение в много малък мащаб, може би за да се спести време, пари или труд по даден проект - например евристично предположение за това колко тегло се очаква да носи един мост може да се използва, за да се определи дали мостът трябва да бъде направен от дърво, камък или стомана, и да се закупят подходящи количества от необходимия материал, докато се завърши точният проект на моста.

Въпреки това използването на евристики в някои много технически области може да бъде вредно - пример за това е информатиката. Програмирането на компютър да извършва повече или по-малко желаните действия може да доведе до сериозни грешки. Ето защо компютърните задачи по принцип трябва да са доста точни. Въпреки това има някои области, в които компютрите могат безопасно да изчисляват евристични решения - например технологията за търсене на Google разчита в голяма степен на евристиката, като създава "почти липсващи" съвпадения на заявката за търсене, когато не може да се намери точно съвпадение. Това дава възможност на потребителя да коригира евентуални грешки, допуснати при търсенето. Пример: При търсене на името "Питър Смит" и невъзможност да се намери точното име, търсачката евристично съвпада с "Пит Смит", а лицето, което използва търсачката, трябва да реши дали Пит и Питър са едно и също лице.

Примери

Polya

Ето и някои други често използвани евристики от книгата на Поля от 1945 г. "Как да го решим":

• Ако ви е трудно да разберете даден проблем, опитайте се да нарисувате картина.
• Ако не можете да намерите решение, опитайте се да предположите, че имате решение, и да видите какво можете да извлечете от него ("работа в обратна посока").
• Ако проблемът е абстрактен, опитайте се да разгледате конкретен пример.
• Опитайте първо да решите по-общ проблем: "парадоксът на изобретателя": по-амбициозният план може да има повече шансове за успех.

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

Един от примерите, в които евристиката е полезна, е проблемът с опаковането. Задачата се състои в опаковане на определен брой предмети. Съществуват правила, които трябва да се спазват. Например, всеки елемент има стойност и тегло. Сега проблемът е да се съберат най-ценните предмети с възможно най-малко тегло. Друг пример е поставянето на редица различни по размер предмети в ограничено пространство, като багажника на автомобил.

За да се получи идеалното решение на проблема, трябва да се изпробват всички възможности. Това често не е добър вариант, тъй като изпробването им отнема много време и средно половината от възможностите трябва да се изпробват, докато се намери решение. Така че това, което повечето хора правят, е да започнат с най-големия елемент, да го поберат и след това да се опитат да подредят другите елементи около него. Това ще даде добро решение в повечето случаи. Има случаи обаче, когато такова решение е много лошо и трябва да се използва друга техника.

Следователно това е евристично решение.

Пример за задача за опаковане. Това е едноизмерна (с ограничения) задача за раница: кои кутии трябва да се изберат, за да се максимизира сумата на парите и да се запази общото тегло под 15 kg? При многоизмерен проблем може да се вземе предвид плътността или размерите на кутиите, като последният е типичен проблем за опаковане. (Решението в този случай е да се изберат всички кутии освен зелената.)