人工智能实验报告-十五数码问题

《人工智能实验报告-十五数码问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录1实验概述22十五数码问题分析22.1十五数码问题简介22.2可行性分析33问题的求解策略33.1算法分析33.2A*算法设计44实验总结54.1实验可视化界面54.2个人体会64.3详细代码：7231实验概述十五数码问题来源于美国的科学魔术大师萨姆.洛伊德（SamI.oyd）在1978年推出的著名的“14-15”智力玩具。这个游戏曾经风靡欧美大陆"。洛伊德的发明其实只是将重排九宫（即八数码问题）中的3阶方阵扩大到4阶方阵罢了。由于这个细微的变化，十五数码问题的规模远远大于八数码问题，八数码问题的规模较小，总的状态数为9！（=3628

2、80）个，而十五数码问题的状态,数为16！（≈20.9*1012）个。故十五数码问题更能评价一个算法的“智能”水平。2十五数码问题分析2.1十五数码问题简介15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目

3、标状态的转变，如下图所示。问题的实质就是寻找一个合法的动作序列232.2可行性分析十五数码问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把四行数展开排成一行,并且丢弃数字0不计入其中,ηi是第i个数之前比该数小的数字的个数,则η=Σηi是该状态的逆序数,例如：对于初始状态：5、1、2、4、9、6、3、8、13、15、10、11、14、7、12.其η=0+0+1+2+4

4、+4+2+6+8+9+8+9+11+6+11=81；对于目标状态：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15，其η=0+1+2+3+4+5+6+7+8+9+10+11+12+13+14=105。初始状态和目标状态的奇偶性相同，故存在解路径。3问题的求解策略3.1算法分析十五数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类：一类是盲目搜索，如深度优先搜索DFS和广度优先搜索BFS；另一类是启发式搜索，如A*算法。对于十五数码问题，深度优先搜索的状态空间搜索树的深度可能为无限深，23或者可能至少要比某个

5、可接受的解答序列的已知深度上限还要深。应用此策略很可能得不到解。宽度优先搜索的优势在于当问题有解时，一定能找到解，且能找到最优解。但其搜索时需要保存所有的待扩展结点，这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至“组合爆炸”。这对宽度优先搜索很不利。这两种搜索方法的共同缺点是结点排序杂乱无章，往往在搜索了大量无关结点后才能得到目的结点，只适合于复杂度较低的问题的求解。启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足，适合于解决十五数码问题。其核心思想是引入一个启发式函数（或称为评估函数）利用评估函数为生

6、成的结点估值%并按估值的大小对结点进行排序，优先搜索估值小的结点。该评估函数根据问题的启发信息建立，评估了解决问题所需的最小费用，其基本形式是f(n)=g(n)+h(n)。其中g(n)：从初始状态s到中间状态n的最佳代价g*(n)的估值，h（n）：从中间状态n到目标状态t的最佳代价h*（n）的估值，利用评估函数来进行的图搜索算法称为A算法，若还有h（n）<=h*（n）则称为A*算法。在八数码问题中，通常g（n）是搜索树中当前结点n的深度，是从根结点到当前结点n的最短路径长度；h（n）的取值则有多种，如错位将牌数、曼哈顿距离。这里主要是h（

7、n）体现了启发信息，h（n）设计的好坏体现了算法的“智能”水平。本课设借鉴这些算法h（n）采用曼哈顿距离。3.2A*算法设计（1）根据初始排列生成初始结点s，并判断问题的可解性。若可解则转（2）否则退出。（2）初始化open，closed表，并将初始节点加入open表。（3）从open表中取出第一个节点。（4）若是目标节点则成功退出。（5）把该节点从open表删除，并添加到closed表中。23（6）对该节点进行扩展，其生成节点mi分成三种情况，mj，mk，ml。mj：新生成的节点既不在open表中也不在closed表中，直接把生成的节点

8、添加到open表即可。Mk：新生成的节点出现在open表中且新生成节点的f（n）小于open表中该节点的f（n），则更改open表中的f（n）的值。Ml：新生成的节点在closed表中并且新生