详细介绍如何利用 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 ∗ A^* A∗ 算法是一种常用的高效图搜索算法，用于在静态图中找到从起始节点到目标节点的最短路径。它结合了 D i j k s t r a Dijkstra Dijkstra 算法和 启发式（贪心）搜索算法的思想，通过使用“启发式函数”来控制搜索过程，从而提高大部分场景下的搜索效率。
D i j k s t r a Dijkstra Dijkstra 算法 （一种标号法）是每次优先搜索距离起始节点最近的待搜索节点，常用在带权值的路径搜素问题当中，这是典型的广度优先搜索，该算法能保证找到最短路，也常用在多目标节点或无目标节点的场景（挖宝游戏），但是这类算法在寻路场景下往往效率较低，需要花费大量的时间探索各个方向；启发式（贪心）搜索算法 则恰恰相反，它每次优先探索距离目标节点最近的节点，在无障碍的地图上，该算法效率极高，但如果有障碍，贪心搜索并不能保证找到的路线是最短的，或者遇到像挖宝这种无目标节点的场景则无法计算与目标的距离。
A ∗ A^* A∗ 算法 在考虑探索节点的优先顺序时，既考虑了与起始节点的距离，又考虑了与目标节点的预估距离，即综合考虑：从起始节点出发，经过当前节点到目标节点的总的估计代价（距离），既能保证找到最短路径，又能比广度优先搜索有更高的效率。
2. 利用A*解决8数码问题（含Python代码）
2.1 什么是8数码问题
8数码问题是一个经典的搜索问题。在一个 3 × 3 3\times 3 3×3 的棋盘上，放着数字 1 1 1 到 8 8 8，还有 1 1 1 个位置空着，通过交换空格与相邻位置的数字，来移动空格（只能上下左右），该问题会给出一个初始的棋盘顺序，以及期望的棋盘顺序，问最少移动多少下空格，能将初始顺序改变为目标顺序？
听着是不是有点像华容道
把空格的移动视作是棋盘顺序的移动，且这种对应关系是确定的，因此可以把8数码问题视为一个路径优化问题，每个棋盘顺序是一个节点。那么现在有个关键的问题，就是如何确定棋盘顺序（节点）与棋盘顺序（节点）之间的距离大小呢？ 有两种简单的计算方法：
-
计算两个顺序中，未正确摆放的数字数量，对于目标顺序，该值为 0 0 0，该方法仅关注未摆放正确的数字数量，计算方法简单，但实际中，往往又不是这么回事，相同的错摆数量，确实不同的调整难度，如下例子：
1 , 2 , 3 2 , 3 4 , 5 , → 4 , 5 , 6 7 , 8 , 6 7 , 8 , 1 1, 2, 3\quad\quad \quad\quad2,3\\ 4,5, \quad\,\rightarrow\quad4,5,6\\7,8,6\quad\quad\quad7,8,1 1,2,32,34,5,→4,5,67,8,67,8,1
-
另一个距离公式是所有数字 1 − 8 1-8 1−8 在两个棋盘顺序中的位置距离之和，而对于二维棋盘上数字的位置，可以用一维的索引值表示，也可以用行列坐标表示，例如上面的例子，数字 6 6 6 在左边棋盘的位置可以是 8 8 8，也可以是 ( 2 , 2 )