人工智能-不同搜索策略的算法实现与性能分析

1、石级注铁道丈曇开放卖验项q报告项目题目丕貝搜.索策.嗤曲.篡迭-实理勺性負-分祈.依托课程.信息处.理.愿理学 生姓名龛影.生学生学号20102782所在系部 信息科学与技术学院学科专业鱼圭信.息壬餐指导教师i.i.a二o 一二年十二月课程作业布置卡课程编号：l090309课程名称：信息处理原理作业序号：1作业名称：不同搜索策略的算法实现与性能 分析任课教师：王正友教学单位：信息科学与技术学院电子信息工 程系布置日期:2012-11-16最后提交日期:2012-12-28说明（1）请务必在最后提交日期之前提交作业，除非有特殊情况（如病假等原因，须由辅导 员签字），过期不交者木次作业判为不及格；

2、（2）作业格式参见具体模板；（2）应个人独立完成作业，不得抄袭他人，一经发现，则本次作业以0分计。作业目的（1）通过编程与实验，常握典型搜索策略的概念、算法实现与性能分析。作业内容（1）利用jave/matlab/c（c+）等编程语言，设计和实现一款不同搜索策略的集成演示 软件。（2）该软件至少包含2种搜索算法，其中一种为盲目搜索、另一种为启发式搜索；（3）软件基本功能满足：1）初始状态可以选择由软件随机产生，也可以通过人机交互产生。2）需要对搜索过程和路径提供解释。3）分析和研究存储结构、启发式函数等因索对搜索性能和效率的影响。（4）界面友好。目录1开放实验冃的52开放实验要求53开放实验内

3、容54实验题冃分析55软件总体设计66详细设计实现67程序调试及心得体会118作业自评129参考文献1310附录13摘要本实验项目主要针对不同搜索策略的算法实现和性能比较，主要运用了盲目 搜索中的(bfs)宽度优先搜索算法和(dfs)深度优先搜索算法和启发式搜索算 法中的a算法。本实验项目的内容是八数码问题，在此问题上运用上述各种算法，并实现 各种算法性能的比较。实现的功能包括通过输入八数码问题的初始状态和最终状 态，并选择所用的搜索算法来实现搜索，搜索的中间过程可以通过程序的编写在 界面中一步步展现出来，还能输出相应的性能比较结果。本项目主要运用了 vc+语言进行程序设计，并利用mfc在vi

4、sual c+中进 行可视化编程，通过可视化编程实现界面友好化，并选取不同的算法实现上述的 要求，每种算法的实现有清楚的注释和说明。关键词:搜索策略八数码mfc1开放实验目的通过编程与实验，掌握典型搜索策略的概念、算法实现与性能分析。2开放实验要求1）熟悉和掌握jave/matlab/c（c+）等程序设计方法；2）至少包含2种搜索算法，其中一种为盲目搜索、另一种为启发式搜索;3）界而友好；4）代码结构清晰，注释易懂。3开放实验内容利用jave/matlab/c（c卄）等编程语言，设计和实现一款不同搜索策略的集 成演示软件。以下儿点是程序必须实现的功能。1）初始状态可以选择由软件随机产生，也可以

5、通过人机交互产生。2）需要对搜索过程和路径提供解释。3）分析和研究存储结构、启发式函数等因素对搜索性能和效率的影响。4实验题目分析软件要求实现的是不同搜索策略的算法实现和性能比较，至少包括盲目搜索 策略中的一种和启发式搜索策略中的一种。耍实现该耍求，就要选择一个项目，运用所选择的算法解决该项目，从而再 实现不同算法的性能比较，所以本实验选择了八数码问题。木实验要求初始状态可以选择由软件随机产生，也可以通过人机交互产生， 所以八数码问题要求可以输入初始状态；需要对搜索过程和路径提供解释，所以 此实验给出了详细的搜索过程；还要求分析和研究存储结构、启发式函数等因素 对搜索性能和效率的影响。要求选择

6、一种编程语言，实现一款不同搜索策略的集成演示软件，此处采用 c+语言，并用mfc实现可视化编程，根据需求设计界面，界面屮包括初始状 态输入的模块，最终状态的设定模块，冇演示搜索过程屮每一步骤的搜索过程的 模块，有不同算法选择的模块，最后有不同算法性能比较的模块。5软件总体设计本软件是用于实现八数码问题的。本软件屮包含三种搜索策略，有宽度优先搜索策略、深度优先搜索策略和启 发式搜索策略中的a算法。采用c+和mfc编程实现可视化界面，界面中包括5个模块，初始状态设 定、目标状态设定、搜索过程的演示、算法的选择模块以及性能的展示。6详细设计实现（1）程序中使用到得算法木程序用到了三种搜索算法，分别是

7、bfs （广度优先搜索）、dfs（深度优先 搜索）和a算法。a. bfs算法步骤：1. 每次搜索z前清空open、closed. path三表，并初始化初始状态initstate；2. 将初始节点放入open表屮；3. 判断初始和目标状态goalstate是否相同，如是则成功退出；4. 将open表屮首端第一个节点取岀放入closed表屮；5. 如果open表为空，则失败退出。否则用函数expandnodebfs按left, right, up, down顺序扩展节点。给子节点的深度赋值，定义其父节点 和子节点的指针；6. 判断扩展后的了节点是否和目标节点相同，如是则成功退出，并用 findp

8、ath函数按照其父节点回溯到初始节点以寻找路径，并把所寻每一节 点放入path表中；如果不相同，则把它放入open表末端；7. 转步骤4。广度优先搜索算法程序流程示意图b. dfs算法步骤：1. 将初始节点s放入open表屮，若此节点为口标节点，则得解；2. 若open表为空，则失败退出；3. 把open表中首端第二个节点n移岀，放入closed表中；4. 若节点n的深度等于最大限制深度；则转向厶5. 扩展节点n,产生其全部子节点，并将它们放入open表首端，并给岀返 回n的指针，若节点不能扩展，则转向厶6. 若后继子节点屮冇目标节点，则得解，成功退出。深度优先搜索算法程序流程示意图c. he

9、uristic a 算法步骤：1. 每次搜索之前清空open、closed> path三表，并初始化初始状态 initstate；2. 将初始节点放入open表中；3. 判断初始和目标状态goalstate是否相同，如是则成功退岀；4. 从open表中找到估价值最小的节点（函数evaluate）将其取出放入 closed 表中。5. 如杲open表为空，贝ij失败退出。否则用函数expandheuristic按left,right,up, down顺序扩展节点。给子节点的深度赋值，定义其父节点和子节点 的指针；6. 判断扩展后的子节点是否和口标节点相同，如是则成功退出，并用findpat

10、h函数按照其父节点回溯到初始节点以寻找路径，并把所寻每一节点放入 path表中；如果不是，则判断了节点是否已在closed表和open表中， 如果都不在，则放入open表末端；7. 转步骤4。启发式搜索算法程序流程示意图(2) 程序数据结构描述1. 节点状态表示：定义结构体struct eightpuzzle int depthcun-ent;/节点深度int state9;/节点状态struct eightpuzzle * father;/节点的父节点struct eightpuzzle * child;/节点的了节点;2. open 表 closed 表：用mfc中clist类定义cptr

11、list open;/open 表cptrlist closed;/closed 表cptrlist path;/用于最后存放路径path表(3) 函数说明1 估价函数 int evaluate (eightpuzzle* current, eightpuzzle* goal) 返y|个int型数值，计算状态current屮每个格子的号码与goal屮相应号 码之间的距离之和。取f (n) =d (n) +h(n), h (n) =p(n);2. enum direction left, right, up, down, invalid;direction movedirection(eight

12、puzzle father, eightpuzzle *child, int &x);定义枚举类型direction,判断返回节点扩展时可以移动的方向。3. 主要函数一览：public:bool numbercheck(int state9) ;/检查数据有效性bool ishavepath(eightpuzzle initial, eightpuzzle *goal) ；/检查时候有路径bool searchhcuristico ；/启发式搜索bool seorchbfso ;/广度优先搜索bool searchdfs 0 ; /深度优先搜索int evaluate (eightpu

13、zzle* current, eightpuzzle* goal);/计算估价函数取 p (n)eightpuzzle initstale;/初女台节，点eightpuzzle goal state;/ 目标节点、cptrli st open;/open 表cptrlist closed;/closed 表cptrlist path;/用于最后存放路径path表int m_ndepth;eightpuzzle *currentstep;private:enum direction left, right, up, down, invalid;void findpath(eightpuzzle

14、*finainode, eightpuzzle *initnode) ;/按各节点父 节点寻找路径direction movedirection(eightpuz刁le father, eightpuzzle *child, int &x);/判 断口j移动方向bool isinclosed(eightpuzzle *curnode);/判断当前扩展的节点是否已存在 closed表屮bool is inopen (eightpuzzle* curnode) ;/判断当前扩展的节点是否己存在open 表屮bool comparestate(eightpu兄le * stateone, e

15、ightpuzzle * stateanother) ；/比较 两个节点状态时候相同void copy8puzzle (eightpuzzle *stateonc, eightpuzzle stateanother);/复制节 点状态bool movetodown (ei gh tpu/zle *fa therstate, eightpuzzle * childstate) ;/向 下不多 动bool movetoup(eightpuzzle *fatherstate, eightpuzzle *childstate) ；/向上移 动bool move to right (eightpuzzl

16、e *fatherstate, eightpuzzle *childstste) ;/向右 移动bool movetoleft(eightpuzzle *fatherstate, eightpuzzle *ch订dstate);/向左移 动bool expandnodebfs(eightpuzzle *newnode, eihtpuz刁1e *noden, ei£htpu;:zle* pinit) ;/广度优先搜索屮扩展节点bool expandnodedfs(eightpuzzle *newnode, eightpuzzle *noden, eightpuzzle* pinit);

17、/深度优先搜索中扩展节点bool expa ndnodeheurist ic (eightpuzzle * new node, eighlpuzzle* pstarl) ;/丿訂发式 搜索中扩展节点(4)界面设计初始状态宋霹过程11230r1 7r5目标状态0 |0 0橄索松广度优先舷魅am法|状态理示,7程序调试及心得体会通过网上查找资料，找到了宽度优先搜索、深度优先搜索和启发式搜索的能 够运行的程序代码，但是在把三种算法合为一个程序时，总是岀现错误，由于自 己对c+编程的不熟悉，总是改不成功，后來找了一个能够运行的带有界面的软 件，但是对t mfc编程以前没有涉及过，所以通过网上查找资料，

18、学习了 mfc 编程最初级的步骤，并能够运行自c所找到的软件，后又根据实验要求，在相应 的代码小修改了所需的算法，以满足有盲口搜索算法和启发式搜索算法，并修改 了性能比较，修改过程屮，也是通过搜集的代码，把其整理，找到自己需要的部 分，在照样了修改在口己的程序中。在该软件中，自己又对界面的尺寸，位置等做了相应的修改，以使其更加的 友好化。在本软件小还有待学习的即是界而的显示的代码编写，以及齐种控件的使 用。通过木次试验，我对bfs、dfs以及启发式搜索有了更加深入的了解。在试验中，通过用不同的测试数据结果来看，宽度优先搜索方法能够保证在搜索树屮找到一条通向目标节点的最短途径（所用操作符最少），

19、只耍结点间可 以到达，就一定可以找到一个最优解。而深度优先搜索具有深度界限，当搜索深度达到深度界限时，停止搜索。所 以，深度优先搜索有可能会得不到结果，是一种不安全的搜索方法。但是当结果 在搜索界限内吋，可以快速的得到结果，时间效率高。故对于深度优先搜索，如 何去定义一个较好的搜索界限，是下一步需要继续改进的方面。相比z下，启发式搜索看来更加实用冇效，能在较复杂情况下求得更加优质 的解，但是对于估价函数的定义趋向多元化，如何更好地定义一个估价函数有待 深入讨论。主观认识上，认识到了自己的编程能力很大程度的需要提高，所以在本次实 验后，我会根据自己的能力口主去学习有关的编程。8作业自评自评指标：

20、a b c d e算法实现：盲口搜索启发式搜索界面设计：主界面设计其它窗体界血设计性能分析：存储结构abaab启发式函数9参考文献1 刑建垒，用mfc动态编程实现8数码问题求解j南京师范大学.2 郑阿奇,丁有和,visual c+教程北京:清华大学出版社.20033 张仰森，黄改娟等，人工智能教程高等教育岀版社200& 034 吉跟林，数据结构教程北京：电了工业出版社.20035 胡敏杰a*算法的探讨及其对八数码问题的实现j漳州师范学院学报(自 然科学版).2005(03)6 欧阳林艳八数码问题的探索算法比较j洛阳师范学院学报.2011(08)10附录程序代码三种算法的实现 8puzz

21、le.cpp: implementation of the c8puzzle class.bool cspuzzle:searchbfs() open.removeall();closed.removeall();pathrenwveall();每次搜索之前清空各链表initstate.depthcurrent=o;/q 始状态参数initstate.child=null;initstate.father=null;eightpuzzle *newnode=new eightpuzzle,*pinit;copy8puzzle(&i nitstate,newnode);pinit=new

22、node;if(comparestate(&initstate,&goalstate) /判断初始和目标状态是否相同，如是则成功退 出path.addtail(newnode);return true;open.addhead(nevvnode);/初始节点放入 open 表中eightpuzzle* noden;while(l)if(openisempty()如open表空，失败退出return false;noden = (eightpuzzle *)open.gethead();closed.addtail(noden);/把open表首端节点取出放入closed表末端o

23、pen.removeheadq;if(noden->depthcurrent<200)eightpuzzle *newnode = new eightpuzzle; if(movetoleft(noden, nevvnode) if(expandnodebfs(newnode,noden,pinit)/向左扩展节点return true;elsedelete newnode;eightpuzzle *newnodel = new eightpuzzle; if(movetoright(noden newnodel) if(expandnodebfs(newnodel,noden,p

24、init)/向右扩展节点 return true;elsedelete newnodel;eightpuzzle *newnode2 = new eightpuzzle; if(movetoup(noden, newnode2) if(expandnodebfs(newnode2,noden,pinit)/ 向上扩展节点 return true;elsedelete nevvnode2;eightpuzzle *newnode3 = new eightpuzzle; if(movetodown(noden newnode3) if(expandnodebfs(newnode3,noden,pi

25、nit)/ 向下扩展节点return true;elsedelete newnode3;bool c8puzzle: :searchheuristic() open.removeall();closed.removealk);pathremoveall();每次搜索之前清空各链表initstate.depthcurrent=o;/j 始状态参数initstate.child=null;initstate.father=null;eightpuzzle *newnode=new eightpuzzle,*pinit;copy8puzzle(&i nitstate,newnode); pi

26、nit=newnode;if(comparestate(&initstate,&goalstate) 判断初始和目标状态是否相同，如是则成功退 出path.addtail(newnode);return true;open.addhead(nevvnode);/e初始节点放入 open 表中while(l)if(open.isempty()/如 open 表空，失败退出return false;eightpuzzle *noden;eightpuzzle *pheadstate=(eightpuzzle*)open<gethead(); int nnextexpand=o

27、npricemin=pheadstate->depthcurrent+ evaluate(pheadstate9&goalstate)+1;for(int k=0;k<open.getcount();k+)/寻找 open 表中估价值最小的节点 eightpuzzle *popenstate;popenstate=(eightpuzzle *)openegetat(open.findindex(k);int neval=popenstate->depthcurrent+evaluate(popenstate,&goalstate);if(neval<np

28、ricemin) npricemin=neval; noden=popenstate; nnextexpand=k;将估价函数最小的节点从open表删除，加入到close表中open.removeat(open.findindex(nnextexpand); closed.addtail(noden);if(noden->depthcurrent<200) eightpuzzle *newnode = new eightpuzzle; if(movetoleft(noden, newnode) if(expandnodeheuristic(newnode,pinit)/ 向左扩展节

29、点 return true;elsedelete newnode;eightpuzzle *newnodel = new eightpuzzle;if(movetoright(noden, newnode 1) if(expandnodeheuristic(newnodel,pinit)/向右扩展节点 return true;elsedelete nevvnodel;eightpuzzle *newnode2 = new eightpuzzle; if(movetoup(noden, newnode2) if(expandnodeheuristic(newnode29pinit)/ 向上扩展节

30、点 return true; elsedelete newnode2;eightpuzzle *newnode3 = new eightpuzzle;if(movetodown(noden newnode3)if(expandnodeheuristic(newnode3,pinit)/向下扩展节点 return true;elsedelete newnode3;bool c8puzzle:movetoleft(eightpuzzle *fatherstate, eightpuzzle *childstate)int x=0;if(movedirection(fatherstate,childs

31、tate,x)=left) return false;childstate->statex = fatherstate->statex-l;/3s换数字 0 和 0 左方数字的位置childstate->statex-l = 0;return true;bool c8puzzle:movetoright(eightpuzzle *fathcrstate. eightpuzzle *childstate) int x=0;if(movedirection(fatherstate,childstate,x)=right)return false;childstate->st

32、atex = fathcrstate>statex+l;交换数字 0 和 0 右方数字的位置childstate->statex+l = 0;return true;bool c8puzzle:movetoup(eightpuzzle *fatherstate, eightpuzzle *childstate) int x=0;if(movedirection(fatherstate,childstate,x)=up)return false;childstate->statex = fatherstate->statex-3 ;/3s换数字 0 和 0 正上方数字的位

33、置childstate->statex-3 = 0;return true;bool c8puzzle:movetodown(eightpuzzle *fatherstate, eightpuzzle *childstate)int x=0;if(movedirection(fatherstate,childstate,x)=down)return false;childstate->statex = fatherstate->statex+3;/换数字 0 和 0 正下方数字的位置childstate->statex+3 = 0;return true;void c8

34、puzzle: copy8puzzle(eightpuzzle *stateone, eightpuzzle *stateanother) stateanother->depthcurrent=stateone->depthcurrent;stateanother->father=stateone->father; stateanother->child=stateone->child;for(int i=0;i<9;i+) stateanother->statei=stateone->statei; bool c8puzzle:compa

35、restate(eightpuzzle *stateone, eightpuzzle *stateanother)for(int i=0;i<9;i+)if(stateone->statei!=stateanother->statei)return false;return true;int c8puzzle:evaluate(eightpuzzle current, eightpuzzle *goal)int xcur9,ycur9,xgoal9,ygoal9;/存 9 个坐标 int ij;int value=o;for(i=0;i<3;i+) for(j=0;j&

36、lt;3;j+)xcurcurrent->state3*i+j=i; ycurcurrent->state3*i+j=j; xgoalgoal->state3*i+j=i; ygoalgoal->state3*i+j=j; for(i=l;i<9;i+) value=value+abs(xcuri-xgoali)+abs(ycuri-ygoali); return value;bool c8puzzle:ishavepath(eightpuzzle *initial, eightpuzzle *goal)int resl=0,res2=0;int ij;int k

37、=0,l=0;int curl8,cur28; for(i=0;i<9;i+)if(initial->statei!=o)curlk=initial->statei;k+;for(i=0;i<9;i+)if(goal->statei!=0)cur2l=goal->statei;l+; for(i=0;i<7;i+)for(j=i+l;j<8;j+)if(curli>curlj) resl+;for(i=0;i<7;i+) for(j=i+l;j<8;j+)if(cur2i>cur2j)res2+; resl=resl%2;

38、 res2=res2 % 2;if(resl=res2)return true;elsereturn false;bool c8puzzle:isinopen(eightpuzzle *curnode)if(open.isempty()return false;for(int i=0;i<open.getcount();i+)eightpuzzle* pcur=(eightpuzzle*)open.getat(open.findindex(i);if(comparestate(pcur,curnode)return true;if(curnode->depthcurrent<

39、pcur->depthcurrent)copy 8puzzle(curnode9pcur);return false;bool c8puzzle:isinclosed(eightpuzzle *curnode)if(closed.isempty() return false;for(int i=();i<closed.getcount();i+)eightpuzzle* pcur=(eightpuzzle*)closed.getat(closed.findindex(i);if(comparestate(pcur,curnode)return true;return false;v

40、oid cspuzzle: :findpath(eightpuzzle * finalnode, eightpuzzle *initnode)while(finalnode!=initnode)path.addhead(finalnode);finalnode=finalnode->father;path.addhead(initnode);bool c8puzzle:expandnodeheuristic(eightpuzzle *newnode,eightpuzzle * pinit)if(!comparestate(newnode, &goalstate)if(number

41、check(newnode->state)&&(!isinopen(newnode) && (!isinclosed(newnode)open.addtail(nevvnode); return false;else return false;elsefindpath(newnode, pinit);return true;cspuzzle:direction c8puzzle:movedirection(eightpuzzle *father,eightpuzzle *child,int& x) for(int i=0;i<9;i+)if(

42、father->statei=o)x=i；for(intj=0;j<9;j+)child->statej=father->statej;child >depthcuitent=fathcr>depthcmtciit+l;child->father=father;child->child=null;if (x=0)li(x=3)li(x=6) return left;/can not move leftif (x=2)ll(x=5)ll(x=8) return right;/can not move rightif (x=0)ll(x=l)ll(x

43、=2) return up;/can not move upif (x=6)ll(x=7)ll(x=8) return down;/can not move downreturn invalid;bool c8puzzle:numbercheck(int state9) int cur9=0;for(int i=0;i<9;i+)if(statei<0llstatei>8)/限制数字范围 0-8return false;curstatei+;for(intj=0;j<9;j+)/j断有无空格(未填写任何数字)if(curj=o)return false;return t

44、rue;bool c8puzzle:expandnodebfs(eightpuzzle *ncwnode. eightpuzzle *noden,eightpuzzle *pinit)if(!comparestate(newnode, &goalstate)/判断初始和目标状态 goalstate 是否相同，如是则 成功退出 if(numbercheck(newnode->state)if( noden->father != null)if(!comparestate(newnode, noden->father)open.addtail(newnode);elseo

45、pen<addtail(newnode);return false;elsefindpath(newnode, pinit);return true;bool c8puzzle:searchdfs()open>removeaii();closed.removeall();pathremoveall();每次搜索之前清空各链表initstate.depthcurrent=o;/j 始状态参数initstate.child=null;initstate.father=null;eightpuzzle *newnode=new eightpuzzlepinit;copy8puzzle(&

46、amp;i nitstate,newnode);pinit=newnode;if(comparestate(&initstate,&goalstate) /判断初始和目标状态是否相同，如是则成功退出path.addtail(nevvnode);return true;open.addhead(newnode);/e初始节点放入 open 表中eightpuzzle* noden;while(l)if(openisempty()如open表空，失败退出return false;noden = (eightpuzzle *)open.gethead();closed.addtail

47、(noden);/把open表首端节点取出放入closed表末端open.removehead(); if(noden->depthcurrent<maxdepth) eightpuzzle *newnode = new eightpuzzle; if(movetoleft(noden, newnode) if(expandnodedfs(newnode,noden,pinit)/向左扩展节点 return true;elsedelete newnode;eightpuzzle *newnodel = new eightpuzzle; if(movetoright(noden, n

48、ewnodel) if(expandnodedfs(newnodel,noden,pinit)/ 向右扩展节点 return true;elsedelete newnodel;eightpuzzle *newnode2 = new eightpuzzle; if(movetoup(noden, newnode2) if(expandnodedfs(newnode2,noden,pinit)/向上扩展节点return true;elsedelete newnode2;eightpuzzle *newnode3 = new eightpuzzle; if(movetodown(noden, new

49、node3) if(expandnodedfs(newnode3,noden,pinit)/向下扩展节点 return true;elsedelete newnode3;else if(noden->depthcurrent=maxdepth)/:节点 n 的深度等于最大限制深度，若 open表为空，则失败退出if(open.isempty()return false;bool c8puzzle:expandnodedfs(eightpuzzle newnode, eightpuzzle *noden, eightpuzzle *pinit)if(!comparestate(newnod

50、e, &goalstate)/判断初始和目标状态 goalstate 是否相同，如是则 成功退出if(numbercheck(newnode->state)if( noden->father != null) if(!comparestate(nevvnode, noden->father)open.addhead(newnode); 扩展节点n,产生其全部子节点，并将 它们放入open表首端elseopen.addtail(newnode);return false;elsefindpath(newnode9 pinit);return true;void cmy8

51、puzzledig:onbuttonheuristic()inputnumbero;if(!(m_8puzzie>numbercheck(m_8puzzlejnitstate<state)&&m_8puzzle.numbercheck(m_8puzzle<goalstate.state) messagebox(”数据输入有误，请检查！ ！ ”)；return;if(!(m_8puzzle.ishavepath(&(m_8puzzle.initstate),&(m_8puzzle>goalstate)messagebox(h初始状态无法到达

52、目标状态，n请重新输入!,remindh);return;time_t start=clock();if(m_8puzzie>searchheuristic()time_t end=clock();m_s trsta teremind .f orma t( * *成功啦，总共需要走%d步，扩展过%d个节点, 用时 %d ms*',m_8puzzle.path.getcount()-l,m_8puzzle.closed.getcount(),end-start);u pdatedata(false);elsem_strstateremind.format(h失败，请重新来过”)；u

53、 pdatedata(false);m_ncurstepcount=0; this->getdlgitem(idc_button_showpath)->enablewindow(true);this->getdlgitem(idc_b()tt()n_sh()wpre)->enablewindow(false);数据的显示以及性能的测试void cmy8puzzledlg:onbuttonbfs() inputnumber();if(!(m_8puzzle.numbercheck(m_8puzzle.initstate.state)&&m_8puzzle.

54、numbercheck(m_8puzzle<goalstate.state) messagebox数据输入有误，请检査！”)；return;if(!(m_8puzzle.lshavepath( & (m_8puzzleinitstate)，&(m_8puzzlegoalstate)messageboxc初始状态无法到达目标状态，n请重新输入!","remind”)；return;time_t start=clock();if(m_8puzzle.searchbfs()time_t end=clock();m_strstateremind.format(

55、1 *成功啦，总共需要走%d步，扩展过%d个节点, 用时%dms”,m_8puzzle.path.getcount()-lm_8puzzle.closed.getcount()9end-start);updatedata(false);elsem_strstateremind.format失败，请重新来过”)；updatedata(false);m_ncurstepcount=0; this->getdlgitem(idc_button_showpath)->enablewindow(true);this->getdlgitem(idc_botton_showpre)->enablewindow(false);void cmy8puzzledlg:onbuttonnext()if(m_ncurstepcount=0&&(!m_8puzzle.pathisempty()m_strstateremind.format(h总共需要走%d步,现在是初始状态"， m_8puzzle.path.getcount()-l);m_ncurstepcount+;m_nprocess00=m_8puzzle.initstate.state0;m_nprocess01 =m_8p