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

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

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

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

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

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

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

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

Компромисс [ править ]

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

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

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

Примеры [ править ]

Более простая проблема [ править ]

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

Проблема коммивояжера [ править ]

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

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

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

Искать [ редактировать ]

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

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

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

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

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

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

Ловушки [ править ]

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

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

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

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

Этимология [ править ]

Поищите эвристику в Викисловаре, бесплатном словаре.

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

См. Также [ править ]

• Алгоритм
• Конструктивная эвристика
• Генетический алгоритм
• Эвристический
• Эвристическая маршрутизация
• Эвристическая оценка : метод выявления проблем удобства использования в пользовательских интерфейсах.
• Метаэвристика : методы управления и настройки основных эвристических алгоритмов, обычно с использованием памяти и обучения.
• Матевристика : алгоритмы оптимизации, созданные на основе взаимодействия методов метаэвристики и математического программирования (МП).
• Реактивная поисковая оптимизация: методы, использующие принципы онлайн- машинного обучения для самонастройки эвристики.
• Рекурсия (информатика)
• Макро (информатика)

Ссылки [ править ]