Эвристика (информатика) - Heuristic (computer science)

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

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

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

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

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

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

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

Компромисс

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

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

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

Примеры

Более простая проблема

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

Проблема коммивояжера

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

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

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

Поиск

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

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

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

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

Антивирусная программа

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

Ловушки

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

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

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

Если эвристика недопустима, она может никогда не найти цель, либо зайдя в тупик графа, либо пропуская назад и вперед между двумя узлами и где .

Этимология

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

Смотрите также

использованная литература