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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править исходный текст]

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

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

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

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

Применение[править | править исходный текст]

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

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

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

Пример оценки эвристического решения[править | править исходный текст]

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

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Pearl Judea Heuristics. — Addison-Wesley Pub. — ISBN 0201055945

Литература[править | править исходный текст]