人工智能报告

《人工智能报告》由会员分享，可在线阅读，更多相关《人工智能报告（10页珍藏版）》请在金锄头文库上搜索。

1、人工智能报告推箱子小游戏的人工智能寻路学院：姓名：学号：班级： 指导教师:人工智能课程申报一简介推箱子游戏简介推箱子游戏地图法度榜样采取手机中的推箱子小游戏的法度榜样，地图总共75 张，难度由易到难，搜 寻路径的运算复杂度也会越来越高。每一张地图都以文本文件的情势储备起来。储存到文本文件中的地图代码：推箱子中人的行动人只能够推箱子, 弗成以拉, 同时一次只能推动一个。即使是处于目标地位的箱子也能 够推走。二全然概念启发式搜刮推敲一个通俗的图搜刮问题：给出初始状况(节点S)和目标状况(节点t,能够不止一 个)以及状况的产生规矩，求从S到t的一条路经。搜刮过程可描述如下：1待展开的节点集合(OPE

2、N表)为s，已展开的节点集合(CLOSED表)为，节点s的层 深为 g(S) = 0。2每次从OPEN表中掏出一个节点n,依照规矩扩大产生一组节点m ,然后把n放入iCLOSED表中。节点m 可能属于下列三种情形之一：i(1) 新的节点，则把m 的源标记为n,层深g(m) = g(n) + 1,并放入OPEN表中。ii(2) 已在OPEN表中存在的节点，同时层深g(m) g(n) + 1,说明从s到m 同时经ii由n的路径要比先前搜刮获得的路径要短。是以，把m 的源改记为n,层深g(m) =g(n)ii+ 1,仍放入OPEN表中。(3) 已在CLOSED表中存在的节点，同时层深g(m ) g(

3、n) + 1同理，把m 的源改记ii为n,层深g(m) = g(n) + 1,并从CLOSED表中掏出从新放入OPEN表中，留待今后从i新搜刮运算 mi 的子节点的层深。i 3赓续反复上一步操作，直到知足下列前提之一：(1) n = t,搜刮成功。(2) OPEN表为空，搜刮掉败。在以上过程中，若何从OPEN表中拔取待扩大的节点是关键。假如每次均拔取层深g(n) 最小的节点，以上过程确实是宽度优先搜刮；假如每次均拔取层深g(n)最大年夜的节点， 以上过程确实是深度优先搜刮。启发式搜刮算法A*的思惟是，给节点定义一个评判函数 f(n) = g(n) + h(n) (1)个中，g(n)是节点的层深

4、，即从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)

5、= 1，则称i j j i i j启发函数h(n)知足单调限制前提。现在，算法A*在拔取节点n进行扩大时，必有g(n)= g*(n)，在搜刮过程中可不能显现把m 从CLOSED表中掏出从新放入OPEN表的情形。i三算法的设计与实施推箱子游戏模块推箱子游戏法度榜样中定义的四个函数：int orderDown(NodeInfo *infos, int *opens, const int &open_used, int root);堆的向下(从根到叶)调 剂，内部应用int orderUp(NodeInfo *infos, int *opens, const int &open_used, int

6、leaf);堆的向上(从叶到根)调 剂，内部应用template int key(Node *nodes, const int &hash size, const Node &n);在散列数组中查找节点template int solve(Node *nodes, int hash_size, Node s);搜刮函数，法度榜样的进 口基于可重用性的推敲，搜刮函数solve被定义为模板函数，它操作的对象是一个表示节点的模板类。节点类要求具有被搜刮函数应用的一些全然接口，这些接口描述了节点的全然行动和属性，而节点的具体意义(比如表示推箱子的某个状况)则隐藏在类的实现细节 中。节点类的全然接口如下

7、：int from;节点的源，返回目标路径时 应用Node();空节点的构造函数int possibleMoves() const;可能的扩大节点数int move(int sw);按第sw种扩大方法改变节 占八、int h() cons t;启发函数int isTarget() const;确信节点是否目标节点int isNull() const;确信节点是否空节点int hash() cons t;散列函数friend int operator = (const Node &left, const Node &right);确信两个节点是否同一void output() const;输出为

8、了进步速度，节点的储备和查找应用开地址散列，应用简单的线性探测解决冲突。 法度榜样中的Node nodes和Nodeinfo infos是并列的两个散列数组，分别储备所有 已展开的节点和节点的附加信息(f值和在OPEN表中的地位)。key依照节点的散列函数 hash()在散列数组中查找或分派节点。OPEN表实际上是一个优先队列，因而采取堆的方法实现。法度榜样中的intopens 是以数组(完全二叉树)储备的堆，数组元素表示节点在散列数组中的地位，最小f值的节 点能够在 堆的根即opens0处中给出。orderDown和orderUp是调剂堆的须要。 推箱子 应用通用法度榜样求解推箱子问题，关键

9、是节点类的实现。状况的划分推箱子的状况由人和箱子的地位决定。推敲到人能够在墙壁和箱子围成的连通区域内随 便率性行走而可不能对局面产生本质性的阻碍，规定人必须位于他所处的连通区域的左上 角。推敲到箱子的全同性，箱子的坐标应从小到大年夜排序。这些都在构造函数Box()或 者节点扩大函数move(sw)中完成。这时，确信两个状况是否相等只需分别比较每个箱子 和人的坐标是否相等即可。节点的扩大每个箱子能够推向四个偏向，是以总的可能的扩大节点数是箱子数的四倍。推敲到人的 可达到范畴(way)的限制，某些箱子的某些偏向(push_directions)是弗成达到的。别的， 地图中 还存在一些“逝世地位”(

10、dead_positions),比如墙角、两个箱子并列在墙边等 等。还有，箱子的背后可能是墙壁或者另一个箱子。这些弗成能的情形都能够在节点扩大 函数move(sw)中予以拒绝。启发函数能够运算所有箱子离比来的目标的距离之和作为启发函数h()的返回值。不难看出， 此定义的启发函数知足算法A*的下界前提，因而找到的目标路径必定是最优解。A*算法的伪代码如下：创建两个表，OPEN表储存所有已生成而未考察的节点，CLOSED表中记录已拜望过的节点。算起点的估价值;将起点放入OPEN表；while(OPEN!=NULL)从OPEN表中取估价值f最小的节点n;if(n节点=目标节点)break;for(当

11、前节点n的每个子节点X)算X的估价值；if(X in OPEN)if( X的估价值小于OPEN表的估价值)把n设置为X的父亲；更新OPEN表中的估价值；/取最巷子径的估价值if(X inCLOSE) if( X的估价值小于CLOSE表的估价值)把n设置为X的父亲；更新CLOSE表中的估价值；把X节点放入OPEN /取最巷子径的估价值if(X not inboth)把n设置为X的父亲；求X的估价值；并将X插入OPEN表中；/还没有排序/end for将n节点插入CLOSE表中；按照估价值将OPEN表中的节点排序；/实际上是比较OPEN表内节点f的大年夜小， 从最巷子径的节点向下进行。/end w

12、hile(OPEN!=NULL) 储存路径，即从终点开端，每个节点沿着父节点移动直至起点，这确实是你的路 径；哈希函数能够将所有箱子的坐标移位相加再平方取中，获得哈希函数hash（）的返回值。以上是我的推箱子法度榜样的重要思路，假如你感爱好，请进一步扫瞄我的法度榜样。（可 能不太好读。）四调试分析我的法度榜样在电脑设备较低的前提下（须要依照情形修改法度榜样中HASH_SIZE和 HEAP_SIZE的设置）全然上能够解六个箱子之内的关，八到十个箱子的关或者专门复杂的六 个箱子的关解起来会比较费劲，专门复杂的八个箱子以上的关全然上就解不了了。启发式 搜刮因此能够在专门大年夜程度上缩小搜刮空间，然则

13、无法全然解决指数爆炸的问题。今 朝我能想到一些改进方法是：假如不苛求最优解，能够恰当增大年夜上文提到的启发函数值。事实上，所有箱子离比 来的目标的距离之和与实际达到目标所需的步数之间有专门大年夜的差距，因而扩大生成 了专门多无关的节点。增大年夜启发函数值，例如工资的给它乘以二，以就义最优解为价 值更快地达到目标。用另一种方法运算每个箱子达到目标所需的步数。推敲一个箱子紧挨着一个目标的情形，因 为 地图和人的地位关系，箱子专门可能全然无法一步推到目标上，这时简单的以箱子和目 标的距离运算就不太合适了。一种可能的方法是，在正式搜刮之前先搜刮得出一个箱子从 不合的地位动身推到目标所需的步数。只是，这

14、点改进对搜刮的机能能有多大年夜进步照 样一个未知数。删除搜刮树上的“逝世”分枝。这点属于对启发式搜刮通用法度榜样的改进，与推箱子 无关。然则测试注解，在推箱子的搜刮过程中，“逝世”分枝的比例一样只占总节点数的 一半阁下。是以，这点改进带来的后果估量也可不能专门明显。五结论（包含成果）结论：启发式搜刮能够比较好的解决推箱子问题。运行成果：点击运行法度榜样，显示如下图：s12Xx当前关卡12可选择关卡，选择完关卡后点击“确信”，然后点击“演示”，则法度榜样进入主动演示状况 每点击一下鼠标，电脑便会主动移动一步，如下图：总共眄个关卡W(Delete)退出（臨J演示.(End)透其卡上一关 下一关(P agcllp)(P 呂匕 Down)确定(Enter)重玩本黄（Hoede；T12IIX当显示“演示完毕”时，演示停止，电脑便会给出最终成果：重顼津：共曲皿）撤销（Delete）退出（氐匚当前关卡比总共羽个关卡选关卡上一关 下一关 (PageUp) (PageDown)W (Enter)滴示LEnd)当前关卡12总共T5个并卡重玩本关CHamc)|撇幫(DeLete.)域示田ni)逃关卡上一关 ,下一关.(.PageUp) (Pag.rD own|n确定、(Enter)退.出(Esc)XXX六心得领会经由过程此次上机练习，不