Эвристика (информатика)

редактировать

В информатике, искусственном интеллекте и математической оптимизации используется эвристика (от греч. Εὑρίσκω "I найти, обнаружить ") - это метод, разработанный для более быстрого решения проблемы, когда классические методы работают слишком медленно, или для поиска приближенного решения, когда классические методы не могут найти точное решение. Это достигается за счет торговли оптимальностью, полнотой, точностью или точностью для скорости. В каком-то смысле это можно считать ярлыком.

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

Содержание

  • 1 Определение и мотивация
  • 2 Компромисс
  • 3 Примеры
    • 3.1 Более простая задача
    • 3.2 Задача коммивояжера
    • 3.3 Поиск
    • 3.4 Ньюэлл и Саймон: гипотеза эвристического поиска
    • 3.5 Антивирусное программное обеспечение
  • 4 подводных камня
  • 5 Этимология
  • 6 См. Также
  • 7 Ссылки

Определение и мотивация

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

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

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

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

Компромисс

Компромиссные критерии для принятия решения об использовании эвристики для решения данной проблемы включают следующее:

  • Оптимальность: Когда существует несколько решений для данной проблемы, гарантирует ли эвристика, что будет найдено лучшее решение? Действительно ли необходимо найти лучшее решение?
  • Полнота: когда существует несколько решений для данной проблемы, может ли эвристика найти их все? Действительно ли нам нужны все решения? Многие эвристики предназначены только для поиска одного решения.
  • Точность и точность: может ли эвристика обеспечить доверительный интервал для предполагаемого решения? Является ли шкала ошибок в решении неоправданно большой?
  • Время выполнения: это самая известная эвристика для решения проблем такого типа? Некоторые эвристики сходятся быстрее других. Некоторые эвристики лишь ненамного быстрее классических методов.

В некоторых случаях может быть сложно решить, достаточно ли хорошее решение, найденное эвристикой, потому что теория, лежащая в основе эвристики, не очень продумана.

Примеры

Более простая задача

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

Задача коммивояжера

Пример аппроксимации описан Джоном Бентли для решения задачи коммивояжера (TSP):

  • " Учитывая список городов и расстояния между каждой парой городов, каков самый короткий маршрут, который проходит через каждый город и возвращается в исходный город? "

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

Поиск

Еще один пример эвристическое ускорение алгоритма происходит при определенных задачах поиска. Первоначально эвристика проверяет все возможности на каждом шаге, как и алгоритм поиска по всему пространству. Но он может остановить поиск в любой момент, если текущая возможность уже хуже, чем уже найденное лучшее решение. В таких задачах поиска можно использовать эвристику, чтобы вначале попробовать хорошие варианты, так что плохие пути могут быть устранены на раннем этапе (см. альфа-бета сокращение ). В случае алгоритмов поиска лучшего первого, таких как A * search, эвристика улучшает сходимость алгоритма, сохраняя при этом его правильность, пока эвристика допустима.

Ньюэлл и Саймон: гипотеза эвристического поиска

В своей благодарственной речи на Премию Тьюринга Аллен Ньюэлл и Герберт А. Саймон обсуждают эвристический поиск Гипотеза: физическая система символов будет многократно генерировать и изменять известные структуры символов, пока созданная структура не будет соответствовать структуре решения. Каждый следующий шаг зависит от шага перед ним, поэтому эвристический поиск изучает, какие пути использовать, а какие игнорировать, измеряя, насколько близок текущий шаг к решению. Следовательно, некоторые возможности никогда не будут созданы, поскольку они, по оценкам, с меньшей вероятностью завершат решение.

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

Антивирусное программное обеспечение

Антивирусное программное обеспечение часто использует эвристические правила для обнаружения вирусов и других форм вредоносного ПО. Эвристическое сканирование ищет код и / или модели поведения, общие для класса или семейства вирусов, с разными наборами правил для разных вирусов. Если обнаруживается, что файл или выполняемый процесс содержит совпадающие шаблоны кода и / или выполняет этот набор действий, то сканер делает вывод, что файл заражен. Самая продвинутая часть эвристического сканирования, основанного на поведении, заключается в том, что оно может работать против сильно рандомизированных самомодифицирующихся / мутирующих (полиморфных ) вирусов, которые нельзя надежно обнаружить с помощью более простых методов сканирования строк. Эвристическое сканирование может обнаружить будущие вирусы, не требуя, чтобы вирус сначала обнаруживался где-то еще, отправлялся разработчику антивирусного сканера, анализировался и предоставлялся пользователям сканера обновление обнаружения для сканера.

Ловушки

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

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

Статистический анализ может проводиться при использовании эвристики для оценки вероятности неверных результатов. Чтобы использовать эвристику для решения задачи поиска или задачи о ранце, необходимо проверить, является ли эвристика допустимой. Дана эвристическая функция h (vi, vg) {\ displaystyle h (v_ {i}, v_ {g})}h (v_ {i}, v_ {g}) , предназначенная для аппроксимации истинного оптимального расстояния d ⋆ (vi, vg) {\ displaystyle d ^ {\ star} (v_ {i}, v_ {g})}d ^ {\ star} (v_ {i}, v_ {g}) к целевому узлу vg {\ displaystyle v_ {g}}v_ {g} в ориентированном графе G {\ displaystyle G}G , содержащем n {\ displaystyle n}n всего узлов или вершин, помеченных v 0, v 1, ⋯, vn {\ displaystyle v_ {0}, v_ {1}, \ cdots, v_ {n}}v_ {0}, v_ {1}, \ cdots, v_ {n} , «допустимый» примерно означает, что эвристика занижает стоимость достижения цели или формально час (vi, vg) ≤ d ⋆ (vi, vg) {\ displaystyle h (v_ {i}, v_ {g}) \ leq d ^ {\ star} (v_ {i}, v_ {g})}h (v_ {i}, v_ {g}) \ leq d ^ {\ star} (v_ {i}, v_ { g}) для всех (vi, vg) {\ displaystyle (v_ {i}, v_ {g})}(v_ {i}, v_ {g}) где i, g ∈ [0, 1,..., n] {\ displaystyle {i, g} \ in [0,1,..., n]}{i, g} \ in [0,1,..., n] .

Если эвристика недопустима, она может никогда не найти цель, либо зайдя в тупик графа G {\ displaystyle G}G или переходом между двумя узлами vi {\ displaystyle v_ {i}}v_ {i} и vj { \ displaystyle v_ {j}}v_ {j} где i, j ≠ g {\ displaystyle {i, j} \ neq g}{ i, j} \ neq g .

Этимология

Искать эвристика в Викисловаре, бесплатном словаре.

Слово «эвристический» вошло в обиход в начале 19 века. Он образован неправильным образом от греческого слова heuriskein, что означает «найти».

См. Также

Ссылки

Последняя правка сделана 2021-05-23 10:51:49
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте