Нарушение допустимости A * привело к экспоненциальному ускорению?

Question

Я работаю над обобщенной версией головоломки, в которой плитки не имеют чисел. Вместо этого в каждом месте есть плитка или отверстие и представлено логическое значение true или false (плитка или отверстие).

Пункт поиска состоит в том, чтобы взять начальное состояние с n плитами и состояние цели с n целевыми местоположениями и использовать A *, чтобы найти решение о том, как перемещать плитки так, чтобы каждое местоположение цели было заполнено. Вот пример ниже для 4x3 сетки:

Initial State: 
T F T F 
F F T F 
F F T T 

Goal State 
T T T T 
T F F F 
F F F F 

я работал на разных эвристики, чтобы сделать это, и наиболее успешным было логики, что-то вроде этого:

int heuristicVal = 0 

for every tile (i)... 
int closest = infinity 
for every goal location (j)... 
if (manhattan distance of ij < closest) closest = manhattan distance of ij 
end for 
heuristicVal += closest 
end for 

return heuristicVal 

К сожалению, это был слишком медленным в ситуациях, когда две или более плитки направлялись эвристикой в ​​одно и то же целевое местоположение. Я попытался умножить heuristicVal на количество плиток, и внезапно появилась экспоненциальная скорость. Проблемы, которые занимали 28 секунд раньше, занимали менее 1 секунды.

Редактировать: Оказалось, что это не всегда дает оптимальные решения после этого изменения. Тем не менее, я не понимаю, почему это так ускорилось или почему оно все еще находит правильный (хотя и неоптимальный) ответ, несмотря на то, что он не является допустимым.

Answer 1

Если вы нарушите допустимость, A * перестанет работать правильно. Обратите внимание, что перестает работать правильно. не означает, что вы никогда не получите оптимальный результат - вам больше не гарантируется его получение. Вы также можете в конечном итоге сходиться быстрее на решении, но в чем смысл, если это решение не является правильным?