Эвристический алгоритм эвристика алгоритм решения задачи включающий практический метод не являющийся гарантированно точн

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

Определение

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

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

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

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

Применение

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

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

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

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

Рассмотрим абстрактный пример. Допустим, что имеется известный, но чрезвычайно сложный точный алгоритм решения задачи, и эвристика, которая требует в 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$ , то есть эвристика в среднем оказывается выгоднее точного решения, если только цена ошибки не превышает двадцатикратную (!) цену точного решения.

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

См. также

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

Примечания

Pearl, Judea. Heuristics (неопр.). — Addison-Wesley Pub, 1984. — .

Литература

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

[1] Pearl, Judea. Heuristics (неопр.). — Addison-Wesley Pub, 1984. — .