Что такое эвристическая функция
Перейти к содержимому

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

  • автор:

Значение словосочетания «эвристическая функция»

Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!

Спасибо! Я стал чуточку лучше понимать мир эмоций.

Вопрос: захватка — это что-то нейтральное, положительное или отрицательное?

Нейтральное
Положительное
Отрицательное

Ассоциации к слову «функция»

Синонимы к словосочетанию «эвристическая функция»

Предложения со словосочетанием «эвристическая функция»

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

Цитаты из русской классики со словосочетанием «эвристическая функция»

  • Материю на костюмчик приобрели хорошую, а сшить костюм — не умеете и вообще, говорит, вы — одноклеточный организм, без функции ».

Сочетаемость слова «эвристический»

  • эвристические методы
    эвристическая функция
    эвристический характер
  • (полная таблица сочетаемости)

Сочетаемость слова «функция»

  • определённые функции
    важная функция
    психические функции
  • функции управления
    функции мозга
    функции организма
  • нарушение функции
    выполнение функций
    ряд функций
  • функция возвращает
  • выполнять свою функцию
    осуществлять свои функции
    иметь свою функцию
  • (полная таблица сочетаемости)

Понятия, связанные со словосочетанием «эвристическая функция»

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

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

Операциональное определение (англ. operational definition) или рабочее определение — описание явления (переменной, термина, объекта и т. д.) в терминах операций (процесса), которые необходимо произвести для подтверждения наличия явления, измерения его продолжительности и величины. Операциональное определение противопоставляется теоретическому, или концептуальному определению (которое, как правило, даётся в словарях и малопригодно при проведении практических исследований и измерений) и является результатом.

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

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

Афоризмы русских писателей со словом «функция»

  • Зло определяется конъюнктурой, спросом, функцией его носителя. Кроме того, фактором случайности. Неудачным стечением обстоятельств. И даже — плохим эстетическим вкусом.

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

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

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

Рис. 4.5. Типичный экземпляр головоломки «игра в восемь». Решение имеет длину 26 этапов

Средняя стоимость решения для сформированного случайным образом экземпляра головоломки «игра в восемь» составляет около 22 этапов. Коэффициент ветвления примерно равен 3. (Если пустой квадрат находится в середине коробки, то количество возможных ходов равно четырем, если находится в углу— двум, а если в середине одной из сторон — трем.) Это означает, что при исчерпывающем поиске на глубину 22 приходится рассматривать примерносостояний. Отслеживая повторяющиеся состояния, это количество состояний можно сократить приблизительно в 170 000 раз, поскольку существует только 9 ! /2 = 181 440 различимых состояний, которые являются достижимыми (см. упр. 3.4.) Это количество состояний уже лучше поддается контролю, но соответствующее количество для игры в пятнадцать примерно равно, поэтому для такой головоломки с более высокой сложностью требуется найти хорошую эвристическую функцию. Если нужно находить кратчайшие решения с использованием поиска А*, то требуется эвристическая функция, которая никогда не переоценивает количество этапов достижения цели. История исследований в области поиска таких эвристических функций для игры в пятнадцать является довольно долгой, а в данном разделе рассматриваются два широко используемых кандидата на эту роль, которые описаны ниже.

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

= сумма расстояний всех фишек от их целевых позиций. Поскольку фишки не могут передвигаться по диагонали, рассчитываемое расстояние представляет собой сумму горизонтальных и вертикальных расстояний. Такое расстояние иногда называют расстоянием, измеряемым в городских кварталах, или манхэттенским расстоянием. Эвристическая функция h2 также является допустимой, поскольку все, что может быть сделано в одном ходе, состоит лишь в перемещении одной фишки на один этап ближе к цели. Фишки от 1 до 8 в рассматриваемом начальном состоянии соответствуют такому значению манхэттенского расстояния:

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

all rights reserved © 2002, rriai.org.ru

Алгоритм A*

Алгоритм А* (англ. A star) — алгоритм поиска, который находит во взвешенном графе маршрут наименьшей стоимости от начальной вершины до выбранной конечной.

Описание

Пример работы А*. Пустые кружки принадлежат к открытому списку, а окрашенные к закрытому.

В процессе работы алгоритма для вершин рассчитывается функция [math]f(v) = g(v) + h(v)[/math] , где

  • [math]g(v)[/math] — наименьшая стоимость пути в [math]v[/math] из стартовой вершины,
  • [math]h(v)[/math] — эвристическое приближение стоимости пути от [math]v[/math] до конечной цели.

Фактически, функция [math]f(v)[/math] — длина пути до цели, которая складывается из пройденного расстояния [math]g(v)[/math] и оставшегося расстояния [math]h(v)[/math] . Исходя из этого, чем меньше значение [math]f(v)[/math] , тем раньше мы откроем вершину [math]v[/math] , так как через неё мы предположительно достигнем расстояние до цели быстрее всего. Открытые алгоритмом вершины можно хранить в очереди с приоритетом по значению [math]f(v)[/math] . А* действует подобно алгоритму Дейкстры и просматривает среди всех маршрутов ведущих к цели сначала те, которые благодаря имеющейся информации (эвристическая функция) в данный момент являются наилучшими.

Свойства

Чтобы A* был оптимален, выбранная функция [math]h(v)[/math] должна быть допустимой эвристической функцией.

Определение:
Говорят, что эвристическая оценка [math]h(v)[/math] допустима, если для любой вершины [math]v[/math] значение [math]h(v)[/math] меньше или равно весу кратчайшего пути от [math]v[/math] до цели.

Допустимая оценка является оптимистичной, потому что она предполагает, что стоимость решения меньше, чем оно есть на самом деле.
Второе, более сильное условие — функция [math]h(v)[/math] должна быть монотонной.

Определение:
Эвристическая функция [math]h(v)[/math] называется монотонной (или преемственной), если для любой вершины [math]v_1[/math] и ее потомка [math]v_2[/math] разность [math]h(v_1)[/math] и [math]h(v_2)[/math] не превышает фактического веса ребра [math]c(v_1, v_2)[/math] от [math]v_1[/math] до [math]v_2[/math] , а эвристическая оценка целевого состояния равна нулю.

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

Пусть [math]k(v)[/math] — длина кратчайшего пути из вершины [math]v[/math] до цели. Докажем индукцией по числу шагов до цели, что [math]h(v) \leqslant k(v)[/math] .

Если до цели расстояние [math]0[/math] , то [math]v[/math] — цель и [math]h(v) = 0 \leqslant k(v)[/math] .

Пусть [math]v[/math] находится на расстоянии [math]i[/math] от цели. Тогда существует потомок [math]v'[/math] , который находится на кратчайшем пути от [math]v[/math] до цели и [math]v'[/math] лежит на расстоянии [math]i — 1[/math] шагов до цели. Следовательно, [math]h(v) \leqslant c(v, v’) + h(v’)[/math] .

По предположению, [math]h(v’) \leqslant k(v’)[/math] . Следовательно, [math]h(v) \leqslant c(v, v’) + k(v’) = k(v)[/math] .

Если [math]h(v)[/math] монотонна, то последовательность значений [math]f(v)[/math] на любом пути неубывает.

Доказательство следует из определения монотонности.

Алгоритм A* является оптимальным, если функция [math]h(v)[/math] монотонна.

Примеры эвристик

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

Пример А* на сетке с возможностью ходить в восьми напрвлениях

  • Если мы можем перемещаться в четырех направлениях, то в качестве эвристики стоит выбрать манхэттенское расстояние [1]
    [math]h(v) = || + ||[/math] .
  • Расстояние Чебышева [2] применяется, когда к четырем направлениям добавляются диагонали:
    [math]h(v) = \max<(||, ||)>[/math] .
  • Если передвижение не ограничено сеткой, то можно использовать евклидово расстояние по прямой:
    [math]h(v) = \sqrt[/math] .

Также стоит обратить внимание на то как соотносятся [math]f(v)[/math] и [math]h(v)[/math] . Если они измеряются в разных величинах (например, [math]g(v)[/math] — это расстояние в километрах, а [math]h(v)[/math] — оценка времени пути в часах) А* может выдать некорректный результат.

Реализация

В приведённой реализации:

  • [math]Q[/math] — множество вершин, которые требуется рассмотреть,
  • [math]U[/math] — множество рассмотренных вершин,
  • [math]f[x][/math] — значение эвристической функции «расстояние + стоимость» для вершины [math]x[/math] ,
  • [math]g[x][/math] — стоимость пути от начальной вершины до [math]x[/math] ,
  • [math]h(x)[/math] — эвристическая оценка расстояния от вершины [math]x[/math] до конечной вершины.

На каждом этапе работы алгоритма из множества [math]Q[/math] выбирается вершина с наименьшим значением эвристической функции и просматриваются её соседи. Для каждого из соседей обновляется расстояние, значение эвристической функции и он добавляется в множество [math]Q[/math] .
Псевдокод:

bool A*(start, goal): U = [math] \varnothing [/math] Q = [math] \varnothing [/math] Q.push(start) g[start] = 0 f[start] = g[start] + h(start) while Q.size() != 0 current = вершина из [math]Q[/math] с минимальным значением [math]f[/math] if current == goal return true // нашли путь до нужной вершины Q.remove(current) U.push(current) for v : смежные с current вершины tentativeScore = g[current] + d(current, v) // d(current, v) — стоимость пути между current и v if [math]v \in U[/math] and tentativeScore >= g[v] continue if [math]v \notin U[/math] or tentativeScore < g[v] parent[v] = current g[v] = tentativeScore f[v] = g[v] + h(v) if [math]v \notin Q[/math] Q.push(v) return false 

См. также

  • Эвристики для поиска кратчайших путей
  • Алгоритм Флойда
  • Алгоритм Дейкстры
  • Алгоритм Форда-Беллмана

Примечания

  1. ↑Wikipedia — Manhattan distance
  2. ↑Википедия — Расстояние Чебышева

Источники информации

  • С. Рассел, П. Норвиг — Искусственный интеллект. Современный подход, 2е издание
  • Википедия — Алгоритм поиска A*
  • Wikipedia — A* search algorithm
  • Статья о поиске кратчайших путей
  • Generalized best-first search strategies and the optimality of A*

Эмоции: эвристическая функция

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

Так ли это? Для ответа на этот вопрос важно различать эвристическую и сигнальную функцию эмоций. Сигналить — эмоция сигналит, подсказывает ли она решение? — вопрос другой.

Если в машине начинает сигналить лампочка о том, что кончается бензин, можно, конечно, сказать, что нам подсказывает лампочка. Точнее все-таки говорить о том, что подсказывает нам датчик, стоящий за этой лампочкой, и наша голова, которая видит сигнал лампочки.

Так же, если нам сигналят огни впереди идущей машины, то кто же нам все-таки подсказывает, что стоит притормозить: фары машины или водитель этой машины?

Думается, что точнее говорить о том, что нам подсказывает наш опыт, и опыт не всегда полностью осознаваемый. — см.→

Иногда говорят, что эвристическая функция эмоций в том, что эмоции подталкивают нас двигаться вперед. Здесь неточность — двигаться вперед нас подвигают внутренние чувства, термины имеет смысл употреблять более точно. Эмоции побуждают импульсивные действия, чувства побуждают направленное, хотя и не вполне осмысленное, поведение (см.→) Считать ли подталкивание к импульсивному поведению эвристической функцией? — Разумные люди с этим не согласятся.

Но даже если не фиксироваться на терминах, то это про разное: эмоции нас могут двигать вперед, но ничего не подсказывать. Также как (теоретически) могут нам подсказывать, но не двигать нас вперед.

  • Эмоции в человеческой жизни
  • Функции эмоций

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *