人工智能 十五数码

《人工智能 十五数码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、利用状态空间法解决十五数码游戏问题学号19110227姓名季佳辉完成时间2013年11月1．十五数码游戏简介十五数码游戏问题是在4*4方格盘上，放有15个数码，剩下第16个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。2．十五数码游戏问题的状态空间法表示问题的状态空间是指表示问题可能态及关系图，记作三元态（Ｓ，Ｆ，Ｇ）。它含三个集合：初始态集Ｓ；操作符集Ｆ；目标态集Ｇ。十五数码问题状态空间法：初始态Ｓ［４］［４］＝｛５，１，２，４，９，６，３，８，１３，１０，７，１１，０，１４，１５，１２｝。

2、目标态Ｇ［４］［４］＝｛１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，０｝（０表示空格）。操作符集Ｆ＝［空格左移、上移、右移、下移］，实现状态转换。3．十五数码游戏问题的盲目搜索技术1.宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。其搜索过程如图（1）所示。SLOMFRPNFFF图1宽度优先搜索示意图1宽度优先搜索算法如下：（1）把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)（2）如果OPEN是个空

3、表，则无解，失败退出；否则继续下一步（3）把第一个节点(记作节点n)从OPEN表移出，并把它放入CLOSED的已扩展节点表中（4）扩展节点n。如果没有后继节点，则转向第(2)步（5）把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针（6）如果n的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第(2)步其流程图如图2所示起始把S放入OPEN表OPEN是否为是失败空表?否把第一个节点n,从OPEN表移出,并把它放入CLOSED表扩展n,把它的后继节点放入OPEN表的末端,提供回到n的指针否是否有

4、任何后继是成功节点为目标节点?图2宽度优先算法流程图22、深度优先搜索在深度优先搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。其搜索过程如图（3）所示。SLOMFRPNFFF图1深度优先搜索示意图深度优先搜索算法如下：（1）把起始节点S放到

5、未扩展节点的OPEN表中。如果此节点为一目标节点，则得到解（2）如果OPEN为一空表，则无解、失败退出（3）把第一个节点(记作节点n)从OPEN表移到CLOSED表（4）如果节点n的深度等于最大深度，则转向第(2)步（5）扩展节点n，产生其全部后继节点，并把它们放入OPEN表的前头。如果没有后继节点，则转向第(2)步（6）如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向第(2)步3起始把S放入OPEN表S是否为目标是成功节点？否OPEN是否为是失败空表?否把OPEN表中的第一个节点n移入CLOSED表是节点

6、n的深度是否等于深度界限？否扩展节点n,把其后裔放入OPEN表的前头否是否有任何后继成功节点为目标节点?图2深度优先算法流程图44．十五数码游戏问题的启发式搜索技术估价函数:f(n)=g(n)+h(n)是对下列函数的一种估计或近似：f*(n)=g*(n)+h*(n)f*(n)：从初始节点到节点n的一条最佳路径的实际代价加上从节点n到目标节点的最佳路径的代价之和。g*(n)：从初始节点到节点n之间最小路径的实际代价h*(n)：从节点n到目标节点的最小代价路径上代价定义利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索

7、方法。核心问题：启发信息应用，启发能力度量和如何获得启发信息。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。全局最佳优先搜索：(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并对其所有