Что значит эвристическая функция

Эвристическая функция

Смотреть что такое «Эвристическая функция» в других словарях:

Алгоритм поиска A* — Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… … Википедия

А* — Алгоритмы поиска на графах A* B* Поиск в ширину Поиск в глубину Алгоритм Дейкстры Двунаправленный поиск Поиск с ограничением глубины Поиск по первому наилучшему совпадению Поиск A* (произносится «А звездочка») в информатике и математике, алгоритм … Википедия

Завьялова, Маргарита Павловна — (р. 03.03.1939) спец. в обл. теории познания; д р филос. наук, проф. Род. в г. Топки Кемеровской обл. Окончила ист. фи лол. ф т Томского ун та (1961). Работала на кафедре филос. в Том. ун те: прошла путь от лаборантки до проф.; с 1990 зав.… … Большая биографическая энциклопедия

Философские основания науки — Содержание 1 Введение 2 Функции философских оснований науки … Википедия

Годник, Симон Моисеевич — Годник Симон Моисеевич Дата рождения: 26 декабря 1929(1929 12 26) (82 года) Место рождения: Курск Страна … Википедия

Аксенов, Николай Романович — (р. 15.12.1920) спец. в обл. науч. атеизма и методики преподавания филос.; д р филос. наук, проф. Род. в с. Кирово Курганской обл. Окончил Челябинский тракторный техникум, Челябинский гос. пед. ин т. Участник Великой Отеч. войны. Работал учителем … Большая биографическая энциклопедия

Курбанов, Рафик Османович — (р. 1937) спец. по филос. науки и техники; д р филос. наук. Работает в ИФ АН СССР (ныне РАН), в наст. вр. вед. н. с. Сфера науч. интересов К. филос. вопросы физики, анализ заруб. иссл. по филос. естествознания и техники; глоб. проблемы… … Большая биографическая энциклопедия

Станис, Лилия Яковлевна — (р. 11.06.1924) спец. в обл. филос. методол. проблем естествознания, теории диалектики и истории филос.; д р филос. наук, проф. Род. в с. Тюхменеве Пензенской обл. Окончила филос. ф т МГУ (1950), асп. там же (1954). Работала на кафедре филос. АН… … Большая биографическая энциклопедия

Прикладные исследования — (НИР и ОКР, applied research, research and development R D) – научные исследования, направленные на решение социально практических проблем. Наука (science) сфера человеческой деятельности, функцией которой является выработка и теоретическая… … Википедия

Научно-популярный подстиль — – одна из стилистико речевых разновидностей науч. функц. стиля, выделяемая (по сравнению с собственно научным) на основании реализации дополнительных задач коммуникации – необходимости перевода специальной науч. информации на язык неспециального… … Стилистический энциклопедический словарь русского языка

Источник

Эвристика: что это простыми словами, методы эвристики

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

Что такое эвристика?

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

В разных изданиях можно встретить разные трактовки термина «эвристика», вот, к примеру:

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

Методы эвристики

Любой метод – это инструмент для получения каких-либо знаний, или решения каких-либо задач. Эвристика сама по себе уже является «оружием» для расширения рамок сознания. В условиях неполноценной информации и четкого плана для решения проблемы, эвристические методы позволяют использовать различные логические приёмы и методики. Симбиоз научных исследований и изобретательного творчества позволяют достичь поставленной цели.

Учитывая тот факт, что эвристика – это молодая наука, она пока лишена многих фундаментальных понятий. К примеру, это проявляется по отношению определения эвристического метода. Однако, несмотря на некоторые «погрешности», существуют методы, которые во многом могут помочь современному человеку выстроить правильный алгоритм действий при решении личных, или профессиональных проблем. Вот самые яркие примеры эвристических методов:

История развития эвристики

Отцом-основателем самой сути эвристики считают Сократа. Он имел особенный подход при обучении своих последователей. Для того, чтобы человек смог познать суть предмета, или явления, великий философ использовал наводящие вопросы. Это позволяло ученику выстроить логическую цепочку, и в правильной последовательности «осознать» суть вещи. Подобные диалоги назывались «сократическими беседами» именно они по мнению многих легли в основу эвристических методов.

Метод Сократа неоднократно был описан и развит в трудах многих известных деятелей. В числе таких: Архимед, Г. Галилей, Ф. Бекон и другие. Эвристику с педагогической точки зрения, рассматривали в своих трудах Ж.-Ж Руссо и Л. Н. Толстой. Оба автора пришли к выводу, что ребёнок должен познавать новое, через призму собственного опыта. При этом, ученик должен иметь свободу выбора при решении поставленных задач. Такой же точки зрения придерживались С. Френе, С. Т. Шацкий, П. Ф. Каптерев и другие.

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

Заключение

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

Источник

Методом проб и ошибок: что такое эвристика и причем тут искажения?

Помните такую шутку, что правильный ответ был найден «методом научного тыка»? Шутки шутками, а ведь это просторечное название одного из врожденных видов мышления человека — метода проб и ошибок. Это эвристический способ поиска решения, который позволяет найти ответ при помощи перебора вариантов. Применяется он обычно при недостаточности исходных данных, поэтому влечет за собой ошибки. Такие ошибки еще называют когнитивными искажениями. Но обо всем по порядку.

Эврика!

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

Слово произошло из Греции, как и сам способ обучения. Его ввел Сократ, который проводил с учениками так называемые сократические беседы, в ходе которых задавал наводящие вопросы ученикам. Таким образом, ученики сами приходили к правильному ответу. Заодно эти беседы развивали критическое мышление у детей — проблема рассматривалась максимально обширно, непредвзято. В переводе с греческого эвристика — «открываю», «отыскиваю». Легенда о том, что Архимед выкрикнул однокоренное «Эврика!» в значении «нашел» — не только красивая, но и логичная.

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

Кривое зеркало

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

Шаблоны мышления возникают из-за того, что мозг экономит энергию и делает выбор в пользу быстрого решения. Особенно, если его «правильность» подтверждается хотя бы частично. Так появляется крючок, которому в большей степени подвержены азартные люди — «ошибка игрока». Игрок, принимая решение, на какой цвет ставить, наблюдает, что черное выпало 5 раз подряд. И ставит на красное с мыслью «вот сейчас уж точно должно сработать!», не принимая во внимание то, что вероятность по-прежнему составляет 50/50.

Игра по правилам

Эвристический подход к решению задач относится к теории творческого мышления и подчиняется определенным правилам.

С этими и другими методами решения задач можно познакомиться в курсе «Творческое мышление». Вы узнаете, как стать креативным и находить нестандартные решения сложных задач, а также научитесь генерировать новые идеи и воплощать их в жизнь.

Источник

Эвристическая функция

Информи́рованный по́иск (также эвристический поиск, англ. informed search, heuristic search ) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.

Содержание

Эвристические функции

В контексте поиска в пространстве состояний, эвристическая функция (англ. heuristic function ) h(n) определена на узлах дерева перебора следующим образом:

h(n) = оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.

Если n — целевой узел, то h(n) = 0.

Узел для развёртывания выбирается на основе функции оценки (англ. evaluation function )

f(n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n, f(n) = g(n) + h(n),

где функция g(n) определяет стоимость уже пройденного пути от начального узла до узла n.

Если эвристическая функция h(n) никогда не переоценивает фактическую минимальную стоимость достижения цели (то есть является нижней оценкой фактической стоимости), то такая функция называется допустимой (англ. admissible ).

Если эвристическая функция h(n) удовлетворяет условию

где b — потомок a, то такая функция называется преемственной (англ. consistent ).

Если f(n) = g(n) + h(n) — функция оценки, h(n) — преемственная функция, то функция f(n) является монотонно неубывающей вдоль любого исследуемого пути. Поэтому преемственные функции также называются монотонными (англ. monotonic ).

Любая преемственная функция является допустимой, но не любая допустимая функция является преемственной.

Если h₁(n), h₂(n) — допустимые эвристические функции, и для любого узла n верно неравенство h₁(n) ≥ h₂(n), то h₁ является более информированной эвристикой, или доминирует над h₂.

Сравнение эвристических функций

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

Примеры задач поиска

В головоломке «Пятнашки» может быть применена эвристика h_m, основанная на манхэттенском расстоянии. Более конкретно, для каждой плитки подсчитывается манхэттенское расстояние между её текущим положением и её положением в начальном состоянии; полученные величины суммируются.

Можно показать, что эта эвристика является допустимой и преемственной: за один ход её значение не может измениться более чем на ±1.

Конструирование эвристических функций

Ослабленная задача

Подзадача

Подзадачей задачи решения головоломки «Пятнашки» может быть задача перемещения на свои места плиток 1, 2, 3 и 4. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.

Базы данных с шаблонами

Алгоритмы поиска

Поиск по первому наилучшему совпадению

Поиск по первому наилучшему совпадению (англ. best-first search ) представляет собой подход, в котором узел для развёртывания выбирается на основе оценочной функции f(n). Для развёртывания выбирается узел с наименьшей оценкой.

Поиск A*

Поиск A* — наиболее известная разновидность поиска по первому наилучшему совпадению. В нём применяется оценка f(n) стоимости наименее дорогостоящего пути решения, проходящего через узел n:

f(n) = g(n) + h(n), где g(n) — стоимость пути от начального узла до узла n, h(n) — оценка стоимости пути от узла n до цели.

Если h(n) никогда не переоценивает стоимость достижения цели (то есть является допустимой), то поиск A* является оптимальным.

Алгоритм A* с итеративным углублением (iterative deepening A*, IDA*) — применение идеи итеративного углубления в контексте эвристического поиска.

Неинформированный алгоритм итеративного углубления останавливает развёртывание, когда глубина поиска d превышает текущий предел глубины l. Информированный алгоритм IDA* останавливает развёртывание, когда оценка f(n) стоимости пути через текущий узел n превышает текущий предел стоимости пути bound.

Алгоритм IDA* отличается минимальными затратами памяти по сравнению с A* и сравнительно малым (в случае удачного выбора эвристики) количеством развёрнутых узлов по сравнению с IDDFS.

Источник

Эвристическая функция

Информи́рованный по́иск (также эвристический поиск, англ. informed search, heuristic search ) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.

Содержание

Эвристические функции [ | ]

В контексте поиска в пространстве состояний, эвристическая функция (англ. heuristic function ) h(n) определена на узлах дерева перебора следующим образом:

h(n) = оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.

Если n — целевой узел, то h(n) = 0.

Узел для развёртывания выбирается на основе функции оценки (англ. evaluation function )

f(n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n, f(n) = g(n) + h(n),

где функция g(n) определяет стоимость уже пройденного пути от начального узла до узла n.

Если эвристическая функция h(n) никогда не переоценивает фактическую минимальную стоимость достижения цели (то есть является нижней оценкой фактической стоимости), то такая функция называется допустимой (англ. admissible ).

Если эвристическая функция h(n) удовлетворяет условию

где b — потомок a, то такая функция называется преемственной (англ. consistent ).

Если f(n) = g(n) + h(n) — функция оценки, h(n) — преемственная функция, то функция f(n) является монотонно неубывающей вдоль любого исследуемого пути. Поэтому преемственные функции также называются монотонными (англ. monotonic ).

Любая преемственная функция является допустимой, но не любая допустимая функция является преемственной.

Если h₁(n), h₂(n) — допустимые эвристические функции, и для любого узла n верно неравенство h₁(n) ≥ h₂(n), то h₁ является более информированной эвристикой, или доминирует над h₂.

Сравнение эвристических функций [ | ]

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

Примеры задач поиска [ | ]

В головоломке «Пятнашки» может быть применена эвристика h_m, основанная на манхэттенском расстоянии. Более конкретно, для каждой плитки подсчитывается манхэттенское расстояние между её текущим положением и её положением в начальном состоянии; полученные величины суммируются.

Можно показать, что эта эвристика является допустимой и преемственной: за один ход её значение не может измениться более чем на ±1.

Конструирование эвристических функций [ | ]

Ослабленная задача [ | ]

Подзадача [ | ]

Подзадачей задачи решения головоломки «Пятнашки» может быть задача перемещения на свои места плиток 1, 2, 3 и 4. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.

Базы данных с шаблонами [ | ]

Алгоритмы поиска [ | ]

Поиск по первому наилучшему совпадению [ | ]

Поиск по первому наилучшему совпадению (англ. best-first search ) представляет собой подход, в котором узел для развёртывания выбирается на основе оценочной функции f(n). Для развёртывания выбирается узел с наименьшей оценкой.

Поиск A* [ | ]

Поиск A* — наиболее известная разновидность поиска по первому наилучшему совпадению. В нём применяется оценка f(n) стоимости наименее дорогостоящего пути решения, проходящего через узел n:

f(n) = g(n) + h(n), где g(n) — стоимость пути от начального узла до узла n, h(n) — оценка стоимости пути от узла n до цели.

Если h(n) никогда не переоценивает стоимость достижения цели (то есть является допустимой), то поиск A* является оптимальным.

Алгоритм A* с итеративным углублением (iterative deepening A*, IDA*) — применение идеи итеративного углубления в контексте эвристического поиска.

Неинформированный алгоритм итеративного углубления останавливает развёртывание, когда глубина поиска d превышает текущий предел глубины l. Информированный алгоритм IDA* останавливает развёртывание, когда оценка f(n) стоимости пути через текущий узел n превышает текущий предел стоимости пути bound.

Алгоритм IDA* отличается минимальными затратами памяти по сравнению с A* и сравнительно малым (в случае удачного выбора эвристики) количеством развёрнутых узлов по сравнению с IDDFS.

Источник