N-Puzzle 上的 X-Y 启发式

Question

首先我看到了这个答案，是的，它解释了 X-Y 启发式算法，但是示例板太简单了，我无法理解一般的启发式算法。

X-Y heuristic function for solving N-puzzle

有人可以用这个例子解释 X-Y 启发式吗？

8 1 2
7 3 6
0 5 4

Answer 1

该算法由 2 个独立的部分组成 - 行和列。

1) 行。将输入矩阵按行划分 - 每行的元素进入单独的集合。

(1, 2, 8) - (3, 6, 7) - (0, 4, 5)

唯一可用的移动是将 0 与相邻集合中的元素交换。 当每个元素都在正确的集合中时，你就完成了。

交换 0 和 7 -> (1, 2, 8) - (0, 3, 6) - (4, 5, 7)

交换 0 和 8 -> (0, 1, 2) - (3, 6, 8) - (4, 5, 7)

交换 0 和 3 -> (1, 2, 3) - (0, 6, 8) - (4, 5, 7)

交换 0 和 4 -> (1, 2, 3) - (4, 6, 8) - (0, 5, 7)

交换 0 和 8 -> (1, 2, 3) - (0, 4, 6) - (5, 7, 8)

交换 0 和 5 -> (1, 2, 3) - (4, 5, 6) - (0, 7, 8)

所需步骤数 = 6。

2) 与列类似。您开始于：

(0, 7, 8) - (1, 3, 5) - (2, 4 ,6)

然后

(1, 7, 8) - (0, 3, 5) - (2, 4, 6)

(0, 1, 7) - (3, 5, 8) - (2, 4, 6)

(1, 3, 7) - (0, 5, 8) - (2, 4, 6)

(1, 3, 7) - (2, 5, 8) - (0, 4, 6)

(1, 3, 7) - (0, 2, 5) - (4, 6, 8)

(0, 1, 3) - (2, 5, 7) - (4, 6, 8)

(1, 2, 3) - (0, 5, 7) - (4, 6, 8)

(1, 2, 3) - (4, 5, 7) - (0, 6, 8)

(1, 2, 3) - (0, 4, 5) - (6, 7, 8)

(1, 2, 3) - (4, 5, 6) - (0, 7, 8)

所需步骤数 = 10

3) 总步数：6 + 10 = 16