Что такое эвристический алгоритм
Эвристический алгоритм
Эвристический алгоритм (эвристика) — алгоритм решения задачи, не имеющий строгого обоснования, но, тем не менее, дающий приемлемое решение задачи в большинстве практически значимых случаев.
Содержание
Определение
Эвристический алгоритм — это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.
Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.
Важно понимать, что эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:
Применение
Эвристические алгоритмы широко применяются для решения задач высокой вычислительной сложности (задачи, принадлежащие классу NP), то есть вместо полного перебора вариантов, занимающего существенное время, а иногда технически невозможного, применяется значительно более быстрый, но недостаточно обоснованный теоретически, алгоритм. В областях искусственного интеллекта, таких, как распознавание образов, эвристические алгоритмы широко применяются также и по причине отсутствия общего решения поставленной задачи. Различные эвристические подходы применяются в антивирусных программах, компьютерных играх и т. д. Например, программы, играющие в шахматы, проводят середину игры, основываясь, преимущественно, на эвристических алгоритмах (в дебюте может использоваться база данных, в эндшпиле — таблицы Налимова, но в миттельшпиле часто количество возможных ходов исключает полный перебор, а точных алгоритмов правильной игры не существует).
Возможность (допустимость) использования эвристик для решения каждой конкретной задачи определяется соотношением затраты на решение задачи точным и эвристическим методом, ценой ошибки и статистическими параметрами эвристики. Кроме того, важным является наличие или отсутствие на выходе «фильтра здравого смысла» — оценки результата человеком.
Пример оценки эвристического решения
Рассмотрим умозрительный пример. Допустим, что имеется известный, но чрезвычайно сложный точный алгоритм решения задачи, и эвристика, которая требует в 1000 раз меньше затрат и чаще всего даёт приемлемое решение (пусть в 95 % случаев). Для простоты примем, что цена точного решения постоянна, как и цена ошибки.
Тогда в среднем решение эвристическим методом будет стоить 
, где T — цена точного решения, а E — цена ошибки. Средняя разница в цене решения точным и эвристическим методом 
, то есть эвристика в среднем оказывается выгоднее точного решения, если только цена ошибки не превышает двадцатикратную (!) цену точного решения.
Если же на выходе результат решения критически оценивается человеком, то ситуация становится ещё лучше: когда ошибка, выданная эвристикой, оказывается достаточно мала, чтобы человек её не заметил, цена этой ошибки обычно гораздо ниже, а серьёзные ошибки будут отсеяны «фильтром здравого смысла», следовательно, не нанесут существенного вреда.
Эвристика: что это простыми словами, методы эвристики
Как человек решает свои проблемы? В большинстве случаев, он выбирает между возможными альтернативами. Если говорить более научным языком, человек использует метод полного ненаправленного перебора возможных альтернатив. Это предполагает огромное количество вариантов исхода событий. Анализ каждого варианта может занять приличное время, а это один из самых дорогих ресурсов. В любой сфере жизнедеятельности человека может возникнуть ситуация, когда необходимо принять решение в условиях ограниченного времени. Именно тогда, на помощь приходит эвристика.
Что такое эвристика?
Эвристика (от др.греч. «εὑρίσκω» (heuristiko) — находить и открывать) – это научная область, которая изучает и анализирует созидательную деятельность человека, то есть умение приносить подлинную пользу: материальную, моральную, техническую и другое. Эвристика представляет собой симбиоз из элементов психологии, математики, философии, физики, теории об искусственном интеллекте, лингвистики структурного типа и теории информации. Эвристику можно трактовать по-разному, в зависимости от области её применения. В общем понимании слова –
В разных изданиях можно встретить разные трактовки термина «эвристика», вот, к примеру:
Для понимания самой сути эвристики можно привести пример из общеобразовательной школьной программы. Например, в случае, когда ученику необходимо объяснить суть теоремы Пифагора, на доске он должен начертить прямоугольный треугольник. Таким образом наглядным становится соотношение между сторонами конкретной геометрической фигуры. Иными словами, чертёж является средством, которое облегчает ученику путь к решению. В это и заключается суть эвристических методов. Если при решении алгебраических задач, ученик будет руководствоваться решениями похожих задач, это так же будет считаться эвристическим методом. Говоря простыми словами, эвристика помогает сократить поиск, отсеяв всю информационную шелуху. Следствием этого, может стать новое видение для решения поставленной задачи.
Методы эвристики
Любой метод – это инструмент для получения каких-либо знаний, или решения каких-либо задач. Эвристика сама по себе уже является «оружием» для расширения рамок сознания. В условиях неполноценной информации и четкого плана для решения проблемы, эвристические методы позволяют использовать различные логические приёмы и методики. Симбиоз научных исследований и изобретательного творчества позволяют достичь поставленной цели.
Учитывая тот факт, что эвристика – это молодая наука, она пока лишена многих фундаментальных понятий. К примеру, это проявляется по отношению определения эвристического метода. Однако, несмотря на некоторые «погрешности», существуют методы, которые во многом могут помочь современному человеку выстроить правильный алгоритм действий при решении личных, или профессиональных проблем. Вот самые яркие примеры эвристических методов:
История развития эвристики
Отцом-основателем самой сути эвристики считают Сократа. Он имел особенный подход при обучении своих последователей. Для того, чтобы человек смог познать суть предмета, или явления, великий философ использовал наводящие вопросы. Это позволяло ученику выстроить логическую цепочку, и в правильной последовательности «осознать» суть вещи. Подобные диалоги назывались «сократическими беседами» именно они по мнению многих легли в основу эвристических методов.
Метод Сократа неоднократно был описан и развит в трудах многих известных деятелей. В числе таких: Архимед, Г. Галилей, Ф. Бекон и другие. Эвристику с педагогической точки зрения, рассматривали в своих трудах Ж.-Ж Руссо и Л. Н. Толстой. Оба автора пришли к выводу, что ребёнок должен познавать новое, через призму собственного опыта. При этом, ученик должен иметь свободу выбора при решении поставленных задач. Такой же точки зрения придерживались С. Френе, С. Т. Шацкий, П. Ф. Каптерев и другие.
Новый толчок развития эвристика получила в прошлом столетии, этому способствовало изобретение электронной вычислительной машины. Создание ЭВМ способствовало упрощению и ускорению поиска правильного решения, ведь компьютер, на основе полученных от программиста моделей и алгоритмов, мог подобрать правильный ответ.
Заключение
Эвристика – это древнегреческая философия, призванная познавать каждое явление и предмет, которая упакована в современные технологии и термины. Эвристические методы, несмотря на свою «незрелость» во многом способны облегчить жизнь людям разных возрастов и профессий, меняя при этом привычные рамки их мышления.
Эвристический алгоритм
Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи. Позволяет ускорить решение задачи в тех случаях, когда точное решение не может быть найдено.
Содержание
Определение
Эвристический алгоритм — это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.
Проще говоря, эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.
Важно понимать, что эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:
Применение
Эвристические алгоритмы широко применяются для решения задач высокой вычислительной сложности (задачи, принадлежащие классу NP), то есть вместо полного перебора вариантов, занимающего существенное время, а иногда технически невозможного, применяется значительно более быстрый, но недостаточно обоснованный теоретически алгоритм. В областях искусственного интеллекта, таких как распознавание образов, эвристические алгоритмы широко применяются также и по причине отсутствия общего решения поставленной задачи. Различные эвристические подходы применяются в антивирусных программах, компьютерных играх и т. д. Например, программы, играющие в шахматы, проводят середину игры, основываясь, преимущественно, на эвристических алгоритмах (в дебюте может использоваться база данных, в эндшпиле — таблицы Налимова, но в миттельшпиле часто количество возможных ходов исключает полный перебор, а точных алгоритмов правильной игры долгое время не существовало).
Возможность (допустимость) использования эвристик для решения каждой конкретной задачи определяется соотношением затрат на решение задачи точным и эвристическим методами, ценой ошибки и статистическими параметрами эвристики. Кроме того, важным является наличие или отсутствие на выходе «фильтра здравого смысла» — оценки результата человеком.
Пример оценки эвристического решения
Рассмотрим умозрительный пример. Допустим, что имеется известный, но чрезвычайно сложный точный алгоритм решения задачи, и эвристика, которая требует в 1000 раз меньше затрат и чаще всего даёт приемлемое решение (пусть в 95 % случаев). Для простоты примем, что цена точного решения постоянна, как и цена ошибки.
Если же на выходе результат решения критически оценивается человеком, то ситуация становится ещё лучше: когда ошибка, выданная эвристикой, оказывается достаточно мала, чтобы человек её не заметил, цена этой ошибки обычно гораздо ниже, а серьёзные ошибки будут отсеяны «фильтром здравого смысла», следовательно, не нанесут существенного вреда.
Грязное программирование с чистой душой: разработка эвристических систем (часть 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 звучит так: «должен существовать один — и, желательно, только один — очевидный способ сделать это». В грязном программировании нормальной является ситуация, когда одну и ту же задачу решают несколькими способами, причем одновременно.
По сути этот принцип является обобщением обсуждавшегося выше принципа создания частных решений наряду с общими. Аргументация здесь та же: снижение нагрузки на компонент позволяет ему лучше сосредоточиться на том, в чем он больше всего силен.
Раз задача решается несколькими способами, могут появиться разные решения. Популярным приемом является создание независимого компонента, выполняющего роль третейского судьи, и выбирающего лучшее решение среди представленных конкурентами. Если такой судья работает качественно, появляется надежда на то, что хотя бы один из компонентов «выстрелит».
Важность принципа многообразия решений трудно переоценить, и он широко используется на практике. Например, он может быть использован для постепенного избавления от компонентов, зашедших в тупик своего развития, т.е. достигших такой степени сложности, что контроль над ними можно считать потерянным. Вместо того чтобы сразу отказаться от морально устаревшей подсистемы, можно постепенно уменьшать ее область ответственности, вводя и развивая компоненты, частично ее подменяющие. Параллельно проблемную подсистему можно упрощать, удаляя из нее ставшие лишними части. Рано или поздно подсистема станет либо управляемой, либо безболезненно изымаемой из всей системы.
Конечно, у обсуждаемого принципа есть побочные эффекты. Во-первых, его применение приводит серьезному разбуханию кода. Во-вторых, конкурирующие решения создают нетривиальные зависимости между соответствующими компонентами, а вред таких зависимостей уже обсуждался.