《人工智能十五数码解读》由会员分享，可在线阅读，更多相关《人工智能十五数码解读（21页珍藏版）》请在金锄头文库上搜索。
1、利用状态空间法解决十五数码游戏问题学号19110227 姓名 季佳辉完成时间 2013年11月#1. 十五数码游戏简介十五数码游戏问题是在4*4方格盘上，放有15个数码，剩下第16个为空，每一 空格其上下左右的数码可移至空格。 问题给定初始位置和目标位置，要求通过一 系列的数码移动，将初始位置转化为目标位置。2. 十五数码游戏问题的状态空间法表示问题的状态空间是指表示问题可能态及关系图，记作三元态（S,F,G） 。它 含三个集合：初始态集S;操作符集F;目标态集G。十五数码问题状态空间法： 初始态 S4 4 = 5,1,2,4,9,6,3,8,13,10,7, 11,0,14,15,12。目标
2、态G4 4 = 1,2,3,4,5, 6,7,8,9,10,11,12,13,14,15,0（0表示空格）。操作符集F=空格左移、上移、右移、下移，实现状态转换。3. 十五数码游戏问题的盲目搜索技术1. 宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优 先搜索。这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前， 必须搜 索完本层的所有节点。其搜索过程如图（1）所示。3.P ”图1宽度优先搜索示意图宽度优先搜索算法如下:（1）（2）（3）(4)(5)把起始节点放到 OPEN表中（如果该起始节点为一目标节点，贝U得到解） 如果OPEN是个空表，则无解，失败退
3、出；否则继续下一步把第一个节点（记作节点n ）从OPEN表移出，并把它放入 CLOSED的 已扩展节点表中扩展节点n。如果没有后继节点，则转向第（2）步把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针如果n的任一个后继节点是个目标节点， 则找到一个解（反向追踪得到从 目标节点到起始节点的路径），成功退出，否则转向第（2）步其流程图如图2所示图2宽度优先算法流程图2、深度优先搜索3）所示。在深度优先搜索中，首先扩展最新产生的（即最深的）节点。深度相等的节点可以 任意排列。首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径 从起始节点向下进行下去；只有当搜索到达一
4、个没有后裔的状态时， 它才考虑另 一条替代的路径。为了避免考虑太长的路径（防止搜索过程沿着无益的路径扩展 下去），往往给出一个节点扩展的最大深度界限。 任何节点如果达到了深度界限， 那么都将把它们作为没有后继节点处理。其搜索过程如图（深度优先搜索示意图深度优先搜索算法如下：如果OPEN为一空表，则无解、失败退出把第一个节点（记作节点n ）从OPEN表移到CLOSED表如果节点n的深度等于最大深度，则转向第（2）步扩展节点n，产生其全部后继节点，并把它们放入OPEN表的前头。如（1）把起始节点S放到未扩展节点的 OPEN表中。如果此节点为一目标节点, 则得到解（2）（3）（4）（5） 果没有后继
5、节点，则转向第（2）步（6）如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目 标节点到起始节点的路径），成功退出；否则，转向第（2）步图2深度优先算法流程图4. 十五数码游戏问题的启发式搜索技术 估价函数:f(n) = g(n) + h(n)是对下列函数的一种估计或近似：f*(n)= g*( n) + h*( n)f*(n):从初始节点到节点n的一条最佳路径的实际代价加上从节点 n到目标节 点的最佳路径的代价之和。g*(n)：从初始节点到节点n之间最小路径的实际代价 h*(n)：从节点n到目标节点的最小代价路径上代价 定义利用与问题有关的知识(即：启发信息)来引导搜索，达到减少
6、搜索范围，降低 问题复杂度的搜索过程称为启发式搜索方法。核心问题： 启发信息应用，启发能力度量和如何获得启发信息。启发信息的强度 强：降低搜索工作量，但可能导致找不到最优解。把起始节点放到OPEN表中，并计算估价函数f(SO)。 如果OPEN是个空表，则没有解，失败退出；否则继续。把OPEN表中的第一个节点(股价函数最小的节点 n),移入CLOSE表0 如果n是目标节点，问题得解，退出。否则继续。判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6) 0 对节点n进行扩展，并对其所有后继节点计算估价函数f (n)的值，并为弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优
7、解。 全局最佳优先搜索：(1) 每个后继节点设置指向n节点的指针。把这些后继节点都送入 OPEN表，然后对 OP EN表中的全部节点按照估价函数值从小到大的顺序排序。转向第步。5. 例子及分析对于每一种算法至少给出两个例子及说明，包括起始状态、目标状态、所走的步数及其对应 操作符、生成的状态总数（0PEN表和CLOSED表的大小）、搜索CPU时间（毫秒）等。 测试的例子12 I61093,4721341L5|111415861034721315111415（深度界限为5）12345 1 7896101213141115123456789101112131415深度优先搜索:(3)任意的初始状态
8、与目标状态。0 1 2 30 2 1 38 9 10 118 9 10 1112 13 14 1512 13 14 15宽度优先搜索:tep 10 2 35 6 79 1 邸 112 13 14 urce =12 35 6 79 10 112 13 14tep 22 B 35 6 715earcli-.dest mat ion01 03&4source:02 03 04 Q5ae 07 Q8 Q9 10 1106 07 08 09 10 1112 13 14 1512 13 14 15giRBFSDebugBFS,exe:itep 510 6 34 2 5 73 9 10 1112 13 14
9、 15ep 42 6 30 5 79 10 1113 14 IS=Step 312 6 34 5 0 75 9 10 1112 13 14 53 , F:BFSDfbugiBFS,ext-回 却n 回0 4泪1 S工4育1 武1理t U Pn 0201009312S 1547365201i16 Pe 1 tr *F;BFSDfbugBFS,ext*S：tep 7 k 1 6 30 2 5 79 10 1112 13 14 1510 0 3r *F:BFSDfbugBFS,ext*tep 11j4 0 1 3 *5679 10 1112 13 14 15Step 120 4 13p 5 6 79
10、 10 1112 13 4 ISpets Ml_o_ps13 14 IS 2 *F：BFSD#tiugBFS.csLtf*I 叵）i 73p0 2tLr厂El坯r g-讨 iTJpuccee&FuLTA*算法:r gu S E RSDE LLDES KTO PA算法D品ugA法.exe2 36 710 11i5?12 13 14 15输入终态=05824912 13 14 151 36 710 11刊始状态：1592 38 7 10 li12 13 14 15Step i148a592 38 7 10 li12 13 14 15Step 21482590 36 710 li12 13 14 1
11、5Step 31486 3 0 710 11259112 13 14 15 T:USERSDELLDESKTOPAg：去D品uRA茸法心bKtep 412 6 34 0 5 7R ? 10 1112 13 14 15=16 p e 0 t fcc6 p e 1 ts 0ECpe its 40036 e i s 400pe it00 4CCa 回 I 3匚回 S2 Ii = T:US E RSDE LLDES KTO PAg：Debugexe恥ep i04 10 32 5 6 78 ? 10 1112 13 14 15Step 114 0 132 5 6 7H ? 10 1112 13 14 15Step 120 4 132 5 6 7S ? 10 1112 13 14 15Step 132 4 13 567H ? 10 1112 13 14 15Step 142 4 135 0 6 7S ? 10 11(2 13 14 15Step 152 0 135 4 6 7a ? 10 1112 13 14 15Step 16B0 2 135
