При использовании A * (или любого другого лучшего алгоритма поиска пути) мы говорим, что используемая эвристика должна быть допустимой , то есть она никогда не должна переоценивать фактическую длину пути решения (или перемещения).
Как допустимая эвристика обеспечивает оптимальное решение? Я предпочтительно ищу интуитивное объяснение.
Если вы хотите, вы можете объяснить, используя эвристику Манхэттена для 8-головоломки.
Ответы:
Хотя ответ Антона абсолютно совершенен, позвольте мне попытаться дать альтернативный ответ: допустимость означает, что эвристика не переоценивает усилия по достижению цели, т. для всех n в пространстве состояний (в 8-головоломке это означает только для любой перестановки плиток и цели, которую вы рассматриваете в настоящее время) где h ∗ ( nh(n)≤h∗(n) n - оптимальная стоимость для достижения цели.h∗(n)
Я думаю, что наиболее логичный ответ, чтобы увидеть, почему обеспечивает оптимальные решения, если h ( n ) допустим, это потому, что он сортирует все узлы в OPEN в порядке возрастания f ( n ) = g ( n ) + h ( n ), а также потому что оно не останавливается при генерации цели, а при ее расширении:A∗ h(n) f(n)=g(n)+h(n)
И это, по сути, все, что вы найдете в оригинальном доказательстве Nilsson et al.
Надеюсь это поможет,
источник
Если эвристическая функция недопустима, мы можем получить оценку, превышающую фактическую стоимость пути от некоторого узла к целевому узлу. Если эта более высокая оценка стоимости пути находится на пути с наименьшей стоимостью (которую мы ищем), алгоритм не будет ее изучать и может найти другой (не менее затратный) путь к цели.
Посмотрите на этот простой пример.
Пусть и G - соответственно начальный и целевой узлы. Пусть h ( N ) - оценка длины пути от узла N до G , ∀ N в графе. Кроме того, пусть c ( N , X i ) будет функцией стоимости шага от узла N до его соседа X i , ∀ N и i = 1 .. m , где mA G h(N) N G ∀N c(N,Xi) N Xi ∀N i=1..m m это число соседей (т. е. функция, которая возвращает стоимость ребра между узлом N и одним из его соседей).N N
Пусть эвристика будет
Эта эвристическая функция недопустима, поскольку h ( C ) = 4 > c ( C , G ) = 2H
источник