Материал из РУВИКИ — свободной энциклопедии

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда в среднем решение эвристическим методом будет стоить , где T — цена точного решения, а E — цена ошибки. Средняя разница в цене решения точным и эвристическим методом , то есть эвристика в среднем оказывается выгоднее точного решения, если только цена ошибки не превышает двадцатикратную (!) цену точного решения.

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

См. также[править | править код]

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

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

Литература[править | править код]