Как манхэттенское расстояние является допустимой эвристикой?

Question

Не правда ли, что подсчет ходов за 1 плиткой может привести к тому, что другие плитки достигнут своего целевого состояния?И, следовательно, подсчет каждой плитки может дать нам больше, чем минимальные ходы, необходимые для достижения целевого состояния?

Этот вопрос в контексте расстояния Манхэттена для 15-Puzzle.

ВотВопрос другими словами:

Можем ли мы использовать манхэттенское расстояние в качестве допустимой эвристики для N-Puzzle.Для реализации поиска A * нам нужна допустимая эвристика.Манхэттенский эвристик - кандидат?Если да, как вы противостоите приведенному выше аргументу (первые 3 предложения в вопросе)?

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

Answer 1

Допустимая эвристика не должна переоценивать количество ходов для решения этой проблемы.Поскольку вы можете перемещать блоки 1 только за один раз и только в одном из 4 направлений, оптимальный сценарий для каждого блока состоит в том, что он имеет свободный и беспрепятственный путь к своему целевому состоянию.Это MD 1. 1. 1001 *

Остальные состояния для пары блоков неоптимальны, то есть будет делать больше ходов, чем MD, чтобы получить блок справаместо.Таким образом, эвристика никогда не переоценивает и является допустимой.

Я буду удалять, когда кто-то публикует правильную формальную версию этого.

Answer 2

Формальное Доказательство: По определению h, h (s ∗) = 0, если s ∗ - целевое состояние. Предположим для доказательства от противного что C ∗ 0, что приводит нас к противоречие, так как h (s ∗) должен быть равен нулю. Следовательно, мы должны иметь h (s0) ≤ C ∗ для всего s0, а h допустимо. ( Источник : Калифорнийский университет, Ирвин)