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

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

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

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

${\ Displaystyle е (п) = г (п) + час (п)}$

где

{\ displaystyle f (n)}

= функция оценки.

{\ Displaystyle г (п)}

= стоимость от начального узла до текущего узла

{\ Displaystyle ч (п)}

= ориентировочная стоимость от текущего узла до цели.

${\ Displaystyle ч (п)}$ вычисляется с помощью эвристической функции. С недопустимой эвристикой алгоритм A * может упустить из виду оптимальное решение проблемы поиска из-за завышенной оценки . ${\ displaystyle f (n)}$

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

{\ displaystyle n}

это узел

{\ displaystyle h}

это эвристический

{\ Displaystyle ч (п)}

стоимость, указанная для достижения цели с

{\ displaystyle h}

{\ displaystyle n}

{\ Displaystyle ч ^ {*} (п)}

оптимальная стоимость достижения цели с

{\ displaystyle n}

{\ Displaystyle ч (п)}

допустимо, если,

{\ displaystyle \ forall n}

{\ Displaystyle ч (п) \ Leq ч ^ {*} (п)}

Строительство

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

Примеры

К проблеме пятнадцати головоломок применимы два разных примера допустимой эвристики :

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

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

{\ displaystyle h (n) = \ sum _ {\ text {все плитки}} {\ mathit {distance}} ({\ text {tile, right position}})}

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

4 ₃	6 ₁	3 ₀	8 ₁
7 ₂	12 ₃	9 ₃	14 ₄
15 ₃	13 ₂	1 ₄	5 ₄
2 ₄	10 ₁	11 ₁

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

{\ displaystyle 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 _истина < T _истина

T _eval ≤ S _eval

Если наша эвристика допустима, из этого следует, что на этом предпоследнем шаге T _eval = T _true, потому что любое увеличение истинной стоимости эвристикой на 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

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

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

Заметки

Хотя все согласованные эвристики допустимы, не все допустимые эвристики согласованы.

Для задач поиска по дереву, если используется допустимая эвристика, алгоритм поиска A * никогда не вернет неоптимальный целевой узел.

Languages

In other projects