Является ли двукратное манхэттенское расстояние все еще допустимым в задаче поиска головоломки N с использованием звезды A?
Я знаю, что манхэттенское расстояние является допустимой эвристической функцией, поскольку она не переоценивает стоимость перемещения плитки в нужное место. Но мой вопрос
Если я удваиваю h, скажем, увеличиваю каждое из манхэттенских расстояний в 2 раза или в коэффициент соответствующего значения тайла (например, h'=9*h, если мы перемещаем тайл 9, 2*h, если мы перемещаем 2 тайла). ).
Это еще допустимо? Мне кажется, что это не так, потому что он завышает истинную стоимость. Итак, для этой конкретной проблемы, является ли манхэттенское расстояние наиболее доминирующей эвристической функцией?
взяв это за пример, начиная с
1 2 3
4 5 6
7 0 8
мы хотим
1 2 3
4 5 6
7 8 0
Очевидно, нам нужен только один ход (поменять местами 0 и 8) и гарантированно найти решение, так что допустимое или недопустимое в данный момент не имеет значения. Но вообще, является ли 2*MD допустимой эвристической функцией? Как мы это обосновываем?