使用 A 算法解决 8-puzzle 问题

问题定义 ：

8 拼图是一个由 3 x 3 网格（包含 9 个方格）组成的简单游戏。其中一个方块是空的。目标是移动到不同位置的方块并使数字显示在目标状态中。

给定 8-puzzle 游戏的初始状态和最终状态，找到从最初状态到达最终状态的最具成本效益的路径。

初始状态 ：

_ 1 3
4 2 5
7 8 6

最终状态 ：

1 2 3
4 5 6
7 8 _

启发式假设 ：

让我们考虑当前和最终状态之间的曼哈顿距离作为此问题陈述的启发式。

h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
      p and q are cell co-ordinates in the final state

总成本函数 ：

所以总费用函数 f(n) 由下式给出，

f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state

示例问题的解决方案 ：

首先，我们找到从初始状态到达最终状态所需的启发式值。成本函数 g(n)= 0，因为我们处于初始状态

h(n) = 8

获得上述值，因为当前状态下的 1 与最终状态下的 1 相距 1 个水平距离。同样适用于 2，5，6。_ 距离 2 个水平距离，距离 2 个垂直距离。所以 h(n) 的总值是 1 + 1 + 1 + 1 + 2 + 2 = 8.总成本函数 f(n) 等于 8 + 0 = 8。

现在，找到了可以从初始状态到达的可能状态，并且我们可以将 _ 向右或向下移动。

所以移动这些动作后得到的状态是：

1 _ 3    4 1 3
4 2 5    _ 2 5
7 8 6    7 8 6
 (1)      (2)

再次使用上述方法为这些状态计算总成本函数，结果分别为 6 和 7。我们选择了最低成本的状态，即状态（1）。下一个可能的移动可以是左，右或下。我们不会像之前在那个状态那样向左移动。所以，我们可以向右或向下移动。

我们再次找到从（1）获得的状态。

1 3 _    1 2 3
4 2 5    4 _ 5
7 8 6    7 8 6
 (3)      (4)

（3）导致成本函数等于 6，（4）导致 4.此外，我们将考虑（2）之前获得的成本函数等于 7.从中选择最小值导致（4）。下一个可能的移动可以是左，右或下。我们获得状态：

1 2 3    1 2 3    1 2 3
_ 4 5    4 5 _    4 8 5
7 8 6    7 8 6    7 _ 6
 (5)      (6)      (7)

对于（5），（6）和（7），我们分别得到等于 5,2 和 4 的成本。此外，我们以前的状态（3）和（2）分别为 6 和 7。我们选择了最小成本状态，即（6）。接下来可能的移动是 Up，Down 和 clear Down 会导致我们进入最终状态，导致启发式函数值等于 0。