八数码实验报告

八数码实验报告八数码实验报告篇一：八数码实验报告利用人工智能技术解决八数码游戏问题1・八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。问题是在3X3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。2.八数码游戏问题的状态空间法表示建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中建立CLOSED表，且置为空表判断OPEN表是否为空表，若为空，则问题无解，退出选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得到。若不是转⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点，设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过并已在losed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。按某一任意方式或某种策略重排OPEN表中节点的顺序转③3・八数码游戏问题的盲目搜索技术宽度优先搜索：1、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索把起始节点放到OPEN表中如果OPEN是个空表，则没有解，失败退出；否则继续。把第一个节点扩展节点n。如果没有后继节点，则转向上述第把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第把起始节点放到OPEN表中如果OPEN是个空表，则没有解，失败退出；否则继续。把第一个节点考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出（5）如果没有后继节点，则转向上述第扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第二g+h=g*+h*f*把起始节点放到OPEN表中，并计算估价函数f如果OPEN是个空表，则没有解，失败退出；否则继续。把OPEN表中的第一个节点（股价函数最小的节点门），移入CLOSED表。如果n是目标节点，问题得解，退出。否则继续。判断节点n是否可扩展。若否则转向第对节点n进行扩展，并对其所有后继节点计算估价函数f（n）的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价函数值从小到大的顺序排序。转向第编制程序实现求解8数码问题A?算法，采用估价函数?n?，f?nd?n?p?n?其中：d?n?是搜索树中结点n的深度；？n?为结点n的数据库中错放的棋子个数；p?n?为结点n的数据库中每个棋子与其目标位置之间的距离总和。2）分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是p?n?的上界的h?n?的定义，并测试使用该估价函数是否使算法失去可采纳性。三、实验原理：问题描述：八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。原理描述：1有序搜索算法：（1）原理：在搜索过程中，OPEN表中节点按照其估价函数值以递增顺序排列，选择OPEN表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。在本例中，估价函数中的g=g*树形方式扩展节点。Node为要扩展的当前节点，depth为当前深度，zero存放该节点空格位置信息，moveflag即扩展节点的移动方式，Choose为选择函数？分别为表OPEN、CLOSE的创建和表的插入操作。7）LNode*Getminf主要是实现从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i。五、实验小结通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所扩在的节点数来看，p{Chessboardboard;LNode*parent,*next;boolflag;Pieepos;记录每个数码a的位置r行列intd,f,move;d：深度；f：启发函数值；move：父节点移动到该节点的方}inti,j,zr；int*z=zr；for{}intpik{int=0,i,j,ii,jj；forforif++;篇三：八数码实验报告53华中师范大学计算机学院 实验报告书实验题目：八数码问题求解 课程名称：人工智能 主讲教师：金聪 班级：试验时间：1.问题描述：八数码问题也称为九宫问题。在3X3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。初始状态103TOC\o"1-5"\h\z2485目标状态123,04,65搜索策略启发式搜索技术（1） 原理：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（2） 估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价（起始节点到当前节点）；2、将要付出的代价（当前节点到目标节点）。节点n的估价函数f=g把初始状态假如open表中；While（未找到解状态表非空）在open表中找到评价值最小的节点，作为当前结点；判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；把当前结点从open表中移除；EndhileEndif输出结果；End6.源代码#inlude<；stdio.h#inlude<；mallo.h#inlude<；stdlib.h#defineOverflo1#defineN3intgoal={1,2,3,8,0,4,7,6,5};intzero,NodeQTY=0；int*z=zero；记录0的位置，zero：r行；zero：歹JtpedefintPiee；strutChessboard{棋盘信息Pieepos;记录每个数码a的位置r行列intd,f,move;d:深度；f:启发函数值；move:父节点移动到该节点的方式};strutLNode{Chessboardboard;LNode*parent,*next;boolflag;};tpedefLNode*List;int*Findzero{inti,j,zr;int*z=zr;for{int=0,i,j,ii,jj;forforif{LNode*NeNode=neLNode；for{ase1：向左移，不能出界：zero=2NeNode-board.posT]T]=NeNode-board.posT]-2]；NeNode-board.posT]-2]=0；break；ase2:向右移，不能出界：zero<=2NeNode-board.posT]T]=NeNode-board.posT]];NeNode-board.posT]]=0;break；ase3:向上移，不能出界：zero=2NeNode-board.posT]T]=NeNode-board.pos-2]T];NeNode-board.pos-2]-1]=0;break；ase4:向下移，不能出界：zero<=2NeNode-board.posT]T]=NeNode-board.pos]T];NeNode-board.pos]-1]=0;break;}NeNode-board.d二depth+1；sith{Open=exit{Listp=L;hile{篇四：人工智能大作业八数码问题基于A星算法的八数码问题求解学号：姓名：摘要：在人工智能领域中，八数码问题一直都是一个游戏难题。介绍了八数码问题，然后在启发式搜索算法上对A*算法定义进行了解释，并在其旨在提高搜索效率的方面作了比较详尽的介绍，详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法：A*算法。再依据这种算法用可视化编程语言VC++0来实现八数码问题的求解过程，取得了预期的搜索解，提高了搜索效率。关键词：八数码问题；启发式搜索；A*算法本组成员：本人分工：主要负责进行问题分析，提出解决方案，进行系统设计，算法上具体负责主函数的编写。1引言八数码问题是人工智能的一个经典的问题。文中通过设计一个基于A*算法的状态空间搜索程序，对于给定的初始状态，采用h=p表示以每一个将牌与目标位置之间距离的总和作为启发函数的度量，并用可视化编程语言VC++来实现该问题。2算法原理与系统设计1)A*算法思想A*算法是对A算法的估价函数f<；=h*=0，对于结点m和n(n是m的子结点)有h-h<；=1满足单调限制条件。3)open和losed表的数据结构表示对open表的操作，每次需要得到所有待扩展结点中f值最小的那个结点。losed表存储已扩展的结点间的扩展关系，主要用于输出路径。losed表中任意一个结点都存储有它的前驱结点的信息，考虑losed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在losed表中形成扩展关系的树状结构。因为只需要前驱点的下标位置，可以用数组实现。每个结点记录8数码格局和它的前驱结点的下标。4）问题分析首先，八数码问题包括一个初始状态和目标状态把初始状态假如open表中；While（未找到解状态表非空）在open表中找到评价值最小的节点，作为当前结点；判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；把当前结点从open表中移除；EndhileEndif输出结果；End算法流程如下：3系统实现5、main函数，主程序运行步骤为：（1）先读入八数码初始状态sr，以及目标状态dest。通过open表的push_bak（2） A*算法搜索开始，设置hile循环，直到找到目标状态或者open表为空或者无解的情况下结束。（3） 不同的八数码初始状态和目标状态不一定有解，所以要根据两种状态下的奇偶性是否一致来判断（详见实验思想的问题分析）。篇五：C语言解八数码问题之人工智能实验报告人工智能》上机实验《基于人工智能的状态空间搜索策略研究——八数码问题求解（一） 实验软件TC0或VC6.0编程语言或其它编程语言（二） 实验目的1.熟悉人工智能系统中的问题求解过程；熟悉状态空间的盲目搜索和启发式搜索算法的应用；熟悉对八数码问题的建模、求解及编程语言的应用。（三） 需要的预备知识1.熟悉TC0或VC6.0编程语言或者其它编程语言；熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；熟悉计算机语言对常用数据结构如链表、队列等的描述应用；熟悉计算机常用人机接口设计。（四）实验数据及步骤1.实验内容八数码问题：在3X3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。图1八数码问题示意图请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A算法或A*算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。实验步骤（1） 分析算法基本原理和基本流程；程序采用宽度优先搜索算法，基本流程如下：（2） 确定对问题描述的基本数据结构，如Open表和Closed表等；（3） 编写算符运算、目标比较等函数；（4） 编写输入、输出接口；（5） 全部模块联调；（6） 撰写实验报告。（五）实验报告要求所撰写的实验报告必须包含以下内容：算法基本原理和流程框图；基本数据结构分析和实现；编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；程序运行结果，含使用的搜索算法及搜索路径等；实验结果分析；结论；提供全部源程序及软件的可执行程序。附：实验报告格式一、 实验问题二、 实验目的三、 实验原理四、 程序框图五、 实验结果及分析六、 结论七、 源程序及注释#inlude<；stdio.h#inlude<；onio.hintn,m；tpedefstrutNode{harmatrix;*存储矩阵*haroperate；*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*harextend；*是否可以扩展，Y代表可以，N代表不可以*intfather；*指向产生自身的父结点*}Node；harstart={83426517};*此处没有必要初始化*harend={12384765};*此处没有必要初始化*Nodebase;intresult;*存放结果的base数组下标号，逆序存放*intmath{if{return0; }}return1;}voidsho{附送：八方责任主体承诺书图片八方责任主体承诺书图片、商品混凝土、混凝土预制构件、建筑构配件和设备等，在建设单位或者监理单位见证下取样送检，经检测合格后使用；保证取样、封样、送检工作不-2-篇三：承诺书关于贯彻落实工程质量终身责任承诺制度的通知鄂建文〔201X〕51号各市、州、直管市、神农架林区住建委：为贯彻落实工程质量治理两年行动，增强工程参建各方主体质量责任意识，强化工程质量责任追究，根据有关法律法规和文件精神，现就实行工程质量终身责任承诺制度有关事项通知如下：一、 在我省范围内，从事房屋建筑和市政基础设施工程建设的建设、勘察、设计、施工、监理单位（以下统称五方责任主体）的项目负责人，应依据国家有关法律法规和相关规定，对工程质量终身责任作出承诺。二、 工程开工前，五方责任主体的项目负责人应签署《工程质量终身责任承诺书》，明确应该履行的职责、承担的责任。三、 建设单位在办理工程质量监督手续时，应向工程质量监督机构提交五方责任主体项目负责人签署的《承诺书》及相应的法定代表人授权书。项目负责人如有变更的，应重新签署《承诺书》，连同法定代表人授权书，报工程质量监督机构备案。四、 施工现场应设置五方责任主体项目负责人质量责任标识牌，公开单位名称、项目负责人姓名等信息。在工程建设过程中，五方责任主体的项目负责人应严格按照建设工程相关法律法规及工程质量终身责任承诺书内容认真履行相应职责。五、 建设单位应加强对五方责任主体项目负责人的管理，及时记录项目负责人信息及项目负责人变更情况，在工程竣工验收前，准确填报《工程质量终身责任信息表》（见附件6），并对工程质量责任信息的真实性负责。六、 工程竣工验收备案前，建设单位负责收集整理《承诺书》和工程质量终身责任信息表等资料，形成工程质量责任信息档案。工程质量责任信息档案连同工程资料移交城建档案管理部门，并作为竣工验收备案材料报竣工验收备案部门。七、 各级住房和城乡建设主管部门要加强对工程质量终身责任制的监督管理，督促五方责任主体项目负责人落实工程质量终身责任承诺制度。对不履行承诺制度的，依据相关规定进行查处，并进行不良行为记录。对在设计使用年限内，发生质量事故和严重质量问题的，依据工程质量责任信息，严格按照规定，追究相关人员的质量终身责任。附件：建设单位项目负责人工程质量终身责任承诺书勘察单位项目负责人工程质量终身责任承诺书设计单位项目负责人工程质量终身责任承诺书施工单位项目负责人工程质量终身责任承诺书监理单位项目负责人工程质量终身责任承诺书工程质量终身责任信息表附件1：建设单位项目负责人工程质量终身责任承诺书工程名称：本人承诺在工程建设过程中和建筑物设计使用年限内，对工程质量承担全面责任。在工程建设过程中认真履行下列职责：1、 严格遵守相关法律法规和规范标准，认真履行建设工程合同所规定的责任和义务。2、 将工程发包给具有相应资质等级的施工、监理、勘察、设计、检测和施工图审查等单位，不将建设工程肢解发包。对按规定必须招标的严格依法依规进行招标，不迫使承包方以低于成本价竞标，不任意压缩合理工期。3、 向勘察、设计、施工、监理、检测和施工图审查等单位。提供真实、准确、齐全的建设项目相关的原始材料。4、 将勘察、设计文件送有资质的审查机构进行审查，及时向施工现场提供审查合格并加盖了审查专用章的勘察、设计文件及审查意见。工程有变更的按规定程序办理相关手续，重大设计变更送原审查机构审查合格后再实施。5、 严格遵守基本建设程序，在开工前办理质量监督手续，领取施工许可证。6、 不明示或暗示勘察、设计、施工、检测等单位违反工程建设强制性标准或使用不合格的建筑材料、建筑配件和设备，降低工程质量。7、 工程竣工后，按规定组织勘察、设计、施工、监理等有关单位进行验收，并接受工程质量监督机构监督。在工程验收合格十五日内，办理竣工验收备案手续。工程未经验收合格不得交付使用。8、 及时整理文件资料，建立健全工程项目档案，并自竣工验收后三个月内向城建档案管理部门移交建设项目档案。9、 督促勘察、设计、施工、监理等有关单位落实质量责任，对未实行监理的工程，组织建设单位相关人员履行监理单位职责。10、法律法规及标准规范规定的其他质量责任。本承诺书一式三份，一份在办理监督手续时提交质量监督机构，一份在建设工程竣工验收合格后与档案资料一并交城建档案管理部门存档，一份建设单位留存。建设单位（公章）：年月日附件2：勘察单位项目负责人工程质量终身责任承诺书工程名称：本人承诺在该工程建设过程中和建筑物设计使用年限内，承担因勘察导致的工程质量事故或质量问题责任。在工程建设过程中认真履行下列职责：1、 严格遵守相关法律法规和规范标准，认真履行建设工程合同所规定的责任和义务。2、 严格按照核定的工程勘察资质等级和业务范围开展勘察业务，不超越资质等级许可的范围承揽工程，不转包或违法分包所承揽的勘察业务。3、 严格按国家强制性标准要求开展勘察工作，及时整理、核对勘察工作的原始记录，确保取样的真实性、代表性，保证勘察成果内容齐全、图表清晰、数据准确、可靠，结论建议合理，相关的签字、盖章手续齐全，勘察文件满足国家有关法律、技术标准和合同规定的要求。4、 及时解决施工过程中涉及到的勘察问题，积极参加地基验槽、基础验收、竣工验收等工作，保证签署的验收结论准确可靠，按规定提交工程质量检查报告。5、 法律法规及标准规范规定的其他质量责任。本承诺书一式四份，一份在办理监督手续时提交质量监督机构，一份在建设工程竣工验收合格后与档案资料一并交城建档案管理部门存档，一份交建设单位，一份勘察单位留存。勘察单位（公章）：年月日附件3：设计单位项目负责人工程质量终身责任承诺书工程名称：本人承诺在该工程建设过程中和建筑物设计使用年限内，承担因设计导致的工程质量事故或质量问题责任。在工程建设过程中认真履行下列职责：1、 严格遵守相关法律法规和规范标准，认真履行建设工程合同所规定的责任和义务。2、 严格按照核定的工程设计资质等级和业务范围开展设计业务，不超越资质等级许可的范围承揽工程，不转包或违法分包所承揽的设计业务。3、 严格依据勘察成果文件进行工程设计，保证设计文件符合工程建设强制性标准要求，达到国家规定的文件编制深度要求，并经过严格的内部校对、审核。提供的设计文件加盖有设计单位出图专用章和执业人员印章。4、 严格按照相关规定进行设计变更。重大设计变更应按规定和程序进行审查。5、 按规定在施工前向施工单位和监理单位做好设计交底和参加图纸会审，及时解决施工过程中涉及到的设计问题，积极参与重要分部分项工程和单位工程竣