版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
奥鹏大连理工大学远程与继续教育学院《人工智能》课程设计学习中心:***专业:计算机科学与技术年级:***学号:***学生:***题目:题目一:A*算法1.谈谈你对本课程学习过程中的心得体会与建议?A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。对于一般的有序搜索,总是选择f值最小的节点作为扩展节点。通过本学期学习,我熟悉启发式搜索的定义、估价函数和算法过程,并利用A*算法求解了8数码难题,理解了求解流程和搜索顺序。本次课程实践过程中巩固了所学的知识,通过实践也提高了自己的编程和思维能力,收获很多。2.《人工智能》课程设计,从以下5个题目中任选其一作答。题目一:A*算法一、算法思路A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。对于一般的有序搜索,总是选择f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的,所以,可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的代价以及从节点n到达目标节点的代价。A*算法基本步骤1)生成一个只包含开始节点n0的搜索图G,把n放在一个叫OPEN的列表上。2)生成一个列表CLOSED,它的初始值为空。3)如果OPEN表为空,则失败退出。4)选择OPEN上的第一个节点,把它从OPEN中移入CLPSED,称该节点为n。5)如果n是目标节点,顺着G中,从n到n的指针找到一条路径,获得解决方案,成功退出(该指针定义了一个搜索树,在第7步建立)。6)扩展节点n,生成其后继结点集M,在G中,n的祖先不能在M中。在G中安置M的成员,使他们成为n的后继。7)从M的每一个不在G中的成员建立一个指向n的指针(例如,既不在OPEN中,的这些成员加到OPEN中。对M的每一个已在OPEN中或也不在CLOSED中)。把M1CLOSED中的成员m,如果到目前为止找到的到达m的最好路径通过n,就把它的指针指向n。对已在CLOSED中的M的每一个成员,重定向它在G中的每一个后继,以使它们顺着到目前为止发现的最好路径指向它们的祖先。8)按递增f*值,重排OPEN(相同最小f*值可根据搜索树中的最深节点来解决)。9)返回第3步。在第7步中,如果搜索过程发现一条路径到达一个节点的代价比现存的路径代价低,就要重定向指向该节点的指针。已经在CLOSED中的节点子孙的重定向保存了后面的搜索结果,但是可能需要指数级的计算代价。二、算法程序框图三、程序代码#include#include#includeusingnamespacestd;constintROW=3;//行数constintCOL=3;//列数constintMAXDISTANCE=10000;//最多可以有的表的数目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;//一个表和目的表的距离intdep;//t深度intindex;//节点的位置}Node;Nodesrc,dest;//父节表目的表vectornode_v;//存储节点boolisEmptyOfOPEN()//open表是否为空{for(inti=0;i<node_v.size();i++){if(node_v[i].dist!=MAXNUM)returnfalse;}returntrue;}boolisEqual(intindex,intdigit[][COL])//判断这个最优的节点是否和目的节点一样{for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++){if(node_v[index].digit[i][j]!=digit[i][j])returnfalse;}returntrue;}ostream&operator<<(ostream&os,Node&node){for(inti=0;i<ROW;i++){for(intj=0;j<COL;j++)os<<node.digit[i][j]<<'';os<<endl;}returnos;}voidPrintSteps(intindex,vector&rstep_v)//输出每一个遍历的节点深度遍历{rstep_v.push_back(node_v[index]);index=node_v[index].index;while(index!=0){rstep_v.push_back(node_v[index]);index=node_v[index].index;for(inti=rstep_v.size()-1;i>=0;i--)//输出每一步的探索过程cout<<"Step"<<rstep_v.size()-i<<endl<<rstep_v[i]<<endl;}voidSwap(int&a,int&b){intt;t=a;a=b;b=t;}voidAssign(Node&node,intindex){for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++)node.digit[i][j]=node_v[index].digit[i][j];}intGetMinNode()//找到最小的节点的位置即最优节点{intdist=MAXNUM;intloc;//thelocationofminimizenodefor(inti=0;i<node_v.size();i++){if(node_v[i].dist==MAXNUM)continue;elseif((node_v[i].dist+node_v[i].dep)<dist){loc=i;dist=node_v[i].dist+node_v[i].dep;}}returnloc;}boolisExpandable(Node&node){for(inti=0;i<node_v.size();i++){if(isEqual(i,node.digit))returnfalse;returntrue;}intDistance(Node&node,intdigit[][COL]){intdistance=0;boolflag=false;for(inti=0;i<ROW;i++)for(intj=0;j<COL;j++)for(intk=0;k<ROW;k++){for(intl=0;l<COL;l++){if(node.digit[i][j]==digit[k][l]){distance+=abs(i-k)+abs(j-l);flag=true;break;}elseflag=false;}if(flag)break;}returndistance;}intMinDistance(inta,intb){return(a<b?a:b);}voidProcessNode(intindex){intx,y;boolflag;for(inti=0;i<ROW;i++){for(intj=0;j<COL;j++){if(node_v[index].digit[i][j]==0){x=i;y=j;flag=true;break;}elseflag=false;if(flag)break;}Nodenode_up;Assign(node_up,index);//向上扩展的节点intdist_up=MAXDISTANCE;if(x>0){Swap(node_up.digit[x][y],node_up.digit[x-1][y]);if(isExpandable(node_up)){dist_up=Distance(node_up,dest.digit);node_up.index=index;node_up.dist=dist_up;node_up.dep=node_v[index].dep+1;node_v.push_back(node_up);}}Nodenode_down;Assign(node_down,index);//向下扩展的节点intdist_down=MAXDISTANCE;if(x<2){Swap(node_down.digit[x][y],node_down.digit[x+1][y]);if(isExpandable(node_down)){dist_down=Distance(node_down,dest.digit);node_down.index=index;node_down.dist=dist_down;node_down.dep=node_v[index].dep+1;node_v.push_back(node_down);}}Nodenode_left;Assign(node_left,index);//向左扩展的节点intdist_left=MAXDISTANCE;if(y>0){Swap(node_left.digit[x][y],node_left.digit[x][y-1]);if(isExpandable(node_left))dist_left=Distance(node_left,dest.digit);node_left.index=index;node_left.dist=dist_left;node_left.dep=node_v[index].dep+1;node_v.push_back(node_left);}}Nodenode_right;Assign(node_right,index);//向右扩展的节点intdist_right=MAXDISTANCE;if(y<2){Swap(node_right.digit[x][y],node_right.digit[x][y+1]);if(isExpandable(node_right)){dist_right=Distance(node_right,dest.digit);node_right.index=index;node_right.dist=dist_right;node_right.dep=node_v[index].dep+1;node_v.push_back(node_right);}}node_v[index].dist=MAXNUM;}intmain()//主函数{intnumber;cout<<"Inputsource:"<<endl;for(inti=0;i<ROW;i++)//输入初始的表for(intj=0;j<COL;j++){cin>>number;src.digit[i][j]=number;}src.index=0;src.dep=1;cout<<"Inputdestination:"<<endl;//输入目的表for(intm=0;m<ROW;m++)for(intn=0;n<COL;n++){cin>>number;dest.digit[m][n]=number;node_v.push_back(src);//在容器的尾部加一个数据cout<<"Search..."<<endl;clock_tstart=clock();while(1){if(isEmptyOfOPEN()){cout<<"Cann'tsolvethisstatement!"<<endl;return-1;}else{intloc;//thelocationoftheminimizenode最优节点的位置loc=GetMinNode();if(isEqual(loc,dest.digit)){vectorrstep_v;cout<<"Source:"<<endl;cout<<src<<endl;PrintSteps(loc,rstep_v);cout<<"Successful!"<<endl;cout<<"Using"<<(clock()-start)/CLOCKS_PER_SEC<<"seconds."<<endl;break;}elseProcessNode(loc);}}return0;}四、程序运行效果图(初始状态)804765(结束状态)五、对于重排九宫问题的启发式函数给定九宫格的初始状态,要求在有限步的操作内,使其转化为目标状态,且所得到的解是代价最小解(即移动的步数最少)。如:初始格局目标状态#include"iostream.h"#include#include#include#includestaticinttarget[9]={1,2,3,8,0,4,7,6,5};//classdefinitionclasseight_num{private:intnum[9];intnot_in_position_num;intdeapth;inteva_function;8124376512384765public:eight_num*parent;eight_num*leaf_next;eight_num*leaf_pre;eight_num(intinit_num[9]);eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){num[0]=num1;num[1]=num2;num[2]=num3;num[3]=num4;num[4]=num5;num[5]=num6;num[6]=num7;num[7]=num8;num[8]=num9;}eight_num(void){for(inti=0;i<9;i++)num[i]=i;}voidcul_para(void);voidget_numbers_to(intother_num[9]);intget_nipn(void){returnnot_in_position_num;}intget_deapth(void){returndeapth;}intget_evafun(void){returneva_function;}voidset_num(intother_num[9]);voidshow(void);eight_num&operator=(eight_num&);eight_num&operator=(intother_num[9]);intoperator==(eight_num&);intoperator==(intother_num[9]);};//计算启发函数g(n)的值voideight_num::cul_para(void){inti;inttemp_nipn=0;for(i=0;i<9;i++)if(num[i]!=target[i])temp_nipn++;not_in_position_num=temp_nipn;if(this->parent==NULL)deapth=0;elsedeapth=this->parent->deapth+1;eva_function=not_in_position_num+deapth;}//构造函数1eight_num::eight_num(intinit_num[9]){for(inti=0;i<9;i++)num[i]=init_num[i];}//显示当前节点的状态voideight_num::show(){cout<<num[0];<p="">cout<<"";cout<<num[1];<p="">cout<<"";cout<<num[2];<p="">cout<<"\n";cout<<num[3];<p="">cout<<"";cout<<num[4];<p="">cout<<"";cout<<num[5];<p="">cout<<"\n";cout<<num[6];<p="">cout<<"";cout<<num[7];<p="">cout<<"";cout<<num[8];<p="">cout<<"\n";}//复制当前节点状态到一个另数组中voideight_num::get_numbers_to(intother_num[9]){for(inti=0;i<9;i++)other_num[i]=num[i];}//设置当前节点状态(欲设置的状态记录的other数组中)voideight_num::set_num(intother_num[9]){for(inti=0;i<9;i++)num[i]=other_num[i];}eight_num&eight_num::operator=(eight_num&another_8num){for(inti=0;i<9;i++)num[i]=another_8num.num[i];not_in_position_num=another_8num.not_in_position_num;deapth=another_8num.deapth+1;eva_function=not_in_position_num+deapth;return*this;}eight_num&eight_num::operator=(intother_num[9]){for(inti=0;i<9;i++)num[i]=other_num[i];return*this;}inteight_num::operator==(eight_num&another_8num){intmatch=1;for(inti=0;i<9;i++)if(num[i]!=another_8num.num[i]){match=0;break;}if(match==0)return0;elsereturn1;}inteight_num::operator==(intother_num[9]){intmatch=1;for(inti=0;i<9;i++)if(num[i]!=other_num[i]){match=0;break;}if(match==0)return0;elsereturn1;}//classdefinitionover//空格向上移intmove_up(intnum[9]){for(inti=0;i<9;i++)if(num[i]==0)break;if(i<3)return0;else{num[i]=num[i-3];num[i-3]=0;return1;}}//空格向下移intmove_down(intnum[9]){for(inti=0;i<9;i++)if(num[i]==0)break;if(i>5)return0;else{num[i]=num[i+3];num[i+3]=0;return1;}}//空格向左移intmove_left(intnum[9]){for(inti=0;i<9;i++)if(num[i]==0)break;if(i==0||i==3||i==6)return0;else{num[i]=num[i-1];num[i-1]=0;return1;}}//空格向右移intmove_right(intnum[9]){for(inti=0;i<9;i++)if(num[i]==0)break;if(i==2||i==5||i==8)return0;else{num[i]=num[i+1];num[i+1]=0;return1;}}//判断可否解出inticansolve(intnum[9],inttarget[9]){inti,j;intcount_num,count_target;for(i=0;i<9;i++)for(j=0;j<i;j++)<p="">{if(num[j]<num[i]&&num[j]!=0)<p="">count_num++;if(target[j]<target[i]&&target[j]!=0)<p="">count_target++;}if((count_num+count_target)%2==0)return1;elsereturn0;}//判断有无重复intexisted(intnum[9],eight_num*where){eight_num*p;for(p=where;p!=NULL;p=p->parent)if(*p==num)return1;return0;}//寻找估价函数最小的叶子节点eight_num*find_OK_leaf(eight_num*start){eight_num*p,*OK;p=OK=start;intmin=start->get_evafun();for(p=start;p!=NULL;p=p->leaf_next)if(min>p->get_evafun()){OK=p;min=p->get_evafun();}returnOK;}//主函数开始intmain(void){doubletime;clock_tStart,Finish;intmemery_used=0,step=0;intnum[9];intflag=0;//是否输入错误标志,1表示输入错误intbingo=0;//是否查找成功标志,1表示成功inti,j;cout<<"Pleaseinputthenumber(0fortheblank):\n";for(i=0;i<9;i++){flag=0;cin>>num[i];for(j=0;j<i;j++)<p="">if(num[i]==num[j])flag=1;if(num[i]<0||num[i]>8||flag==1){i--;cout<<"Illeglenumber!\tReinput!\n";}}eight_numS(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used++;cout<<"Nowtheinitialnumbersare:\n";S.show();cout<<"AndtheTargetis:\n";Target.show();if(!icansolve(num,target)){cout<<"Noonecansolveit!\n";cin>>i;return1;}Start=clock();eight_num*OK_leaf=&S,*leaf_start=&S,*new_8num,*p;while(OK_leaf!=NULL&&bingo!=1){OK_leaf=find_OK_leaf(leaf_start);if(*OK_leaf==Target){bingo=1;break;}p=OK_leaf->leaf_pre;OK_leaf->get_numbers_to(num);if(move_up(num)&&!existed(num,OK_leaf)){new_8num=neweight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_p
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 胆管癌治疗与护理
- 肾结石的病因及治疗方法
- 糖尿病合并骨质疏松
- 降糖药物治疗护理常规
- 颈椎病的保养方法和护理
- 神经内科运动神经元病
- 动态规划问题分析
- 糖尿病合并脑梗护理
- 有关转基因食品安全性的探讨
- 厨余垃圾堆肥的过程
- 第五单元测试卷(单元测试)-2024-2025学年统编版六年级上册语文
- 五级应急救援员职业鉴定考试题库(含答案)
- 第7课 实践出真知-【中职专用】2024年中职思想政治《哲学与人生》金牌课件(高教版2023·基础模块)
- 《电工电子技术基础》高职全套教学课件
- 高考英语单词3500记忆短文40篇
- 国开电大-工程数学(本)-工程数学第4次作业-形考答案
- 淋巴瘤教学讲解课件
- 全国文明单位测评体系(2020年版)
- T/CEC 162-2018 电站锅炉炉膛检修平台_(高清-最新版)
- 【职业规划】自动化专业大学生职业生涯规划PPT
- 航模遥控器ET07使用说明书(全比例10通道遥控器)
评论
0/150
提交评论