Эвристический алгоритм

Эвристический алгоритм (эвристика) — алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве практически значимых случаев.

Определение

Эвристический алгоритм — это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.

Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

Важно понимать, что эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:

• Она не гарантирует нахождение лучшего решения.
• Она не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).
• Она может дать неверное решение в некоторых случаях.

Применение

Эвристические алгоритмы широко применяются для решения задач высокой вычислительной сложности (задачи, принадлежащие классу NP), то есть вместо полного перебора вариантов, занимающего существенное время, а иногда технически невозможного, применяется значительно более быстрый, но недостаточно обоснованный теоретически алгоритм. В областях искусственного интеллекта, таких как распознавание образов, эвристические алгоритмы широко применяются также и по причине отсутствия общего решения поставленной задачи. Различные эвристические подходы применяются в антивирусных программах, компьютерных играх и т. д. Например, программы, играющие в шахматы, проводят середину игры, основываясь, преимущественно, на эвристических алгоритмах (в дебюте может использоваться база данных, в эндшпиле — таблицы Налимова, но в миттельшпиле часто количество возможных ходов исключает полный перебор, а точных алгоритмов правильной игры не существует).

По утверждению Judea Pearl, эвристические методы основаны на интеллектуальном поиске стратегий компьютерного решения проблемы с использованием нескольких альтернативных подходов.

Возможность (допустимость) использования эвристик для решения каждой конкретной задачи определяется соотношением затрат на решение задачи точным и эвристическим методами, ценой ошибки и статистическими параметрами эвристики. Кроме того, важным является наличие или отсутствие на выходе «фильтра здравого смысла» — оценки результата человеком.

Пример оценки эвристического решения

Рассмотрим умозрительный пример. Допустим, что имеется известный, но чрезвычайно сложный точный алгоритм решения задачи, и эвристика, которая требует в 1000 раз меньше затрат и чаще всего даёт приемлемое решение (пусть в 95 % случаев). Для простоты примем, что цена точного решения постоянна, как и цена ошибки.

Тогда в среднем решение эвристическим методом будет стоить $(T/1000+0.05*E)$, где T — цена точного решения, а E — цена ошибки. Средняя разница в цене решения точным и эвристическим методом $(T-T/1000-0,05*E)=(19,98*T-E)/20=0,999*T-E/20$, то есть эвристика в среднем оказывается выгоднее точного решения, если только цена ошибки не превышает двадцатикратную (!) цену точного решения.

Если же на выходе результат решения критически оценивается человеком, то ситуация становится ещё лучше: когда ошибка, выданная эвристикой, оказывается достаточно мала, чтобы человек её не заметил, цена этой ошибки обычно гораздо ниже, а серьёзные ошибки будут отсеяны «фильтром здравого смысла», следовательно, не нанесут существенного вреда.

См. также

• Эвристика
• Эвристическое обучение
• Эвристическое сканирование

Литература

• С.Гудман, С.Хидетниеми, Введение в разработку и анализ алгоритмов, М.:"Мир", 1981.
• А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман, Структуры данных и алгоритмы, М.,СПб.,Киев: «Вильямс», 2001.