搜索
1利用状态空间法解决十五数码游戏问题学号19110227姓名季佳辉完成时间2013年11月1．十五数码游戏简介十五数码游戏问题是在4*4方格盘上，放有15个数码，剩下第16个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。2．十五数码游戏问题的状态空间法表示问题的状态空间是指表示问题可能态及关系图，记作三元态（Ｓ，Ｆ，Ｇ）。它含三个集合：初始态集Ｓ；操作符集Ｆ；目标态集Ｇ。十五数码问题状态空间法：初始态Ｓ［４］［４］＝｛５，１，２，４，９，６，３，８，１３，１０，７，１１，０，１４，１５，１２｝。目标态Ｇ［４］［４］＝｛１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，０｝（０表示空格）。操作符集Ｆ＝［空格左移、上移、右移、下移］，实现状态转换。3．十五数码游戏问题的盲目搜索技术1.宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。其搜索过程如图（1）所示。图1宽度优先搜索示意图MSOPFLFRFNF2宽度优先搜索算法如下：（1）把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解)（2）如果OPEN是个空表，则无解，失败退出；否则继续下一步（3）把第一个节点(记作节点n)从OPEN表移出，并把它放入CLOSED的已扩展节点表中（4）扩展节点n。如果没有后继节点，则转向第(2)步（5）把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针（6）如果n的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第(2)步其流程图如图2所示是否否是图2宽度优先算法流程图把S放入OPEN表FangruOPEN是否为空表?把第一个节点n,从OPEN表移出,并把它放入CLOSED表扩展n,把它的后继节点放入OPEN表的末端,提供回到n的指针失败起始成功是否有任何后继节点为目标节点?32、深度优先搜索在深度优先搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。其搜索过程如图（3）所示。图1深度优先搜索示意图深度优先搜索算法如下：（1）把起始节点S放到未扩展节点的OPEN表中。如果此节点为一目标节点，则得到解（2）如果OPEN为一空表，则无解、失败退出（3）把第一个节点(记作节点n)从OPEN表移到CLOSED表（4）如果节点n的深度等于最大深度，则转向第(2)步（5）扩展节点n，产生其全部后继节点，并把它们放入OPEN表的前头。如果没有后继节点，则转向第(2)步（6）如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向第(2)步MSPFFRFNFOL4是否是否是否否图2深度优先算法流程图把S放入OPEN表FangruOPEN是否为空表?把OPEN表中的第一个节点n移入CLOSED表扩展节点n,把其后裔放入OPEN表的前头成功起始成功是否有任何后继节点为目标节点?S是否为目标节点？失败节点n的深度是否等于深度界限？54．十五数码游戏问题的启发式搜索技术估价函数:f(n)=g(n)+h(n)是对下列函数的一种估计或近似：f*(n)=g*(n)+h*(n)f*(n)：从初始节点到节点n的一条最佳路径的实际代价加上从节点n到目标节点的最佳路径的代价之和。g*(n)：从初始节点到节点n之间最小路径的实际代价h*(n)：从节点n到目标节点的最小代价路径上代价定义利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复杂度的搜索过程称为启发式搜索方法。核心问题：启发信息应用，启发能力度量和如何获得启发信息。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解。弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。全局最佳优先搜索：(1)把起始节点放到OPEN表中，并计算估价函数f(S0)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（股价函数最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并对其所有后继节点计算估价函数f（n）的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价函数值从小到大的顺序排序。(7)转向第(2)步。65．例子及分析对于每一种算法至少给出两个例子及说明，包括起始状态、目标状态、所走的步数及其对应操作符、生成的状态总数（OPEN表和CLOSED表的大小）、搜索CPU时间（毫秒）等。测试的例子(1)(2)（深度界限为5）7深度优先搜索：(3)任意的初始状态与目标状态。012302134567546789101189101112131415121314158宽度优先搜索：910A*算法：1112136．体会与致谢这次作业让我的编程能力有了很大的提高，查阅资料等能力也有很大的提升。让我对人工智能技术有了进一步的认识。在解决问题和算法设计上的能力也极大地提高。这次作业我花了近7天的事件收集相关材料阅读并消化，并写出宽度遍历，深度遍历搜索算法。这里我也要谢谢我朋友的帮助，在我没有思路的情况下帮助我，给我提供思路。通过这次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。学到了不少知识。7．实验程序简单说明1.宽度优先遍历：我没有用随机产生初始节点的方法，而是由用户自己输入。2.深度优先遍历：节点数据由用户自己输入。3.启发式搜索：节点数据由用户自己输入。读书的好处1、行万里路，读万卷书。2、书山有路勤为径，学海无涯苦作舟。3、读书破万卷，下笔如有神。4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文5、少壮不努力，老大徒悲伤。6、黑发不知勤学早，白首方悔读书迟。——颜真卿7、宝剑锋从磨砺出，梅花香自苦寒来。8、读书要三到：心到、眼到、口到9、玉不琢、不成器，人不学、不知义。10、一日无书，百事荒废。——陈寿11、书是人类进步的阶梯。12、一日不读口生，一日不写手生。13、我扑在书上，就像饥饿的人扑在面包上。——高尔基14、书到用时方恨少、事非经过不知难。——陆游15、读一本好书，就如同和一个高尚的人在交谈——歌德16、读一切好书，就是和许多高尚的人谈话。——笛卡儿17、学习永远不晚。——高尔基18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向19、学而不思则惘，思而不学则殆。——孔子120、读书给人以快乐、给人以光彩、给人以才干。——培根