人工智能实验报告1计算机人工智能_计算机-人工智能.pdf

*大学 人工智能基础课程实验报告（2011-2012 学年第一学期）启发式搜索 王浩算法 班 级：*学 号：*姓 名：*指导教师：*成 绩：2012 年 1 月 10 日 实验一 启发式搜索算法 1.实验内容：使用启发式搜索算法求解 8 数码问题。编制程序实现求解 8 数码问题A算法，采用估价函数 w nf nd np n，其中：d n是搜索树中结点n的深度；w n为结点n的数据库中错放的棋子个数；p n为结点n的数据库中每个棋子与其目标位置之间的距离总和。分析上述中两种估价函数求解 8 数码问题的效率差别，给出一个是 p n的上界的 h n的定义，并测试使用该估价函数是否使算法失去可采纳性。2.实验目的 熟练掌握启发式搜索A算法及其可采纳性。3.实验原理 使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率；启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。4.实验内容 1.问题描述 在一个 3*3 的九宫格 里有 1 至 8 八个数以及一个空格随机摆放在格子中，如下图：初始状态 目标状态 现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。2.算法分析 (1)解存在性的讨论 2 8 3 1 6 1 2 3 8 0 式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。（2）估价函数的确定 通 过 对 八 数 码 的 特 性 的 研 究，找 出 一 个 相 对 好 的 函 数，f(n)=d(n)+h(n)其 中h(n)=2*compare(n)+3*S(n);d(n)为已搜索的深度；（compare（n）为当前节点与目标结点相同位置不相同的个数，S(n)为当前节点的无序度。）（3）节点的处理 取得一个结点后，判断是否有解，然后对其进行扩展，用估价函数从中取得一个最优节点，依次循环将路径得到，直到取的最后的目标状态。(4)算法设计 a.输入初始结点，判断解的存在性，并与目标节点对比。b.若不是目标节点则进行扩展，生成其全部后继节点。c.对于每个后继节点均求其 f(n),并比较。d.将最小 f(n)存入正确路径，并与目标节点进行对比。e.若不是目标节点则循环执行 b，若是目标节点则输出 5 实验结果 输入输出：源代码如下：式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始#include int final9=1,2,3,8,0,4,7,6,5;实验内容：实现命题逻辑框架内的王浩算法。将命题逻辑中的王浩算法推广至下述命题语言的情形之下:命题变量符号：1p，2p，3p，L 逻辑连接符：，间隔符：(，)在上述中所定义的命题语言中实现王浩算法。2.实验目的 熟练掌握命题逻辑中的王浩算法。3.实验要求 实验题目必须由个人独立完成，允许自行参考相关文献资料，但严禁同学间相互拷贝和抄袭程序以及文档资料。实验结束后一周内上交实验报告和实验文档资料。提交的文档资料包括设计文档和程序源代码。设计文档和程序源代码以书面文档方式提供（用4A纸打印）；并提交电子文档备查。四数据结构 给定公式，例如：(p1-(q1-r1)-(p1-q1)-(p1-r1)函数 inite主要作用是负责将符号初始化成树的结构。函数 clone 复制一棵完全相同的符号树。函数 restruct查找所有&，|，等符号，并将其拆分成新形式：！，-符号。函数 searching王浩算法的主要函数。函数 show 和 output:显示符号串和推理过程。五实验结果 公式正确 式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 六实验总结 通过本次实验，使我更深入的理解了启发式搜索的原理以及实现，对于其优越性有一定认识，加深了对语法分析以及逻辑公式理解，同时熟练掌握了对树的操作。在编程实现过程中出现过不少问题，通过一次次调试得以解决，并一定程度上提高了我的编程能力，而且让我对人工智能这一课程有了更直接的认知。王浩算法源代码清单：#include#include#include#define MAX_L 5 int i=0;int stepcount=1;enum typeand,or,detrusion,equal,level,variable;struct nodechar*s;type kind;int polar;node*next;node*child;int start;struct stepstep*child;step*brother;node*lhead;node*rhead;int count;char name30;int inite(char*s,node*head)式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 int len=strlen(s);int j=0,polar=1;node*now=NULL;node*last=NULL;if(s=NULL)return 0;last=head;while(ilen)if(si=|)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!|i=0)return 0;now=(node*)malloc(sizeof(node);now-kind=or;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;elselast-next=now;last=now;i+;else if(si=&)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!|i=0)return 0;now=(node*)malloc(sizeof(node);式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 now-kind=and;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;else last-next=now;last=now;i+;else if(si=!)if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=(&si+1!=!)return 0;polar=1-polar;i+;else if(si=-)if(si+1!=|(si+2!=!&si+2!=(&!(si+2=A|si+2=a)|i=0)return 0;now=(node*)malloc(sizeof(node);now-kind=detrusion;now-s=NULL;now-next=NULL;now-child=NULL;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;else last-next=now;last=now;i=i+2;else if(si=)|(si+3!=!&si+3!=(&!(si+3=A|si+3=a)|i=0)&si+3!=1&si+3!=0)return 0;now=(node*)malloc(sizeof(node);now-kind=equal;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;else last-next=now;last=now;i=i+3;else if(si=A|si=a)now=(node*)malloc(sizeof(node);式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 now-kind=variable;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;now-s=(char*)malloc(MAX_L*sizeof(char);if(last-kind=level&last-child=NULL)last-child=now;else last-next=now;last=now;j=0;while(si=A|si=a)|(si=0)(now-s)j=si;i+;j+;if(si!=|&si!=&si!=-&si!=s)j=0;polar=1;else if(si=1|si=0)if(si+1!=kind=equal;now-s=(char*)malloc(2*sizeof(char);式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 (now-s)0=si;(now-s)1=0;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;else last-next=now;last=now;i+;else if(si=()if(!(si+1=A|si+1=a)&si+1!=1&si+1!=0&si+1!=!&si+1!=()return 0;now=(node*)malloc(sizeof(node);now-kind=level;now-s=NULL;now-next=NULL;now-child=NULL;now-polar=polar;now-start=0;if(last-kind=level&last-child=NULL)last-child=now;else 式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 last-next=now;last=now;i+;polar=1;if(!inite(s,last)return 0;else if(si=)if(si+1!=P&si+1!=1&si+1!=0&si+1!=-&si+1!=kind=parent-kind;son-polar=parent-polar;son-s=parent-s;son-start=parent-start;if(parent-next!=NULL)son-next=clone(parent-next);else son-next=NULL;if(parent-child!=NULL)son-child=clone(parent-child);else son-child=NULL;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 return son;void remove(node*head)node*now=NULL;now=head;if(now=NULL)return;if(now-kind=level&now-child-kind=variable&now-child-next=NULL)now-polar=(now-child-polar=now-polar);now-child-polar=1;while(now-kind=level&now-child-kind=level&now-child-next=NULL)now-polar=(now-polar=now-child-polar);now-child=now-child-child;if(now-next!=NULL)remove(now-next);if(now-child!=NULL)remove(now-child);void restruct(node*head)node*now=NULL;node*last=NULL;node*newone=NULL,*newtwo=NULL,*newthree=NULL,*newfour=NULL,*newnow=NULL;int order=1;while(orderchild;while(now!=NULL)if(now-kind=variable|now-kind=level)&order=1)式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 if(now-next!=NULL&now-next-kind=and)newone=(node*)malloc(sizeof(node);newone-child=NULL;newone-kind=level;newone-next=NULL;newone-polar=0;newone-s=NULL;newone-start=0;if(last-kind=level)last-child=newone;else last-next=newone;newone-next=now-next-next-next;newone-child=now;now-next-next-polar=1-now-next-next-polar;now-next-kind=detrusion;now-next-next-next=NULL;now=newone;else last=now;now=now-next;else if(now-kind=variable|now-kind=level)&order=2)if(now-next!=NULL&now-next-kind=or)newone=(node*)malloc(sizeof(node);newone-child=NULL;newone-kind=level;newone-next=NULL;newone-polar=1;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 newone-s=NULL;newone-start=0;if(last-kind=level)last-child=newone;else last-next=newone;newone-next=now-next-next-next;newone-child=now;now-polar=1-now-polar;now-next-kind=detrusion;now-next-next-next=NULL;now=newone;else last=now;now=now-next;else if(now-kind=variable|now-kind=level)&order=3)if(now-next!=NULL&now-next-kind=equal)newone=(node*)malloc(sizeof(node);newone-child=NULL;newone-kind=level;newone-next=NULL;newone-polar=0;newone-s=NULL;newone-start=0;newtwo=(node*)malloc(sizeof(node);newtwo-child=NULL;newtwo-kind=level;newtwo-next=NULL;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 newtwo-polar=1;newtwo-s=NULL;newtwo-start=0;newthree=(node*)malloc(sizeof(node);newthree-child=NULL;newthree-kind=detrusion;newthree-next=NULL;newthree-polar=1;newthree-s=NULL;newthree-start=0;newfour=(node*)malloc(sizeof(node);newfour-child=NULL;newfour-kind=level;newfour-next=NULL;newfour-polar=0;newfour-s=NULL;newfour-start=0;if(last-kind=level)last-child=newone;else last-next=newone;newone-next=now-next-next-next;newone-child=newtwo;now-next-kind=detrusion;newtwo-child=now;now-next-next-next=NULL;newtwo-next=newthree;newthree-next=newfour;newfour-next=NULL;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 newnow=clone(now);newnow-next-kind=detrusion;newfour-child=newnow-next-next;newnow-next-next-next=newnow-next;newnow-next-next=newnow;newnow-next=NULL;now=newone;else last=now;now=now-next;else if(now-kind=level&order=4)restruct(now);last=now;now=now-next;else last=now;now=now-next;order+;void show(node*head)node*now=NULL;now=head;while(now!=NULL)if(now-kind=level)式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 if(now-polar=0)printf(!);if(now-start!=1|(now-polar=0&now-child-next!=NULL)printf();show(now-child);if(now-start!=1|(now-polar=0&now-child-next!=NULL)printf();now=now-next;if(now!=NULL&now-start=1)putchar(,);else if(now-kind=and)printf(&);now=now-next;else if(now-kind=or)printf(|);now=now-next;else if(now-kind=detrusion)printf(-);now=now-next;else if(now-kind=equal)printf();now=now-next;else if(now-kind=variable)if(now-polar=0)printf(!);printf(%s,now-s);now=now-next;return;int searching(step*one)式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 node*now=NULL;node*last=NULL;node*newlev=NULL;node*nnow=NULL;node*nlast=NULL;step*nextone=NULL;step*nexttwo=NULL;int key=0;int mark=0;int re1=1;int re2=1;nextone=(step*)malloc(sizeof(step);nextone-brother=NULL;nextone-child=NULL;nextone-lhead=NULL;nextone-rhead=clone(one-rhead);nextone-lhead=clone(one-lhead);strcpy(nextone-name,);one-child=nextone;now=nextone-rhead;last=now;while(now!=NULL)if(now-polar=0)if(now=nextone-rhead)nextone-rhead=now-next;else last-next=now-next;now-next=NULL;remove(now);式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 now-next=nextone-lhead;nextone-lhead=now;now-polar=1-now-polar;now-start=1;now=last-next;strcpy(one-name,根据规则 1);mark=1;key=1;break;else if(now-child-next!=NULL&now-child-next-kind=detrusion)nlast=now-child;nnow=now-child-next;while(nnow-next-next!=NULL&nnow-next-next-kind=detrusion)nlast=nnow-next;nnow=nnow-next-next;now-polar=1-now-polar;newlev=(node*)malloc(sizeof(node);newlev-child=nnow-next;newlev-kind=level;newlev-polar=1;newlev-next=NULL;newlev-start=1;nlast-next=NULL;remove(newlev);newlev-next=now-next;now-next=NULL;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 remove(now);now-next=newlev;strcpy(one-name,根据规则 4);mark=1;key=1;break;else last=now;now=now-next;now=nextone-lhead;last=now;while(now!=NULL&key!=1)if(now-polar=0)if(now=nextone-lhead)nextone-lhead=now-next;else last-next=now-next;now-next=NULL;remove(now);now-next=nextone-rhead;nextone-rhead=now;now-polar=1-now-polar;now-start=1;now=last-next;strcpy(one-name,根据规则 2);mark=1;key=1;break;式搜索算法实验内容使用启发式搜索算法求解数码问题编制程序实现求解数码问题算法采用估价函数其中是搜索树中结点的深度为结点的数据库中错放的棋子个数为结点的数据库中每个棋子与其目标位置之间的距离总和分析上述中性实验目的熟练掌握启发式搜索算法及其可采纳性实验原理使用启发式信息知道搜索过程可以在较大的程度上提高搜索算法的时间效率和空间效率启发式搜索的效率在于启发式函数的优劣在启发式函数构造不好的情况下甚至在存在述在一个的九宫格里有至八个数以及一个空格随机摆放在格子中如下图初始状态目标状态现需将图一转化为图二的目标状态调整的规则为每次只能将空格与其相邻的一个数字进行交换实质是要求给出一个合法的移动步骤实现从初始 else if(now-child-next!=NULL&now-child-next-kind=detrusion)nexttwo=(step*)malloc(sizeof(step);nexttwo-brother=NULL;nexttwo-child=NULL;nexttwo-lhead=NULL;nexttwo-rhead=clone(nextone-rhead);nexttwo-