人工智能大作业八数码问题.pdf

人工智能大作业八数码问题.pdf

ID:56058370

大小:387.26 KB

页数:10页

时间:2020-06-20

人工智能大作业八数码问题.pdf_第1页
人工智能大作业八数码问题.pdf_第2页
人工智能大作业八数码问题.pdf_第3页
人工智能大作业八数码问题.pdf_第4页
人工智能大作业八数码问题.pdf_第5页
资源描述:

《人工智能大作业八数码问题.pdf》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、人工智能课程大作业基于A星算法的八数码问题求解学号:姓名:摘要:在人工智能领域中,八数码问题一直都是一个游戏难题。介绍了八数码问题,然后在启发式搜索算法上对A*算法定义进行了解释,并在其旨在提高搜索效率的方面作了比较详尽的介绍,详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法:A*算法。再依据这种算法用可视化编程语言VC++6.0来实现八数码问题的求解过程,取得了预期的搜索解,提高了搜索效率。关键词:八数码问题;启发式搜索;A*算法本组成员:本人分工:主要负责进行问题分析,提出解决方案,进行系统设计,算法上具体负责主函数的编写。1

2、引言八数码问题是人工智能的一个经典的问题。文中通过设计一个基于A*算法的状态空间搜索程序,对于给定的初始状态,采用h(n)=p(n)表示以每一个将牌与目标位置之间距离的总和作为启发函数的度量,并用可视化编程语言VC++来实现该问题。2算法原理与系统设计1)A*算法思想A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。A*算法对A算法中的g(n)和h(n)分别提出如下限制:第一,g(n)是对最小代价g*(n)的估计,且g(n)>0;第二,h(n)是最小代价h*(n)的下界,即对任意节点n均有h(n

3、)≤h*(n)。即满足上述两条限制的A算法称为A*算法。2)估价函数用来估算节点希望程度的量度,叫估价函数f(x),f(x)=g(x)+h(x)。g(x)为从初始节点到当前节点已经付出的代价,h(x)为从当前节点到目标节点的最优路径的估计代价。本算法中令g(x)为当前节点的深度depth,h(x)为当前节点每个数字位与目标节点数字位间距离和dist,进一步考虑当前结点与目标结点的距离信息,令启发函数h(n)为当前8个数字位与目标结点对应数字位距离和(不考虑中1人工智能课程大作业间路径),满足h(n)<=h*(n),且对于目标节点有h(t)=

4、0,对于结点m和n(n是m的子结点)有h(m)–h(n)<=1满足单调限制条件。3)open和closed表的数据结构表示对open表的操作,每次需要得到所有待扩展结点中f值最小的那个结点。closed表存储已扩展的结点间的扩展关系,主要用于输出路径。closed表中任意一个结点都存储有它的前驱结点的信息,考虑closed表中任意一个结点,如果它是初始结点,它没有前驱结点,如果不是根结点,扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱点的下标位置,可以用数组实现。每个结点记录8数码格局和它的前

5、驱结点的下标。4)问题分析首先,八数码问题包括一个初始状态(src)和目标状态(dest),所谓解八数码问题就是在两个状态间寻找一系列可过渡状态。这个状态是否存在就是我们要解决的第一个问题。解决八数码问题,主要面临的问题有:Q1)开始状态S到目标状态D是否可解;Q2)扩展节点的选择;Q3)扩展待扩展节点,该节点是否已扩展过;Q4)判断是否已达目标节点D;问题Q1)通过逆序数的奇数偶数来判断。因为在空白移动过程中,数码的逆序数不改变。左右移动,数码序列不变。上下移动,数码序列中某个数字则移动了两位。问题的实质就是:如果是N*N的数码盘的话,左

6、右移动,数码序列不变;上下移动则数码序列变动N-1位。若N为奇数则在变动过程中其逆序数不会改变。而八数码问题为3*3矩阵,3为奇数,故逆序数不作改变。故可通过判断当前状态S的逆序数以及目标状态SD的数字序列的逆序数的奇偶性是否相同来判断该问题是否可解。问题Q2)扩展节点的选择通过getmin函数,根据估价函数f来获得代价最小的节点。问题Q3)扩展节点即为上下左右四个方向移动空格到没有扩展过的节点中去,要判断是否扩展过,只要跟之前的状态做比较即可。问题Q4)是否达到目标节点,将当前节点和目标节点进行比较。算法的功能:产生8数码问题的解(由初始

7、状态到达目标状态的过程)输入:初始状态,目标状态2人工智能课程大作业输出:从初始状态到目标状态的一系列过程算法描述:Begin:读入初始状态和目标状态,并计算初始状态评价函数值f;根据初始状态和目标状态,判断问题是否可解;If(问题可解)把初始状态假如open表中;While(未找到解&&状态表非空)①在open表中找到评价值最小的节点,作为当前结点;②判断当前结点状态和目标状态是否一致,若一致,跳出循环;否则跳转到③;③对当前结点,分别按照上、下、左、右方向移动空格位置来扩展新的状态结点,并计算新扩展结点的评价值f并记录其父节点;④对于新

8、扩展的状态结点,判断其是否重复,若不重复,把其加入到open表中;⑤把当前结点从open表中移除;EndwhileEndif输出结果;End算法流程如下:3人工智能课程大作业开始

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。