logo资料库

八数码实验报告（附源代码·）.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.09M 资料格式：doc 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    《人工智能》实验一题目 实验一 启发式搜索算法 1. 实验内容： 使用启发式搜索算法求解 8 数码问题。 ⑴ 编制程序实现求解 8 数码问题 A 算法，采用估价函数  f n    d n       w n  p n   ，  d n 是搜索树中结点 n 的深度；  其中：  结点 n 的数据库中每个棋子与其目标位置之间的距离总和。 w n 为结点 n 的数据库中错放的棋子个数；  p n 为   h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。 ⑵ 分析上述⑴中两种估价函数求解 8 数码问题的效率差别，给出一个是   2. 实验目的 熟练掌握启发式搜索 A 算法及其可采纳性。 p n 的上界的  3.数据结构与算法设计 该搜索为一个搜索树。为了简化问题，搜索树节点设计如下： typedef struct Node//棋盘 {//节点结构体 int data[9]; double f,g; struct Node * parent; //父节点 }Node,*Lnode; int data[9]; 数码数组：记录棋局数码摆放状态。 struct Chess * Parent; 父节点：指向父亲节点。 下一步可以通过启发搜索算法构造搜索树。 1、局部搜索树样例：
    2、搜索过程 搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过 程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘； （5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节 点），是则把子棋盘压入队列，否则抛弃； （5）、跳到步骤（2）； 3、算法的评价
    完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。现存在的一 些优缺点。 1、可以改变数码规模（N），来扩展成 N*N 的棋盘，即扩展为 N 数码问题的求解过程。 2、 内存泄漏。由于采用倒链表的搜索树结构，简化 了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏； 3、 采用了屏蔽方向，有效防止往回搜索（节点的回 推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题； 源码： #include #include #include typedef struct Node {//节点结构体 int data[9]; double f,g; struct Node * parent; }Node,*Lnode; typedef struct Stack {//OPEN CLOSED 表结构体 Node * npoint; struct Stack * next; }Stack,* Lstack; Node * Minf(Lstack * Open) {//选取 OPEN 表上 f 值最小的节点，返回该节点地址 Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open); Node * minx; while(temp->next != NULL) { if((temp->next ->npoint->f) < (min->npoint->f)) { min = temp->next; minp = temp; } temp = temp->next; }
    minx = min->npoint; temp = minp->next; minp->next = minp->next->next; free(temp); return minx; } int Canslove(Node * suc, Node * goal) {//判断是否可解 int a = 0,b = 0,i,j; for(i = 1; i< 9;i++) for(j = 0;j < i;j++) { if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)a++; if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)b++; } if(a%2 == b%2)return 1; else return 0; } int Equal(Node * suc,Node * goal) {//判断节点是否相等，相等，不相等 for(int i = 0; i < 9; i ++ ) if(suc->data[i] != goal->data[i])return 0; return 1; } Node * Belong(Node * suc,Lstack * list) {//判断节点是否属于 OPEN 表或 CLOSED 表，是则返回节点地址，否则返回空地址 Lstack temp = (*list) -> next ; if(temp == NULL)return NULL; while(temp != NULL) { if(Equal(suc,temp->npoint))return temp -> npoint; temp = temp->next; } return NULL; } void Putinto(Node * suc,Lstack * list) {//把节点放入 OPEN 或 CLOSED 表中 Stack * temp; temp =(Stack *) malloc(sizeof(Stack)); temp->npoint = suc;
    temp->next = (*list)->next; (*list)->next = temp; } ///////////////计算 f 值部分-开始////////////////////////////// double Fvalue(Node suc, Node goal, int m) {//计算 f 值 switch(m) { case 1:{ int error(Node,Node); int w=0; w=error(suc,goal); return w+suc.g; case 2:{ } } double Distance(Node,Node,int); double p = 0; for(int i = 1; i <= 8; i++) p = p + Distance(suc, goal, i); return p + suc.g; //f = h + g; default: break; } } int error(Node suc,Node goal) {//计算错位个数 int w,i; w=0; for(i=0;i<9;i++){ if(suc.data[i]!=goal.data[i]) w++; } return w; } double Distance(Node suc, Node goal, int i) {//计算方格的错位距离 int k,h1,h2;
    for(k = 0; k < 9; k++) { if(suc.data[k] == i)h1 = k; if(goal.data[k] == i)h2 = k; } return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3)); } ///////////////计算 f 值部分-结束////////////////////////////// ///////////////////////扩展后继节点部分的函数-开始///////////////// int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,int m) {//判断子节点是否属于 OPEN 或 CLOSED 表并作出相应的处理 Node * temp = NULL; int flag = 0; if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL)) { if(Belong(*suc,Open) != NULL) temp = Belong(*suc,Open); else temp = Belong(*suc,Closed); if(((*suc)->g) < (temp->g)) { temp->parent = (*suc)->parent; temp->g = (*suc)->g; temp->f = (*suc)->f; flag = 1; } } else { Putinto(* suc, Open); (*suc)->f = Fvalue(**suc, goal, m); } return flag; } int Canspread(Node suc, int n) {//判断空格可否向该方向移动，，，表示空格向上向下向左向右移 int i,flag = 0; for(i = 0;i < 9;i++) if(suc.data[i] == 0)break; switch(n) { case 1: if(i/3 != 0)flag = 1;break; case 2:
    if(i/3 != 2)flag = 1;break; case 3: if(i%3 != 0)flag = 1;break; case 4: if(i%3 != 2)flag = 1;break; default:break; } return flag ; } void Spreadchild(Node * child,int n) {//扩展 child 节点的字节点 n 表示方向，，，表示空格向上向下向左向右移 int i,loc,temp; for(i = 0;i < 9;i++) child->data[i] = child->parent->data[i]; for(i = 0;i < 9;i++) if(child->data[i] == 0)break; if(n==0) loc = i%3+(i/3 - 1)*3; else if(n==1) loc = i%3+(i/3 + 1)*3; else if(n==2) loc = i%3-1+(i/3)*3; else loc = i%3+1+(i/3)*3; temp = child->data[loc]; child->data[i] = temp; child->data[loc] = 0; } void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, int m) {//扩展后继节点总函数 int i; Node * child; for(i = 0; i < 4; i++) { if(Canspread(**suc, i+1)) //判断某个方向上的子 节点可否扩展 { 节点 child = (Node *) malloc(sizeof(Node)); child->g = (*suc)->g +1; child->parent = (*suc); //扩展子节点 //算子节点的 g 值 //子节点父指针指向父 Spreadchild(child, i); //向该方向移动空格生
    成子节点 if(BelongProgram(&child, Open, Closed, goal, m)) // 判断子节点是否属于 OPEN 或 CLOSED 表并作出相应的处理 free(child); } } } ///////////////////////扩展后继节点部分的函数-结束////////////////////////////////// Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, int m) {//总执行函数 while(1) { if((*Open)->next == NULL)return NULL; //判断 OPEN 表是否 为空，为空则失败退出 Node * minf = Minf(Open); 出 f 值最小的节点 Putinto(minf, Closed); CLOSED 表中 //从 OPEN 表中取 //将节点放入 if(Equal(minf, *goal))return minf; //如果当前节点是目标 节点，则成功退出 Spread(&minf, Open, Closed, **goal, m); //当前节点不是目标节 点时扩展当前节点的后继节点 } } int Shownum(Node * result) {//递归显示从初始状态到达目标状态的移动方法 if(result == NULL)return 0; else { int n = Shownum(result->parent); printf("第%d 步：",n); for(int i = 0; i < 3; i++) { } printf("\n"); for(int j = 0; j < 3; j++) { if(result->data[i*3+j] != 0) printf(" %d ",result->data[i*3+j]); else printf(" 0 "); } printf("\n");
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料