详细介绍如何利用 A star（A*）算法解决8数码问题

文章目录

• 1. A star（A*）算法简介
• 2. 利用A*解决8数码问题（含Python代码）
• • 2.1 什么是8数码问题
  • 2.2 A*算法中的开放列表和关闭列表
  • 2.3 A*算法解决8数码问题过程
  • • 2.3.1 计算节点（棋盘顺序）间距离
    • 2.3.2 交换数字生成新的节点
    • 2.3.3 A*主求解程序

---

1. A star（A*）算法简介

$A^{\ast }$ 算法是一种常用的高效图搜索算法，用于在静态图中找到从起始节点到目标节点的最短路径。它结合了 $Dijkstra$ 算法和 启发式（贪心）搜索算法的思想，通过使用“启发式函数”来控制搜索过程，从而提高大部分场景下的搜索效率。

$Dijkstra$ 算法 （一种标号法）是每次优先搜索距离起始节点最近的待搜索节点，常用在带权值的路径搜素问题当中，这是典型的广度优先搜索，该算法能保证找到最短路，也常用在多目标节点或无目标节点的场景（挖宝游戏），但是这类算法在寻路场景下往往效率较低，需要花费大量的时间探索各个方向；启发式（贪心）搜索算法 则恰恰相反，它每次优先探索距离目标节点最近的节点，在无障碍的地图上，该算法效率极高，但如果有障碍，贪心搜索并不能保证找到的路线是最短的，或者遇到像挖宝这种无目标节点的场景则无法计算与目标的距离。

$A^{\ast }$ 算法 在考虑探索节点的优先顺序时，既考虑了与起始节点的距离，又考虑了与目标节点的预估距离，即综合考虑：从起始节点出发，经过当前节点到目标节点的总的估计代价（距离），既能保证找到最短路径，又能比广度优先搜索有更高的效率。

2. 利用A*解决8数码问题（含Python代码）

2.1 什么是8数码问题

8数码问题是一个经典的搜索问题。在一个 $3\times 3$ 的棋盘上，放着数字 $1$ 到 $8$，还有 $1$ 个位置空着，通过交换空格与相邻位置的数字，来移动空格（只能上下左右），该问题会给出一个初始的棋盘顺序，以及期望的棋盘顺序，问最少移动多少下空格，能将初始顺序改变为目标顺序？

听着是不是有点像华容道

把空格的移动视作是棋盘顺序的移动，且这种对应关系是确定的，因此可以把8数码问题视为一个路径优化问题，每个棋盘顺序是一个节点。那么现在有个关键的问题，就是如何确定棋盘顺序（节点）与棋盘顺序（节点）之间的距离大小呢？ 有两种简单的计算方法：

1. 计算两个顺序中，未正确摆放的数字数量，对于目标顺序，该值为 $0$，该方法仅关注未摆放正确的数字数量，计算方法简单，但实际中，往往又不是这么回事，相同的错摆数量，确实不同的调整难度，如下例子：

   $$\begin{gathered} 1,2,32,3 \\ 4,5,\to 4,5,6 \\ 7,8,67,8,1 \end{gathered}$$

2. 另一个距离公式是所有数字 $1-8$ 在两个棋盘顺序中的位置距离之和，而对于二维棋盘上数字的位置，可以用一维的索引值表示，也可以用行列坐标表示，例如上面的例子，数字 $6$ 在左边棋盘的位置可以是 $8$，也可以是 ( 2 , 2 )