В інформатиці евристичний алгоритм або просто евристика це алгоритм спроможний видати прийнятне рішення проблеми серед б

В інформатиці евристичний алгоритм, або просто евристика — це алгоритм, спроможний видати прийнятне рішення проблеми серед багатьох рішень, але неспроможний гарантувати, що це рішення буде найкращим. Отже, такі алгоритми є приблизними і неточними. Зазвичай такі алгоритми знаходять рішення, близьке до найкращого і роблять це швидко. Іноді такий алгоритм може бути точним, тобто він знаходить дійсно найкраще рішення, але він все одно буде називатися евристичним доти, доки не буде доведено, що рішення дійсно найкраще. Один з найвідоміших — жадібний алгоритм. (для того, щоб бути простим і швидким, цей алгоритм ігнорує деякі вимоги задачі).

Дві фундаментальні цілі в інформатиці — знаходження алгоритмів з імовірно найкращим часом виконання та з хорошою або оптимальною якістю. Евристичний алгоритм відмовляється від однієї або обох цих цілей; наприклад, він зазвичай знаходить дуже хороше рішення, але немає доказів, що рішення насправді не є поганим; або працює досить швидко, але не має гарантії, що він завжди видасть рішення.

Декілька евристичних методів використовуються антивірусним ПЗ для виявлення вірусів та іншого шкідливого ПЗ.

Часто можна знайти таку задачу, в якій евристичний алгоритм буде працювати або дуже довго, або видавати невірні результати. Однак, такі парадоксальні приклади можуть ніколи не зустрітись на практиці через свою специфічну структуру. Таким чином, використання евристики дуже поширене в реальному світі. Для багатьох практичних проблем евристичні алгоритми, можливо, єдиний шлях для отримання задовільного рішення в прийнятний проміжок часу. Існує клас евристичних стратегій, названих метаалгоритмами, котрі часто використовують — наприклад, випадковий пошук. Такі алгоритми можуть бути застосовані до широкого кола завдань, при цьому хороші характеристики не гарантуються.

Див. також

Джерела

S. E. Goodman, S. T. Hedetniemi, Introduction to the Design and Analysis of Algorithms, McGraw-Hill, 1977.
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, Data Structures and Algorithms, Addison-Wesley.

Посилання

— евристичний аналіз граматики будь-якої мови від Сергія Горелова.