Я работал над обобщенной версией головоломки со скользящими плитками, где плитки не имеют чисел. Вместо этого каждое местоположение имеет плитку или отверстие и представлено логическим значением как 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 секунду.
Редактировать. Оказывается, это изменение не всегда приводит к оптимальным решениям. Однако я не понимаю, почему он так ускорился или почему он все еще находит правильный (хотя и неоптимальный) ответ, несмотря на то, что он больше не является допустимым.
