A星算法求解八数码技术报告.doc_第1页
A星算法求解八数码技术报告.doc_第2页
A星算法求解八数码技术报告.doc_第3页
A星算法求解八数码技术报告.doc_第4页
A星算法求解八数码技术报告.doc_第5页
已阅读5页,还剩10页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

A*算法求解八数码问题l open 表、closed 表数据结构的选择:1) 把s放入open表,记f=h,令closed为空表。2) 重复下列过程,直到找到目标节点为止。若open表为空表,则宣告失败。3) 选取open表中未设置过的具有最小f值的节点为最佳节点bestnode,并把它放入closed表。4) 若bestnode为一目标节点,则成功求得一解。5) 若bestnode不是目标节点,则扩展之,产生后继节点succssor。6) 对每个succssor进行下列过称:a) 对每个succssor返回bestnode的指针。b) 计算g(suc)=g(bes)+k(bes,suc)。c) 如果succssore open,称此节点为old,并填到bestnode的后继节点表中。d) 比较新旧路劲代价。如果g(suc)g(old),则重新确定old的父辈节点为bestnode,记下较小代价g(old),并修真f(old)值。e) 若至old节点的代价较低或一样,则停止扩展节点。f) 若succssore不再closed表中,则看其是否在closed表中。g) 若succssore在closed表中,则转向(c)。h) 若succssore既不在open表中,又不在closed表中,则把它放入open表中,并添入bestnode后裔表中,然后转向(7)。i) 计算f值j) Go loopl 节点的数据结构:static int target9=1,2,3,8,0,4,7,6,5; 全局静态变量,表示目标状态class eight_numprivate:int num9; 定义八数码的初始状态int not_in_position_num; 定义不在正确位置八数码的个数int deapth; 定义了搜索的深度int eva_function; 评价函数的值,每次选取最小的进行扩展public:eight_num* parent; 指向节点的父节点eight_num* leaf_next; 指向open表的下一个节点eight_num* leaf_pre; 指向open 表的前一个节点 初始状态的构造函数 eight_num(int init_num9); eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)eight_num(void) 计算启发函数g(n)的值void eight_num:cul_para(void)显示当前节点的状态void eight_num:show()复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9)设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)eight_num& eight_num:operator=(eight_num& another_8num)eight_num& eight_num:operator=(int other_num9)int eight_num:operator=(eight_num& another_8num)int eight_num:operator=(int other_num9)空格向上移int move_up(int num9)空格向下移int move_down(int num9)空格向左移int move_left(int num9)空格向右移int move_right(int num9)判断可否解出int icansolve(int num9,int target9)判断有无重复int existed(int num9,eight_num *where)寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start)l A*算法求解框图:把m放入open表,记f=h开始Open=nil?选取open表上未设置过的具有最小f值的节点bestnode,放入closed表是失败Bestnode是目标节点?成功是扩展bestnode,产生其后继节点successor否否建立从successor返回bestnode的指针计算g(suc)=g(bes)+k(bes,suc)Suc属于open?Suc属于closed?Suc=old,把它添加到bestnode的后继节点表中g(suc)g(old)?把successor放入open表,添进bestnode的后裔表重新确定old的父辈节点为bestnode,并修正父辈节点的g值和f值,记下g(old)计算f值否否是是否是l 分析估价函数对搜索算法的影响 : 估价函数就是评价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜索(Ordered-Search),它着重看好能否找出解,而不看解离起始结点的距离(深度)。如果估值函数考虑了深度,或者是带权距离(从起始结点到目标结点的距离加权和),那就是A*如果不考虑深度,就是说不要求最少步数,移动一步就相当于向后多展开一层结点,深度多算一层,如果要求最少步数,那就需要用A*。简单的来说A*就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一般性启发价值,合在一起算估整个结点的价值,考虑到八数码问题的特点,在本实验中使用A*算法求解。l 分析 A*算法的特点: A*搜索是一种效的搜索算法,它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:f(n)=g(n)+h(n)。当h(n)是可采纳时,使用Tree-Search的A*算法将是最优的。l 实验结果: l 附录:源代码及其注释#include iostream.h#include #include #include #include static int target9=1,2,3,8,0,4,7,6,5;/class definitionclass eight_numprivate:int num9;int not_in_position_num;int deapth;int eva_function;public:eight_num* parent;eight_num* leaf_next;eight_num* leaf_pre;eight_num(int init_num9);eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)num0=num1;num1=num2;num2=num3;num3=num4;num4=num5;num5=num6;num6=num7;num7=num8;num8=num9;eight_num(void)for (int i=0;i9;i+)numi=i;void cul_para(void);void get_numbers_to(int other_num9);int get_nipn(void)return not_in_position_num;int get_deapth(void)return deapth;int get_evafun(void)return eva_function;void set_num(int other_num9);void show(void);eight_num& operator=(eight_num&);eight_num& operator=(int other_num9);int operator=(eight_num&);int operator=(int other_num9);/计算启发函数g(n)的值void eight_num:cul_para(void)int i;int temp_nipn=0;for (i=0;iparent=NULL)deapth=0;elsedeapth=this-parent-deapth+1;eva_function=not_in_position_num+deapth;/构造函数1eight_num:eight_num(int init_num9)for (int i=0;i9;i+)numi=init_numi;/显示当前节点的状态void eight_num:show()coutnum0;cout ;coutnum1;cout ;coutnum2;coutn;coutnum3;cout ;coutnum4;cout ;coutnum5;coutn;coutnum6;cout ;coutnum7;cout ;coutnum8;coutn;/复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9)for (int i=0;i9;i+)other_numi=numi;/设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)for (int i=0;i9;i+)numi=other_numi;eight_num& eight_num:operator=(eight_num& another_8num)for (int i=0;i9;i+)numi=another_8num.numi;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=(int other_num9)for (int i=0;i9;i+)numi=other_numi;return *this;int eight_num:operator=(eight_num& another_8num)int match=1;for (int i=0;i9;i+)if(numi!=another_8num.numi)match=0;break;if (match=0)return 0;else return 1;int eight_num:operator=(int other_num9)int match=1;for (int i=0;i9;i+)if(numi!=other_numi)match=0;break;if (match=0)return 0;else return 1;/class definition over/*/空格向上移int move_up(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i3)return 0;elsenumi=numi-3;numi-3=0;return 1;/空格向下移int move_down(int num9)for (int i=0;i5)return 0;elsenumi=numi+3;numi+3=0;return 1;/空格向左移int move_left(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i=0|i=3|i=6)return 0;elsenumi=numi-1;numi-1=0;return 1;/空格向右移int move_right(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i=2|i=5|i=8)return 0;elsenumi=numi+1;numi+1=0;return 1;/判断可否解出int icansolve(int num9,int target9)int i,j;int count_num,count_target;for (i=0;i9;i+)for (j=0;ji;j+)if(numjnumi&numj!=0)count_num+;if(targetjparent)if(*p=num)return 1;return 0;/寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start)eight_num *p,*OK;p=OK=start;int min=start-get_evafun();for(p=start;p!=NULL;p=p-leaf_next)if(minp-get_evafun()OK=p;min=p-get_evafun();return OK;/主函数开始int main(void)double time; clock_t Start,Finish;int memery_used=0,step=0;int num9;int flag=0;/是否输入错误标志,1表示输入错误int bingo=0;/是否查找成功标志,1表示成功int i,j;cout请输入数字0-8 (0表示空格):n;for (i=0;inumi;for(j=0;ji;j+)if(numi=numj)flag=1;if (numi8|flag=1)i-;cout数字不合法!t请重输!n;eight_num S(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used+;cout起始数字组是:n;S.show();cout目标数字组是:n;Target.show();if(!icansolve(num,target)couti;return 1;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=new eight_num;new_8num-set_num(num);new_8num-parent=OK_leaf;new_8num-cul_para();new_8num-leaf_pre=p;if(p=NULL)leaf_start=new_8num;elsep-leaf_next=new_8num;p=new_8num;memery_used+;OK_leaf-get_numbers_to(num);if(move_down(num)&!existed(num,OK_leaf)new_8num=new eight_num;new_8num-set_num(num);new_8num-parent=OK_leaf;new_8num-cul_para();new_8num-leaf_pre=p;if(p=NULL)leaf_start=new_8num;elsep-leaf_next=new_8num;p=new_8num;memery_used+;OK_leaf-get_numbers_to(num);if(move_left(num)&!existed(num,OK_leaf)new_8num=new eight_num;new_8num-set_num(num);new_

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论