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

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

Определение

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

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

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

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

Применение

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

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

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

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

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

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

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

См. также

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

Литература

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

Отрывок, характеризующий Эвристический алгоритм

В 1808 году император Александр ездил в Эрфурт для нового свидания с императором Наполеоном, и в высшем Петербургском обществе много говорили о величии этого торжественного свидания.
В 1809 году близость двух властелинов мира, как называли Наполеона и Александра, дошла до того, что, когда Наполеон объявил в этом году войну Австрии, то русский корпус выступил за границу для содействия своему прежнему врагу Бонапарте против прежнего союзника, австрийского императора; до того, что в высшем свете говорили о возможности брака между Наполеоном и одной из сестер императора Александра. Но, кроме внешних политических соображений, в это время внимание русского общества с особенной живостью обращено было на внутренние преобразования, которые были производимы в это время во всех частях государственного управления.
Жизнь между тем, настоящая жизнь людей с своими существенными интересами здоровья, болезни, труда, отдыха, с своими интересами мысли, науки, поэзии, музыки, любви, дружбы, ненависти, страстей, шла как и всегда независимо и вне политической близости или вражды с Наполеоном Бонапарте, и вне всех возможных преобразований.
Князь Андрей безвыездно прожил два года в деревне. Все те предприятия по именьям, которые затеял у себя Пьер и не довел ни до какого результата, беспрестанно переходя от одного дела к другому, все эти предприятия, без выказыванья их кому бы то ни было и без заметного труда, были исполнены князем Андреем.
Он имел в высшей степени ту недостававшую Пьеру практическую цепкость, которая без размахов и усилий с его стороны давала движение делу.
Одно именье его в триста душ крестьян было перечислено в вольные хлебопашцы (это был один из первых примеров в России), в других барщина заменена оброком. В Богучарово была выписана на его счет ученая бабка для помощи родильницам, и священник за жалованье обучал детей крестьянских и дворовых грамоте.
Одну половину времени князь Андрей проводил в Лысых Горах с отцом и сыном, который был еще у нянек; другую половину времени в богучаровской обители, как называл отец его деревню. Несмотря на выказанное им Пьеру равнодушие ко всем внешним событиям мира, он усердно следил за ними, получал много книг, и к удивлению своему замечал, когда к нему или к отцу его приезжали люди свежие из Петербурга, из самого водоворота жизни, что эти люди, в знании всего совершающегося во внешней и внутренней политике, далеко отстали от него, сидящего безвыездно в деревне.
Кроме занятий по именьям, кроме общих занятий чтением самых разнообразных книг, князь Андрей занимался в это время критическим разбором наших двух последних несчастных кампаний и составлением проекта об изменении наших военных уставов и постановлений.
Весною 1809 года, князь Андрей поехал в рязанские именья своего сына, которого он был опекуном.
Пригреваемый весенним солнцем, он сидел в коляске, поглядывая на первую траву, первые листья березы и первые клубы белых весенних облаков, разбегавшихся по яркой синеве неба. Он ни о чем не думал, а весело и бессмысленно смотрел по сторонам.
Проехали перевоз, на котором он год тому назад говорил с Пьером. Проехали грязную деревню, гумны, зеленя, спуск, с оставшимся снегом у моста, подъём по размытой глине, полосы жнивья и зеленеющего кое где кустарника и въехали в березовый лес по обеим сторонам дороги. В лесу было почти жарко, ветру не слышно было. Береза вся обсеянная зелеными клейкими листьями, не шевелилась и из под прошлогодних листьев, поднимая их, вылезала зеленея первая трава и лиловые цветы. Рассыпанные кое где по березнику мелкие ели своей грубой вечной зеленью неприятно напоминали о зиме. Лошади зафыркали, въехав в лес и виднее запотели.
Лакей Петр что то сказал кучеру, кучер утвердительно ответил. Но видно Петру мало было сочувствования кучера: он повернулся на козлах к барину.
– Ваше сиятельство, лёгко как! – сказал он, почтительно улыбаясь.
– Что!
– Лёгко, ваше сиятельство.
«Что он говорит?» подумал князь Андрей. «Да, об весне верно, подумал он, оглядываясь по сторонам. И то зелено всё уже… как скоро! И береза, и черемуха, и ольха уж начинает… А дуб и не заметно. Да, вот он, дуб».
На краю дороги стоял дуб. Вероятно в десять раз старше берез, составлявших лес, он был в десять раз толще и в два раза выше каждой березы. Это был огромный в два обхвата дуб с обломанными, давно видно, суками и с обломанной корой, заросшей старыми болячками. С огромными своими неуклюжими, несимметрично растопыренными, корявыми руками и пальцами, он старым, сердитым и презрительным уродом стоял между улыбающимися березами. Только он один не хотел подчиняться обаянию весны и не хотел видеть ни весны, ни солнца.