人工智能十五数码解读

1、利用状态空间法解决十五数码游戏问题学号19110227 姓名 季佳辉完成时间 2013年11月161. 十五数码游戏简介十五数码游戏问题是在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 1

9、4 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 7

10、9 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

11、15Step 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

12、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 4 6 78 ? 10 1112 13 14 151anv key to continuer T:US E RSDE LLDES KTO PA算法WbugXAS法.exe6. 体会与致谢这次作业让我的编程能力有了很大的提高，查阅资料等能力也有很大的提

13、 升。让我对人工智能技术有了进一步的认识。 在解决问题和算法设计上的能力也 极大地提高。这次作业我花了近7天的事件收集相关材料阅读并消化，并写出宽 度遍历，深度遍历搜索算法。这里我也要谢谢我朋友的帮助，在我没有思路的情 况下帮助我，给我提供思路。通过这次实验更加熟悉状态空间的宽度优先搜索、 深度优先搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。学到了不少知识。7.实验程序简单说明1. 宽度优先遍历：我没有用随机产生初始节点的方法，而是由用户自己输入。2. 深度优先遍历：节点数据由用户自己输入。3. 启发式搜索：节点数据由用户自己输入。读书的好处1、行万里路，读万卷书。2、书山有路勤为径，学海无涯苦作舟 3、读书破万卷，下笔如有神达尔文4、我所学到的任何有价值的知识都是由自学中得来的。5、少壮不努力，老大徒悲伤6、黑发不知勤学早，白首方悔读书迟。一一颜真卿 7、宝剑锋从磨砺出，梅花香自苦寒来。8、读书要三到：心到、眼到、口到 9、玉不琢、不成器，人不学、不知义。10、一