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

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

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

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

${displaystyle f (n) = g (n) + h (n)}$

куда

{displaystyle f (n)}

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

{displaystyle g (n)}

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

{displaystyle h (n)}

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

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

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

{displaystyle n}

это узел

{displaystyle h}

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

{displaystyle h (n)}

Стоимость указана

{displaystyle h}

достичь цели из

{displaystyle n}

{displaystyle h ^ {*} (n)}

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

{displaystyle n}

{displaystyle h (n)}

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

{displaystyle forall n}

{displaystyle h (n) leq h ^ {*} (n)}

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

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

Примеры

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

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

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

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

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

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 * ), то этот алгоритм завершится на кратчайшем пути. Чтобы понять, почему, просто представьте, что любой путь, на котором завершается алгоритм, был продвинут только потому, что его общая ожидаемая стоимость была самой низкой из возможных. Для допустимой эвристики ни один из кандидатов не переоценивает свои затраты, поэтому их истинные затраты могут быть только больше или равны стоимости принятого пути. Наконец, общая ожидаемая стоимость - это истинная стоимость пути, который достигает цели, потому что единственная допустимая эвристика при достижении цели равна нулю.

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

 0 10 0 100 0 НАЧАЛО ---- O ----- ЦЕЛЬ | | 0 | | 100 | | О ------- О ------ O100 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 * никогда не вернет неоптимальный целевой узел.

Смотрите также

[1] Рассел, С.Дж .; Норвиг П. (2002). Искусственный интеллект: современный подход. Прентис Холл. ISBN 0-13-790395-2.

[Korf,2000-2] Корф, Ричард Э. (2000), «Последние достижения в разработке и анализе допустимых эвристических функций» (PDF), в Choueiry, Berthe Y .; Уолш, Тоби (ред.), Абстракция, переформулирование и приближение: 4-й Международный симпозиум, SARA 2000 Horseshoe Bay, США, 26-29 июля 2000 г. Труды, 1864, Springer, стр. 45–55, Дои:10.1007/3-540-44914-0_3, ISBN 978-3-540-67839-7, получено 2010-04-26

[3] «Почему допустимая [sic] эвристика гарантирует оптимальность?». алгоритм. Переполнение стека. Получено 2018-12-11.

[1]

[2]

[3]