（人工智能）人工智能报告
人工智能课程方案
——推箱子小游戏的人工智能寻路
学院：
姓名：
学号：
班级：
指导教师：
人工智能课程方案
壹．简介
推箱子游戏简介
经典的推箱子是壹个来自日本的古老游戏，目的是于训练你的逻辑思考能力。于壹个狭
小的仓库中，要求把木箱放到指定的位置，稍不小心就会出现箱子无法移动或者通道被堵住
的情况，所以需要巧妙的利用有限的空间和通道，合理安排移动的次序和位置，才能顺利的
完成任务。胜利条件就是把所有的箱子均推到目的地。本程序的目标就是利用启发式搜索实
现电脑自动推箱子。
推箱子游戏地图
程序采用手机中的推箱子小游戏的程序，地图总共 75张，难度由易到难，搜寻路径的
计算复杂度也会越来越高。每壹张地图均以文本文件的形式存储起来。
地图展示：
（第 1关）（第 35关）
（第 56关）（第 75关）
保存到文本文件中的地图代码：
推箱子中人的行为
人只能够推箱子,不能够拉,而且壹次只能推动壹个。即使是处于目的位置的箱子也能够
推走。
二．基本概念
启发式搜索
考虑壹个普通的图搜索问题：给出初始状态(节点 s)和目标状态(节点 t，能够不止壹个)
以及状态的产生规则，求从 s到 t的壹条路经。搜索过程可描述如下：
1待展开的节点集合(OPEN表)为{s}，已展开的节点集合(CLOSED表)为{}，节点 s的层深为
g(s)=0。
2每次从 OPEN表中取出壹个节点 n，根据规则扩展产生壹组节点 mi，然后把 n放入 CLOSED
表中。节点 mi可能属于下列三种情况之壹：
（1）新的节点，则把 mi的源标记为 n，层深 g(mi)=g(n)+1，且放入 OPEN表中。
（2）已于 OPEN表中存于的节点，且且层深 g(mi)>g(n)+1，说明从 s到 mi且且经由 n的路径
要比先前搜索得到的路径要短。因此，把 mi的源改记为 n，层深 g(mi)=g(n)+1，仍放入 OPEN
表中。
（3）已于 CLOSED表中存于的节点，且且层深 g(mi)>g(n)+1。同理，把 mi的源改记为 n，层
深 g(mi)=g(n)+1，且从 CLOSED表中取出重新放入 OPEN表中，留待以后重新搜索计算 mi的子
节点的层深。
3不断重复上壹步操作，直到满足下列条件之壹：
（1）n==t，搜索成功。
（2）OPEN表为空，搜索失败。
于之上过程中，如何从 OPEN表中选取待扩展的节点是关键。如果每次均选取层深 g(n)
最小的节点，之上过程就是宽度优先搜索；如果每次均选取层深 g(n)最大的节点，之上过程
就是深度优先搜索。启发式搜索算法 A*的思想是，给节点定义壹个评价函数
f(n)=g(n)+h(n)(1)
其中，g(n)是节点的层深，即从 s到 n目前搜索已知的最短路径长度，h(n)是节点 n到
目标节点 t的最短路径长度的估计值，称为启发函数。拥有最小 f(n)值的节点有希望成为从
s到 t的最短路径上的壹个节点，因而被取出且扩展。
启发函数 h(n)具有下列壹些性质(证明略，我也不完全懂)：
如果 h(n)处于从 n到 t的最短路径长度的真实值 h*(n)的下界，即恒有 h(n)<=h*(n)，则算法
A*找到的壹定是从 s到 t的最短路径。此时算法 A*称为算法 A*。
能够想象，h(n)越接近真实值 h*(n)，它所包含的启发信息就越多，搜索所需扩展的节点数
就越少。
如果对所有节点 ni和 nj(其中 nj是 ni的子节点)均有 h(ni)-h(nj)<=1，则称启发函数 h(n)满
足单调限制条件。此时，算法 A*于选取节点 n进行扩展时，必有 g(n)==g*(n)，于搜索过程
中不会出现把 mi从 CLOSED表中取出重新放入 OPEN表的情况。
三．算法的设计和实施
推箱子游戏模块
程序中定义的四个函数：
intorderDown(NodeInfo*infos,int*opens,constint&open_used,introot);,堆的向下(从根
到叶)调整，内部使用
intorderUp(NodeInfo*infos,int*opens,constint&open_used,intleaf);,堆的向上(从叶到
根)调整，内部使用
template<classNode>intkey(Node*nodes,constint&hash_size,constNode&n);,于散列数
组中查找节点
template<classNode>intsolve(Node*nodes,inthash_size,Nodes);,搜索函数，程序的入口
基于可重用性的考虑，搜索函数 solve被定义为模板函数，它操作的对象是壹个表示节
点的模板类。节点类要求具有被搜索函数使用的壹些基本接口，这些接口描述了节点的基本
行为和属性，而节点的具体意义(比如表示推箱子的某个状态)则隐藏于类的实现细节中。节
点类的基本接口如下：
intfrom;,节点的源，返回目标路径时使用
Node();,空节点的构造函数
intpossibleMoves()const;,可能的扩展节点数
intmove(intsw);,按第 sw种扩展方式改变节点
inth()const;,启发函数
intisTarget()const;,判断节点是否目标节点
intisNull()const;,判断节点是否空节点
inthash()const;,散列函数
friendintoperator==(constNode&left,constNode&right);,判断俩个节点是否同壹
voidoutput()const;,输出
为了提高速度，节点的存储和查找使用开地址散列，使用简单的线性探测解决冲突。程
序中的 Nodenodes[]和 NodeInfoinfos[]是且列的俩个散列数组，分别存储所有已展开的节
点和节点的附加信息(f值和于 OPEN表中的位置)。key根据节点的散列函数 hash()于散列数
组中查找或分配节点。
OPEN表实际上是壹个优先队列，因而采用堆的方式实现。程序中的 intopens[]是以数
组(完全二叉树)存储的堆，数组元素表示节点于散列数组中的位置，最小 f值的节点能够于
堆的根即 opens[0]处中给出。orderDown和 orderUp是调整堆的需要。
推箱子
应用通用程序求解推箱子问题，关键是节点类的实现。
状态的划分
推箱子的状态由人和箱子的位置决定。考虑到人能够于墙壁和箱子围成的连通区域内任
意行走而不会对局面产生实质性的影响，规定人必须位于他所处的连通区域的左上角。考虑
到箱子的全同性，箱子的坐标应从小到大排序。这些均于构造函数 Box()或者节点扩展函数
move(sw)中完成。这时，判断俩个状态是否相等只需分别比较每个箱子和人的坐标是否相等
即可。
节点的扩展
每个箱子能够推向四个方向，因此总的可能的扩展节点数是箱子数的四倍。考虑到人的
可到达范围(way[])的限制，某些箱子的某些方向(push_directions[])是不可到达的。另外，
地图中仍存于壹些“死位置”(dead_positions[])，比如墙角、俩个箱子且列于墙边等等。
仍有，箱子的背后可能是墙壁或者另壹个箱子。这些不可能的情况均能够于节点扩展函数
move(sw)中予以拒绝。
启发函数
能够计算所有箱子离最近的目标的距离之和作为启发函数 h()的返回值。不难见出，此
定义的启发函数满足算法 A*的下界条件，因而找到的目标路径壹定是最优解。
A*算法的伪代码如下：
创建俩个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算起点的估价值;
将起点放入 OPEN表;
while(OPEN!=NULL)
{
从 OPEN表中取估价值 f最小的节点 n;
if(n节点==目标节点){
break;
}
for(当前节点 n的每个子节点 X)
{
算 X的估价值;
if(XinOPEN)
{
if(X的估价值小于 OPEN表的估价值){
把 n设置为 X的父亲;
更新 OPEN表中的估价值;//取最小路径的估价值
}
}
if(XinCLOSE){
if(X的估价值小于 CLOSE表的估价值){
把 n设置为 X的父亲;
更新 CLOSE表中的估价值;
把 X节点放入 OPEN//取最小路径的估价值
}
}
if(Xnotinboth){
把 n设置为 X的父亲;
求 X的估价值;
且将 X插入 OPEN表中;//仍没有排序
}
}//endfor
将 n节点插入 CLOSE表中;
按照估价值将 OPEN表中的节点排序;//实际上是比较 OPEN表内节点 f的大小，从最小路径
的节点向下进行。
}//endwhile(OPEN!=NULL)
保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；
哈希函数
能够将所有箱子的坐标移位相加再平方取中，得到哈希函数 hash()的返回值。
之上是我的推箱子程序的主要思路，如果你感兴趣，请进壹步阅读我的程序。(可能不太好
读。)
四．调试分析
我的程序于电脑配置较低的条件下(需要根据情况修改程序中 HASH_SIZE和 HEAP_SIZE
的设置)基本上能够解六个箱子之内的关，八到十个箱子的关或者特别复杂的六个箱子的关
解起来会比较费劲，特别复杂的八个箱子之上的关基本上就解不了了。启发式搜索虽然能够
于很大程度上缩小搜索空间，可是无法根本解决指数爆炸的问题。目前我能想到壹些改进措
施是：
如果不苛求最优解，能够适当增大上文提到的启发函数值。事实上，所有箱子离最近的
目标的距离之和和实际到达目标所需的步数之间有很大的差距，因而扩展生成了许多无关的
节点。增大启发函数值，例如人为的给它乘以二，以牺牲最优解为代价更快地到达目标。
用另壹种方式计算每个箱子到达目标所需的步数。考虑壹个箱子紧挨着壹个目标的情况，因
为地图和人的位置关系，箱子很可能根本无法壹步推到目标上，这时简单的以箱子和目标的
距离计算就不太合适了。壹种可能的办法是，于正式搜索之前先搜索得出壹个箱子从不同的
位置出发推到目标所需的步数。不过，这点改进对搜索的性能能有多大提高仍是壹个未知数。
删除搜索树上的“死”分枝。这点属于对启发式搜索通用程序的改进，和推箱子无关。
可是测试表明，于推箱子的搜索过程中，“死”分枝的比例壹般只占总节点数的壹半左右。
因此，这点改进带来的效果估计也不会很明显。
五．结论（包括结果）
结论：启发式搜索能够比较好的解决推箱子问题。
运行结果：
点击运行程序，显示如下图：
可选择关卡，选择完关卡后点击“确定”，然后点击“演示”，则程序进入自动演示状态，每
点击壹下鼠标，电脑便会自动移动壹步，如下图：
当显示“演示完毕”时，演示结束，电脑便会给出最终结果：
六．心得体会
通过这次上机实习，不仅让我对人工智能有了壹定的了解，更重要的仍让我学会了、或
者说是验证了“做事壹定要有次序和对事物的总体把握”这句话。开始我壹味的进行调试，
急切的想侥幸调试出来，但由于没有进行深入的考虑，我调试了很久均没没有成功，我仔细
的分析材料，于原由的基础上我进行了改正，终于调试成功了，虽然这个过程仍是经过了壹
翻努力，当然汗水仍是留的很值，这次编程方案，不仅让我对人工智能这门课程有了更深入
的研究、对很多重要的概念有了巩固和掌握，仍给了我今后做事的启示。做事要塌实，不能
想着壹步登天，要有计划，有目的的进行做事。我们应该认真找到自己的缺点且且及时改正。
此时此刻，我心里多了些成就感。这是我整个学习过程中的壹次经验、壹次总结，我相信它
肯定会给我今后的学习有所启示和指导作用。
七．参考文献
1．C++程序设计实践教程第 2版，吴乃陵李海文，高等教育出版社
2．深入浅出 MFC第 2版，候俊杰，华中科技大学出版社
3．VisualC++从入门到实践，葛亮，清华大学出版社
4.傅京孙,蔡自兴,徐光祐.人工智能及其应用.北京:清华大学出版社,1987
5.高济,朱淼良,何钦铭.人工智能基础.北京:高等教育出版社,2002
6.格雷厄姆(GrahamN)著,戎志盛,高育德译.人工智能使机器思维.北京:机械工业出版
社,1985
