Эвристика что это информатика

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

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

Содержание

Определение

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

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

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

Применение

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

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

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

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

Тогда в среднем решение эвристическим методом будет стоить , где T — цена точного решения, а E — цена ошибки. Средняя разница в цене решения точным и эвристическим методом , то есть эвристика в среднем оказывается выгоднее точного решения, если только цена ошибки не превышает двадцатикратную (!) цену точного решения.

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

Источник

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

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

СОДЕРЖАНИЕ

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

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

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

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

Компромисс

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

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

Примеры

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

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

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

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

Поиск

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

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

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

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

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

Ловушки

Этимология

Источник

Грязное программирование с чистой душой: разработка эвристических систем (часть 2)

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

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

Резиновые перчатки

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

• Система тестирования. Нужна для интегрального исследования поведения программы, а также для выявления скрытых закономерностей. В идеале она должна позволять чувствовать происходящее на кончиках пальцев. Хорошо, если система снабжена набором метрик для выявления разнообразных аспектов поведения исследуемой программы. Готовьтесь потратить серьезные ресурсы на написание и развитие системы тестирования, а также на подготовку и расширение эталонных баз. Используйте систему тестирования при каждом изменении программы.

• Система логирования. Нужна, чтобы быстро и удобно понять тонкости работы программы и взаимодействия эвристик в данном конкретном случае. В зависимости от решаемой задачи система логирования может иметь разный вид, но стоит ожидать, что это будет нечто большее, чем дамп в текстовый файл. Позаботьтесь о своем удобстве, ибо с разбором полетов вам придется иметь дело часто.

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

• Общение с коллегами. Уведомляйте их о внесенных вами изменениях в программе и о том, на какие аспекты они могут повлиять.

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

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

Разделение ответственности

В эвристическом программировании неизбежна ситуация адаптации одних компонент к нежелательным особенностям работы других, притирки компонент друг под друга. Пусть имеется два компонента A и B, косвенно влияющие друг на друга. Пусть при некотором изменении компонента A компонент B начинает работать в новых условиях, в которых дефекты его работы проявляются сильнее. Как итог, изменение может оказаться неприемлемым, даже если оно улучшает A (вспомним пример с классификатором из первой части статьи). Разумеется, в данном случае следует внести изменения в B, чтобы этот компонент стал лучше работать в новых условиях — но мы живём в реальном мире, где у большинства задач есть сроки исполнения, при превышении которых прибегает PM в не очень добром настроении. В итоге в A вносятся только такие изменения, при которых дефекты B не проявляются. А начинает неявно приспосабливаться к шероховатостям и неровностям B. После этого дефекты B станет нелегко исправить: A уже адаптирован к неприятным особенностям B, и изменение статус-кво нарушит его работу. Если надо создать компонент C, непосредственно использующий B, то может оказаться проще написать C, в явном виде учитывающим ошибки B и исправляющим их самостоятельно, чем править строптивый B. Появилась новая зависимость, и теперь шансы на улучшение B стали совсем призрачными. Щедрой рукой пририсуем к картине компоненты D, E и так далее, а также вспомним об их взаимодействиях друг с другом. Легко прийти к ситуации, когда любое изменение в системе оказывается вредным.

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

Глубокое проникновение

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

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

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

Распутываем связи

«Разделяй и властвуй» — один из мощных принципов управления любой сложной системой. Иметь компактную, но сильно связную систему гораздо хуже, чем иметь систему более громоздкую и объемную, но зато с охватываемым воображением взаимодействиями. Необходимое зло при распутывании клубка связей — раздувание системы, увеличение количества кода.

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

Один раз не копипаст

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

Вспомним, что компоненты в грязном программировании имеют нечеткую область ответственности, и что любые зависимости стремятся эту область деформировать. Допустим, есть компонент A, которым пользуются компоненты B и C. Может оказаться, что B и C будут склонны «тянуть» А в разные стороны (каждому из двух компонентов нужно от A что-то свое). Чтобы А выдержал нагрузку, необходимо будет его усложнять (например, вводить дополнительные параметры). В итоге усложнение может оказаться менее приемлемым решением, чем простое копирование кода А и превращение его в компоненты A_для_B и A_для_С. (Между прочим, копирование является одним из основных творческих инструментов эволюции. Часто сначала ген просто случайно дублируется, а затем одна из его копий приспосабливается под новые задачи.)

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

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

Любовь к частным случаям

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

Допустим, нужно разработать модуль поиска на изображении определенного вида картинок. Многие из самых изощренных и бесчеловечных серийных маньяков с детства отличались патологической склонностью к жестоким издевательствам над животными. Этот факт не имеет отношения к теме статьи — я просто хотел убедиться, что вы не заснули. Итак, допустим, нужно разработать модуль поиска на изображении определенного вида картинок. Изначально предполагается, что картинки могут иметь произвольную форму. Поэтому писать решение, не предъявляющее требований к форме картинок, придется. Тем не менее, идея реализовать совместно с этим модулем еще и модуль поиска только прямоугольных картинок может оказаться вполне продуктивной (несмотря на то, что общее решение призвано находить и прямоугольные картинки тоже). Причины тому следующие. Во-первых, в реальных изображениях доля прямоугольных картинок весьма представительна. Во-вторых, модуль поиска прямоугольных картинок может оказаться написать намного легче, и можно рассчитывать на увеличение качества работы по сравнению с общим решением. Менее очевидна третья причина. Если отдельно обработать наиболее важный, но и простой случай, серьезно снизится нагрузка на основной модуль. После некоторой эволюции этот модуль, возможно, будет в среднем хуже искать прямоугольные картинки, чем делал бы это, развиваясь в одиночку. Зато стоит ожидать лучшего качества работы в нетривиальных случаях.

Зоопарк решений

Один из принципов философии Python звучит так: «должен существовать один — и, желательно, только один — очевидный способ сделать это». В грязном программировании нормальной является ситуация, когда одну и ту же задачу решают несколькими способами, причем одновременно.

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

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

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

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

Источник