Эвристическая функция X-Y для решения N-головоломки

Question

Может ли кто-нибудь объяснить эту эвристическую функцию, например, для следующей компоновки головоломки 4x4, какова эвристическая стоимость X-Y?

1 2 3 4 
5 6 7 8 
9 10 11 12 
0 13 14 15 

(0 указует на пустое пространство)

Answer 1

Как от here и here эвристического XY вычисляются по сумме минимальное количеству столбцов соседних пустых свопов, чтобы получить все плитки в их колонке назначения и минимальное количество смежных смежных строк, чтобы получить все плитки в их строке назначения.

Так что в этой ситуации:

1 2 3 4 
5 6 7 8 
9 10 11 12 
0 13 14 15 

только неуместны плитки 13, 14 и 15, предполагая, что состояние цели является

1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 0 

Так что в этом случае мы должны вычислить в первом количество столбец-свопов, которое должен заполнить пробел, чтобы получить все плитки в правильном положении. Это эквивалентно 3, так как пробел должен перемещаться три раза, чтобы правый столбец находился в правильном положении (и чтобы все плитки были в правильном положении)

Затем мы должны вычислить количество строк поменяет пробел. Это 0 благодаря тому, что все плитки уже находятся на правильной строке.

И наконец h(n) = 3 + 0 = 3.