人工智能报告

人工智能课程报告——推箱子小游戏的人工智能寻路学院：姓名：学号：班级：指导教师：人工智能课程报告一．简介推箱子游戏简介经典的推箱子是一个来自日本的古老游戏，目的是在训练你的逻辑思考能力。在一个狭小的仓库中，要求把木箱放到指定的位置，稍不小心就会出现箱子无法移动或者通道被堵住的情况，所以需要巧妙的利用有限的空间和通道，合理安排移动的次序和位置，才能顺利的完成任务。胜利条件就是把所有的箱子都推到目的地。本程序的目标就是利用启发式搜索实现电脑自动推箱子。推箱子游戏地图程序采用手机中的推箱子小游戏的程序，地图总共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);堆的向上(从叶到根)调整，内部使用templateclassNodeintkey(Node*nodes,constint&hash_size,constNode&n);在散列数组中查找节点templateclassNodeintsolve(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.傅京孙,蔡自兴,徐光祐.人工智能及其应用.北京:清华大学出版社,19875.高济,朱淼良,何钦铭.人工智能基础.北京:高等教育出版社,20026.格雷厄姆(GrahamN)著,戎志盛,高育德译.人工智能使机器思维.北京:机械工业出版社,1985