人工智能课程报告——推箱子小游戏的人工智能寻路学院：姓名：学号：班级：指导教师：人工智能课程报告一．简介推箱子游戏简介经典的推箱子是一个来自日本的古老游戏，目的是在训练你的逻辑思考能力。在一个狭小的仓库中，要求把木箱放到指定的位置，稍不小心就会出现箱子无法移动或者通道被堵住的情况，所以需要巧妙的利用有限的空间和通道，合理安排移动的次序和位置，才能顺利的完成任务。胜利条件就是把所有的箱子都推到目的地。本程序的目标就是利用启发式搜索实现电脑自动推箱子。推箱子游戏地图程序采用手机中的推箱子小游戏的程序，地图总共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);堆的向上(从叶到根)调整，内部使用templateintkey(Node*nodes,constint&hash_size,constNode&n);在散列数组中查找节点templateintsolve(Node*nodes,inthash_size,Nodes);搜索函数，程序的入口基于可重用性的考虑，搜索函数solve被定义为模板函数，它操作的对象是一个表示节点的模板类。节点类要求具有被搜索函数使用的一些基本接口，这些接口描述了节点的基本行为和属性，而节点的具体意义(比如表示推箱子的某个状态)则隐藏在类的实现细节中。节点类的基本接口如下：intfrom;节点的源，返回目标路径时使用Node();空节点的构造函...
