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

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

Определение

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

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

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

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

Применение

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

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

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

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

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

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

См. также

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

Примечания

Литература

• Алферов В. И., Бурков В. Н., Кравцов А. Е., Карпов Ю. А. Эвристические алгоритмы распределения ресурсов // Вестник Воронежского государственного технического университета. — 2009. — № 12. — С. 176-179
• Ахо, Альфред В. Структуры данных и алгоритмы [Текст] / Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман ; [пер. с англ. и ред. А. А. Минько]. — Москва [и др.] : Вильямс, 2010 (Санкт-Петербург : Печатный двор им. А. М. Горького). — 391 с. : ил.; 23 см.
• Белова, Т. Б. Информационная эвристика : Учебное пособие для бакалавров / Т. Б. Белова, М. Н. Михин. — Москва : Ай Пи Ар Медиа, 2023. — 91 с.
• Володин, А. Ю. Персональные базы знаний и актуальные вопросы интернет-эвристики / А. Ю. Володин // Информационный бюллетень ассоциации История и компьютер. — 2013. — № 40. — С. 51-57.
• Гудман, С. Введение в разработку и анализ алгоритмов / С. Гудман, С. Хидетниеми. — М. : Мир, 1981. — 366 с.
• Лейбин, В. М. Психоаналитическая эвристика и терапия: проблемы и противоречия / В. М. Лейбин // Вопросы философии. — 2007. — № 3. — С. 130-141.
• Обнаружение и оценка экстремальных особенностей пространства поиска эвристическими алгоритмами / Р. А. Нейдорф, И. В. Черногоров, О. Т. Ярахмедов, В. В. Полях // Наукоемкие технологии в космических исследованиях Земли. — 2016. — Т. 8, № 2. — С. 16-25.
• Попов, А. В. Истории Русской Православной Церкви и архивная эвристика / А. В. Попов // Макарьевские чтения : Материалы XVI международной научно-практической конференции, Горно-Алтайск, 23–24 сентября 2021 года / Редакционная коллегия: ответственный редактор: Бабин В.Г., технический редактор: Куликов Ф.И., члены редакционной коллегии: Алексеева А.А., Федосова Т.В. — Горно-Алтайск: Горно-Алтайский государственный университет, 2021. — С. 230-244.
• Попов, А. В. Архивная эвристика и алгоритм поиска документов по истории Русской Православной Церкви и теологии в отечественных архивах // Теология и образование — 2024. Ежегодник Научно-образовательной теологической ассоциации. — М.: Изд-во РАНХиГС, 2024. — С. 308-332.
• Рязанцева, Е. А. Эвристические алгоритмы поиска / Е. А. Рязанцева, Н. В. Гаврилов // Пути инновационного развития науки и образования в современных условиях : Сборник научных трудов. — Миасс : ООО "Издательство Аниго", 2023. — С. 148-151.
• Чеботарев, С. В. Об эвристических алгоритмах: комбинирование правил предпочтения / С. В. Чеботарев // Вестник Барнаульского государственного педагогического университета. — 2006. — № 6-2. — С. 77-82.
• Эвристические алгоритмы и распределенные вычисления в прикладных задачах [Текст] : коллективная монография / [П. И. Аверин и др.] ; под ред. Б. Ф. Мельникова ; М-во образования и науки Российской Федерации, Федеральное гос. бюджетное образовательное учреждение высш. проф. образования "Тольяттинский гос. ун-т". — Тольятти : ФГБОУ ВПО "ТГУ", 2012. — 329 с. : ил.