人工智能大作业报告
——A*算法解决十五数码问题
学号：
姓名：
目录
一、问题描述
1.1 十五数码问题描述
1.2 补充测试用例
二、算法分析
2.1 状态和操作符
2.1.1 棋局状态
2.1.2 操作规则
2.1.3 操作符
2.2 A*算法中的启发式函数
2.2.1 A*算法启发式函数概述
2.2.2 几种启发式函数
2.3 排序去重算法
2.3.1 堆排序
2.3.2 哈希表去重
2.4 算法步骤
三、运行结果
3.1 基本运行结果
3.2 启发式函数对运行结果影响
3.2.1 启发函数1
3.2.2 启发函数2
3.2.3 启发函数3
3.3 操作顺序对运行结果影响
3.3.1 操作符1
3.3.2 操作符2
3.4 补充算例运行结果
3.4.1 补充算例Test2
3.4.2 补充算例Test3
四、总结分析
4.1 启发式函数分析
4.2 其他算法分析
五、附录
5.1 Python Code
5.2 完整运行结果
一、问题描述
1.1 十五数码问题描述
在4×4的棋盘上，摆有十五个棋子，每个棋子上标有1至15的某一数字。棋盘中留有一个空格，空格用0
来表示。空格周围的棋子可以移到空格中（即空格可以上下左右移动）。要求解的问题是：给出一种初
始布局：[11, 9, 4, 15, 1, 3, 0, 12, 7, 5, 8, 6, 13, 2, 10, 14]和目标布局：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 0]，找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
1.2 补充测试用例
为验证算法，仅用一个测试用例不足以证明程序的正确性，以下在题目给定的测试用例外，再设置3个
用例对程序进行测试：
Test0 = [11, 9, 4, 15, 1, 3, 0, 12, 7, 5, 8, 6, 13, 2, 10, 14]（题目给定）
Test1 = [0, 5, 1, 7, 2, 11, 4, 3, 9, 13, 6, 15, 10, 14, 12, 8]
Test2 = [11, 9, 4, 15, 1, 3, 12, 6, 7, 5, 8, 0, 13, 2, 10, 14]
Test3 = [5, 3, 7, 8, 1, 2, 11, 4, 13, 6, 15, 14, 0, 10, 9, 12]
二、算法分析
2.1 状态和操作符
2.1.1 棋局状态
将棋局的每一步状态保存到一个二维数组中，例如初始状态：[[11, 9, 4, 15], [1, 3, 0, 12], [7, 5, 8, 6],
[13, 2, 10, 14]]。
2.1.2 操作规则
将空格周围的棋子可以移到空格中的操作，等价为可以将空格（即0）上下左右移动的操作，每次只能
移动一步（即每次移动代价D=1）。
2.1.3 操作符
定义0在一个二维数组中移动的操作符，Operations = [[-1, 0], [0, -1], [1, 0], [0, 1]]。[1, 0]表示0向右移
动，[0, 1]表示0向上移动，-1则表示相反的方向。
2.2 A*算法中的启发式函数
2.2.1 A*算法启发式函数概述
启发式搜索是利用知识来引导搜索过程的，达到减少搜索范围的目标，使得尽量先走“最有希望的方
向”，从而降低问题复杂度。这里就是要根据知识，设计启发函数。
对于A算法中，对于一个节点是从起始节点到达该节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合
起来对节点进行评价的，即
f(n)=g(n)+h(n)
g(n)和h(n)，尤其是h(n)该如何选择呢，选择如果超过实际代价太多，也就是太强，可能会找不到解；太
弱就会在搜索过程中，扩展一些多余的节点，对于具体问题要根据具体知识进行设计。这里定义如果对
于所有的n都有h(n)≤h* (n)，也称h(n)为h* (n)的下界，则是一种相对保守的搜索，但是这样是可纳的。
采用h*(n)的下界h(n)为启发函数的A算法，称为A* 算法。
在设计估价函数时，要尽可能的使得和h(n)逼近h*(n)，但又不超过h*(n)，下面以次为设计依据，设计了
启发函数。
2.2.2 几种启发式函数
1）估价函数①：f(n)=d(n)+h(n)
d(n)为n的深度；
h(n)为不在位的棋子数。
这样h(n)≤h*(n)，是满足A* 算法的限制条件，所有一定能找到最优解，但是这样设计估价函数并不是最
优的。
2）估价函数②：f(n)=d(n)+h(n)
d(n)为n的深度；
h(n)为不在位的棋子与其目标位置的距离的绝对值之和。
这样h(n)≤h*(n)，也是满足A* 算法的限制条件；1）中的h(n)是不在位的棋子数，不够贴切，错误选用节
点加以扩展，而这里的h(n)是更接近于h*(n)的，其值是节点n与目标状态节点相比较，每个错位棋子在
假设不受阻拦的情况下，移动到目标状态相应位置所需走步的总和。h(n)不仅考虑了错位因素，还考虑
了错位的距离（移动次数），也就是启发性信息更多了。
3）估价函数③：f(n)=d(n)+h(n)
d(n)为n的深度；
h(n)为零。
这样相当于广度搜索，与以上两种方法进行对比。
2.3 排序去重算法
2.3.1 堆排序
在实际程序设计中，因为需要对大量的节点进行排序，如果排序算法时间复杂度高，会严重影响算法的
运行速度，这里通过堆排序的方法，先将OPEN表转换为堆结构，减小排序算法的时间复杂度。
1）堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。堆排序就是利用堆这种数据结构而
设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也
是不稳定排序。
2）堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节
点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样
会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
3）Python中的堆排序：Python的标准库中提供了堆排序模块heapq。对于储存节点的OPEN表可以通
过：heap.heapify(OPEN)直接转换为堆结构，heapq.heappush(state)将子节点push到堆中，
heapq.heappop(OPEN)可以直接将子节点中估值最小的节点pop出，优先进行判断和扩展。
2.3.2 哈希表去重
在搜索过程中，可能会生成相同状态的节点，如果该节点之前就已经在OPEN表中出现过，那么再对这
个节点进行扩展和判断是没有意义的，故需要一个方法对加入OPEN的节点进行去重。
1）哈希算法（Hash Algorithm）：又称散列算法，杂凑算法，是一种从任意文件中创造小的数字「指
纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件
的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改
变，从而告诉文件使用者当前的文件已经不是你所需求的文件。
2）Python中的hash转换：对于节点状态，可以先将节点状态转换为哈希值hash(str(state))，存入一个
集合(hashtable)中，在生成节点后先对节点进行判断，如果之前出现过，那么直接忽略；反之，加入
OPEN表中。
2.4 算法步骤
程序中A*算法部分的步骤如下：
