Допустимая эвристика

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

Это связано с концепцией непротиворечивой эвристики . Хотя все непротиворечивые эвристики допустимы, не все допустимые эвристики непротиворечивы.

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

Допустимая эвристика используется для оценки стоимости достижения целевого состояния в алгоритме информированного поиска . Чтобы эвристика чтобы быть допустимым для задачи поиска, оценочная стоимость всегда должна быть ниже или равна фактической стоимости достижения целевого состояния. Алгоритм поиска использует допустимую эвристику для нахождения оценочной оптимальный путь к целевому состоянию от текущего узла. Например, в A* найдите оценочную функцию (где $n$ текущий узел):

$f(n)=g(n)+h(n)$

где

$f(n)$ = функция оценки.

$g(n)$ = стоимость от начального узла до текущего узла

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

$h(n)$ рассчитывается с использованием эвристики функция. При наличии недопустимой эвристики алгоритм A* может упустить оптимальное решение задачи поиска из-за переоценка в $f(n)$.

Формулировка

$n$ это узел

$h$ это эвристика

$h(n)$ стоимость указана $h$ достичь цели из $n$

$h^{*}(n)$ оптимальная стоимость достижения цели из $n$

$h(n)$ допустимо, если $\forall n$

$h(n)\leq h^{*}(n)$

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

Примеры

применимы два разных примера допустимых эвристик К задаче «Пятнадцать головоломок» :

• Расстояние Хэмминга
• Расстояние Манхэттен

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

Манхэттенское расстояние головоломки определяется как:

$h(n)=\sum _{\text{all tiles}}{\mathit {distance}}({\text{tile, correct position}})$

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

4 3	6 1	3 0	8 1
7 2	12 3	9 3	14 4
15 3	13 2	1 4	5 4
2 4	10 1	11 1

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

$h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36$

Доказательство оптимальности

Если допустимая эвристика используется в алгоритме, который на итерации продвигается только по пути с наименьшей оценкой (текущая стоимость + эвристика) из нескольких путей-кандидатов, завершается в тот момент, когда его исследование достигает цели, и, что особенно важно, никогда не закрывает все оптимальные пути раньше завершение (что возможно с помощью алгоритма поиска A*, если не принять особых мер ), то этот алгоритм может завершиться только на оптимальном пути. Чтобы понять почему, рассмотрим следующее доказательство от противного :

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

S _true < T _true

Тевал ≤ S_Севал

Если наша эвристика допустима, из этого следует, что на этом предпоследнем шаге T _eval = T _{истинно,} поскольку любое увеличение истинной стоимости за счет эвристики на T было бы недопустимо, и эвристика не может быть отрицательной. С другой стороны, допустимая эвристика потребует, чтобы S _eval ≤ S _true , что в сочетании с приведенными выше неравенствами дает нам T _eval < T _true и, более конкретно, T _eval ≠ T _true . Поскольку T _eval и T _true не могут быть одновременно равными и неравными, наше предположение должно быть ложным, и поэтому должно быть невозможно завершить процесс на более затратном, чем оптимальный, пути.

В качестве примера: скажем, у нас есть следующие затраты: (стоимость выше/ниже узла — это эвристика, стоимость на краю — это фактическая стоимость)

 0     10   0   100   0
START ----  O  ----- GOAL
 |                   |
0|                   |100
 |                   | 
 O ------- O  ------ O
100   1    100   1   100

Итак, очевидно, что мы начнем с посещения верхнего среднего узла, поскольку ожидаемая общая стоимость, т. е. $f(n)$, является $10+0=10$. Тогда целью будет кандидат с $f(n)$ равный $10+100+0=110$. Тогда мы бы явно выбрали нижние узлы один за другим, а затем обновленную цель, поскольку все они имеют $f(n)$ ниже, чем $f(n)$ текущей цели, т.е. их $f(n)$ является $100,101,102,102$. Таким образом, хотя цель была кандидатом, мы не могли выбрать ее, потому что существовали пути получше. Таким образом, допустимая эвристика может обеспечить оптимальность.

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

См. также

• Последовательная эвристика
• Эвристическая функция
• Алгоритм поиска