Как допустимая эвристика обеспечивает оптимальное решение?

16

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

Как допустимая эвристика обеспечивает оптимальное решение? Я предпочтительно ищу интуитивное объяснение.

Если вы хотите, вы можете объяснить, используя эвристику Манхэттена для 8-головоломки.

Ashwin
источник
2
@Ashwin Интуитивно понятно, потому что, когда алгоритм находит путь длиной , он уже перепробовал любой другой путь, который может иметь длину не более k . Вот почему ваша эвристическая функция никогда не должна переоценивать цену цели. Попробуйте сами, сделав эвристическую функцию, которая может быть переоценена. kk
Пол GD

Ответы:

7

Хотя ответ Антона абсолютно совершенен, позвольте мне попытаться дать альтернативный ответ: допустимость означает, что эвристика не переоценивает усилия по достижению цели, т. для всех n в пространстве состояний (в 8-головоломке это означает только для любой перестановки плиток и цели, которую вы рассматриваете в настоящее время) где h ( nh(n)h(n)n - оптимальная стоимость для достижения цели.h(n)

Я думаю, что наиболее логичный ответ, чтобы увидеть, почему обеспечивает оптимальные решения, если h ( n ) допустим, это потому, что он сортирует все узлы в OPEN в порядке возрастания f ( n ) = g ( n ) + h ( n ), а также потому что оно не останавливается при генерации цели, а при ее расширении:Ah(n)f(n)=g(n)+h(n)

  1. Поскольку узлы раскрываются в порядке возрастания вы знаете, что ни один другой узел не является более перспективным, чем текущий. Помните: h ( n ) допустимо, так что наличие наименьшего f ( n ) означает, что у него есть возможность достичь цели более дешевым путем, чем у других узлов в OPEN. И это верно, если вы не можете доказать обратное, т. Е. Путем расширения текущего узла.f(n)h(n)f(n)
  2. Поскольку останавливается только тогда, когда он продолжает расширять целевой узел (в противоположность остановке при его генерации), вы уверены (из первого пункта выше), что ни один другой узел не ведет через более дешевый путь к нему.A

И это, по сути, все, что вы найдете в оригинальном доказательстве Nilsson et al.

Надеюсь это поможет,

Карлос Линарес Лопес
источник
3
Благодарю. Это помогло. Вы имели в виду какое-то доказательство Nilsson et al. Кто это? И где я могу найти доказательства?
Эшвин
1
@Ashwin См. Книгу « Принципы искусственного интеллекта » (около 80 стр.) Нильса Дж. Нильссона (1982).
nbro
11

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

Посмотрите на этот простой пример.

введите описание изображения здесь

Пусть и G - соответственно начальный и целевой узлы. Пусть h ( N ) - оценка длины пути от узла N до G , N в графе. Кроме того, пусть c ( N , X i ) будет функцией стоимости шага от узла N до его соседа X i , N и i = 1 .. m , где mAGh(N)NGNc(N,Xi)NXiNi=1..mmэто число соседей (т. е. функция, которая возвращает стоимость ребра между узлом N и одним из его соседей).NN

Пусть эвристика будет

  • h(B)=3

  • h(C)=4

Эта эвристическая функция недопустима, поскольку h ( C ) = 4 > c ( C , G ) = 2H

h(C)=4>c(C,G)=2

AABGABG4ACG3

Антон
источник
1
Ok. Но как допустимая эвристика обеспечивает оптимальное решение?
Эшвин
Может случиться так, что - h (b) <h (c) с допустимыми значениями h (b) и h (c), но фактическая_катость (б)> фактическая_кост (в) не так ли? Таким образом, b будет выбран в качестве следующего пути, где в действительности c дал бы лучший путь.
Эшвин
Для 1-го комментария: допустимая эвристика обеспечивает поиск кратчайшего пути. Само решение является оптимальным, если эвристика согласована .
Антон
Для второго комментария: если эвристика допустима, можно выбрать A-> B для следующего расширяемого узла, но после этого A * выберет A-> C, а не A-> B-> G. И в конце концов это закончится с A-> C-> G.
Антон
1
Потому что А * работает так. Он расширяет узел с наименьшей суммой расстояния до этого узла + эвристическая оценка от этого узла. d (A, G) + h (G) = 4 + 0 = 4 и d (A, C) + h (C) = 1 + что-то <= 2 (потому что это допустимо). Таким образом, C имеет меньшую сумму, и A * выберет ее. Так же, как это будет, чем расширить G и найти наименьший путь.
Антон