В информатике, искусственном интеллекте и математической оптимизации используется эвристика (от греч. Εὑρίσκω "I найти, обнаружить ") - это метод, разработанный для более быстрого решения проблемы, когда классические методы работают слишком медленно, или для поиска приближенного решения, когда классические методы не могут найти точное решение. Это достигается за счет торговли оптимальностью, полнотой, точностью или точностью для скорости. В каком-то смысле это можно считать ярлыком.
A эвристическая функция, также называемая просто эвристикой, представляет собой функцию , которая ранжирует альтернативы в алгоритмах поиска на каждом шаге ветвления на основе доступной информации чтобы решить, за какой веткой следовать. Например, это может приблизительно соответствовать точному решению.
Цель эвристики - дать решение в разумные сроки, достаточные для решения возникшей проблемы. Это решение может быть не лучшим из всех решений этой проблемы или может просто приближаться к точному решению. Но он по-прежнему ценен, потому что на его поиск не требуется чрезмерно много времени.
Эвристические методы могут давать результаты сами по себе или они могут использоваться вместе с алгоритмами оптимизации для повышения их эффективности (например, они могут использоваться для генерации хороших начальных значений).
Результаты о NP-твердости в теоретической информатике делают эвристику единственным жизнеспособным вариантом для множества сложных задач оптимизации, которые необходимо регулярно решать в реальных приложениях.
Эвристика лежит в основе всей области искусственного интеллекта и компьютерного моделирования мышления, поскольку они могут использоваться в ситуациях, когда отсутствуют известные алгоритмы.
Компромиссные критерии для принятия решения об использовании эвристики для решения данной проблемы включают следующее:
В некоторых случаях может быть сложно решить, достаточно ли хорошее решение, найденное эвристикой, потому что теория, лежащая в основе эвристики, не очень продумана.
Один из способов достижения ожидаемого повышения вычислительной производительности эвристики состоит в решении более простой проблемы, решение которой также является решением исходной проблемы.
Пример аппроксимации описан Джоном Бентли для решения задачи коммивояжера (TSP):
, чтобы выбрать порядок рисования с помощью перьевого плоттера . TSP известен как NP-Hard, поэтому трудно найти оптимальное решение даже для проблемы среднего размера. Вместо этого можно использовать жадный алгоритм, чтобы дать хорошее, но не оптимальное решение (это приближение к оптимальному ответу) за достаточно короткий промежуток времени. Эвристика жадного алгоритма говорит, что нужно выбрать то, что в настоящее время является лучшим следующим шагом, независимо от того, предотвращает ли это (или даже делает невозможным) хорошие шаги в дальнейшем. Это эвристика в том смысле, что практика говорит, что это достаточно хорошее решение, теория говорит, что есть лучшие решения (и даже может сказать, насколько лучше в некоторых случаях).
Еще один пример эвристическое ускорение алгоритма происходит при определенных задачах поиска. Первоначально эвристика проверяет все возможности на каждом шаге, как и алгоритм поиска по всему пространству. Но он может остановить поиск в любой момент, если текущая возможность уже хуже, чем уже найденное лучшее решение. В таких задачах поиска можно использовать эвристику, чтобы вначале попробовать хорошие варианты, так что плохие пути могут быть устранены на раннем этапе (см. альфа-бета сокращение ). В случае алгоритмов поиска лучшего первого, таких как A * search, эвристика улучшает сходимость алгоритма, сохраняя при этом его правильность, пока эвристика допустима.
В своей благодарственной речи на Премию Тьюринга Аллен Ньюэлл и Герберт А. Саймон обсуждают эвристический поиск Гипотеза: физическая система символов будет многократно генерировать и изменять известные структуры символов, пока созданная структура не будет соответствовать структуре решения. Каждый следующий шаг зависит от шага перед ним, поэтому эвристический поиск изучает, какие пути использовать, а какие игнорировать, измеряя, насколько близок текущий шаг к решению. Следовательно, некоторые возможности никогда не будут созданы, поскольку они, по оценкам, с меньшей вероятностью завершат решение.
Эвристический метод может выполнять свою задачу, используя деревья поиска. Однако вместо того, чтобы генерировать все возможные ветви решения, эвристика выбирает ветви с большей вероятностью, чем другие ветви. Он является выборочным в каждой точке принятия решения, выбирая ветви, которые с большей вероятностью будут производить решения.
Антивирусное программное обеспечение часто использует эвристические правила для обнаружения вирусов и других форм вредоносного ПО. Эвристическое сканирование ищет код и / или модели поведения, общие для класса или семейства вирусов, с разными наборами правил для разных вирусов. Если обнаруживается, что файл или выполняемый процесс содержит совпадающие шаблоны кода и / или выполняет этот набор действий, то сканер делает вывод, что файл заражен. Самая продвинутая часть эвристического сканирования, основанного на поведении, заключается в том, что оно может работать против сильно рандомизированных самомодифицирующихся / мутирующих (полиморфных ) вирусов, которые нельзя надежно обнаружить с помощью более простых методов сканирования строк. Эвристическое сканирование может обнаружить будущие вирусы, не требуя, чтобы вирус сначала обнаруживался где-то еще, отправлялся разработчику антивирусного сканера, анализировался и предоставлялся пользователям сканера обновление обнаружения для сканера.
У некоторых эвристик есть сильная теория; они либо выводятся сверху вниз из теории, либо получаются на основе экспериментальных или реальных данных. Другие - это всего лишь практические правила, основанные на наблюдениях или опыте реального мира, даже без проблеска теории. Последние подвержены большему количеству подводных камней.
Когда эвристика повторно используется в различных контекстах, поскольку было замечено, что она «работает» в одном контексте, без математического доказательства соответствия заданному набору требований, возможно, что текущий набор данных не обязательно представляют будущие наборы данных (см.: переоснащение ), и предполагаемые "решения" оказываются сродни шуму.
Статистический анализ может проводиться при использовании эвристики для оценки вероятности неверных результатов. Чтобы использовать эвристику для решения задачи поиска или задачи о ранце, необходимо проверить, является ли эвристика допустимой. Дана эвристическая функция , предназначенная для аппроксимации истинного оптимального расстояния к целевому узлу в ориентированном графе , содержащем всего узлов или вершин, помеченных , «допустимый» примерно означает, что эвристика занижает стоимость достижения цели или формально для всех где .
Если эвристика недопустима, она может никогда не найти цель, либо зайдя в тупик графа или переходом между двумя узлами и где .
Искать эвристика в Викисловаре, бесплатном словаре. |
Слово «эвристический» вошло в обиход в начале 19 века. Он образован неправильным образом от греческого слова heuriskein, что означает «найти».