人工智能.doc

石家庄铁道大学开放实验项目报告项目题目不同搜索策略的算法实现与性能分析依托课程信息处理原理 学生姓名 宋影华 学生学号 20102782 所在系部 信息科学与技术学院 学科专业电子信息工程 指导教师 王正友 二O一二年十二月课程作业布置卡课程编号：L090309课程名称：信息处理原理作业序号：1作业名称：不同搜索策略的算法实现与性能分析任课教师：王正友教学单位：信息科学与技术学院电子信息工程系布置日期：2012-11-16最后提交日期：2012-12-28说明 （1） 请务必在最后提交日期之前提交作业，除非有特殊情况（如病假等原因，须由辅导员签字），过期不交者本次作业判为不及格； （2） 作业格式参见具体模板；（2） 应个人独立完成作业，不得抄袭他人，一经发现，则本次作业以0分计。作业目的（1） 通过编程与实验，掌握典型搜索策略的概念、算法实现与性能分析。作业内容（1） 利用Jave/MATLAB/C(C+)等编程语言，设计和实现一款不同搜索策略的集成演示软件。（2） 该软件至少包含2种搜索算法，其中一种为盲目搜索、另一种为启发式搜索；（3） 软件基本功能满足：1）初始状态可以选择由软件随机产生，也可以通过人机交互产生。2）需要对搜索过程和路径提供解释。3）分析和研究存储结构、启发式函数等因素对搜索性能和效率的影响。（4） 界面友好。目录1开放实验目的42开放实验要求43开放实验内容44实验题目分析45软件总体设计56详细设计实现57程序调试及心得体会58作业自评59参考文献510附录5摘要 本实验项目主要针对不同搜索策略的算法实现和性能比较，主要运用了盲目搜索中的（BFS）宽度优先搜索算法和（DFS）深度优先搜索算法和启发式搜索算法中的A算法。本实验项目的内容是八数码问题，在此问题上运用上述各种算法，并实现各种算法性能的比较。实现的功能包括通过输入八数码问题的初始状态和最终状态，并选择所用的搜索算法来实现搜索，搜索的中间过程可以通过程序的编写在界面中一步步展现出来，还能输出相应的性能比较结果。 本项目主要运用了VC+语言进行程序设计，并利用MFC在Visual C+中进行可视化编程，通过可视化编程实现界面友好化，并选取不同的算法实现上述的要求，每种算法的实现有清楚的注释和说明。关键词： 搜索策略 八数码 MFC1开放实验目的通过编程与实验，掌握典型搜索策略的概念、算法实现与性能分析。2开放实验要求1）熟悉和掌握Jave/MATLAB/C(C+)等程序设计方法；2）至少包含2种搜索算法，其中一种为盲目搜索、另一种为启发式搜索；3）界面友好；4）代码结构清晰，注释易懂。3开放实验内容利用Jave/MATLAB/C(C+)等编程语言，设计和实现一款不同搜索策略的集成演示软件。以下几点是程序必须实现的功能。1）初始状态可以选择由软件随机产生，也可以通过人机交互产生。2）需要对搜索过程和路径提供解释。3）分析和研究存储结构、启发式函数等因素对搜索性能和效率的影响。4实验题目分析软件要求实现的是不同搜索策略的算法实现和性能比较，至少包括盲目搜索策略中的一种和启发式搜索策略中的一种。要实现该要求，就要选择一个项目，运用所选择的算法解决该项目，从而再实现不同算法的性能比较，所以本实验选择了八数码问题。本实验要求初始状态可以选择由软件随机产生，也可以通过人机交互产生，所以八数码问题要求可以输入初始状态；需要对搜索过程和路径提供解释，所以此实验给出了详细的搜索过程；还要求分析和研究存储结构、启发式函数等因素对搜索性能和效率的影响。要求选择一种编程语言，实现一款不同搜索策略的集成演示软件，此处采用c+语言，并用MFC实现可视化编程，根据需求设计界面，界面中包括初始状态输入的模块，最终状态的设定模块，有演示搜索过程中每一步骤的搜索过程的模块，有不同算法选择的模块，最后有不同算法性能比较的模块。5软件总体设计本软件是用于实现八数码问题的。 本软件中包含三种搜索策略，有宽度优先搜索策略、深度优先搜索策略和启发式搜索策略中的A算法。采用c+和MFC编程实现可视化界面，界面中包括5个模块，初始状态设定、目标状态设定、搜索过程的演示、算法的选择模块以及性能的展示。6详细设计实现（1）程序中使用到得算法本程序用到了三种搜索算法，分别是BFS（广度优先搜索）、DFS(深度优先搜索)和A算法。A BFS算法步骤：1 每次搜索之前清空OPEN 、CLOSED、PATH三表，并初始化初始状态Initstate；2 将初始节点放入OPEN表中；3 判断初始和目标状态Goalstate是否相同，如是则成功退出；4 将OPEN表中首端第一个节点取出放入CLOSED表中；5 如果OPEN表为空，则失败退出。否则用函数expandnodeBFS按Left，Right，Up，Down顺序扩展节点。给子节点的深度赋值，定义其父节点和子节点的指针；6 判断扩展后的子节点是否和目标节点相同，如是则成功退出，并用FindPath函数按照其父节点回溯到初始节点以寻找路径，并把所寻每一节点放入PATH表中；如果不相同，则把它放入OPEN表末端；7 转步骤4。 广度优先搜索算法程序流程示意图B DFS算法步骤：1 将初始节点S放入OPEN表中，若此节点为目标节点，则得解；2 若OPEN表为空，则失败退出；3 把OPEN表中首端第二个节点n移出，放入CLOSED表中； 4 若节点n的深度等于最大限制深度；则转向2；5 扩展节点n，产生其全部子节点，并将它们放入OPEN表首端，并给出返回n的指针，若节点不能扩展，则转向2；6 若后继子节点中有目标节点，则得解，成功退出。深度优先搜索算法程序流程示意图C Heuristic A算法步骤：1每次搜索之前清空OPEN 、CLOSED、PATH三表，并初始化初始状态Initstate；2将初始节点放入OPEN表中；3判断初始和目标状态Goalstate是否相同，如是则成功退出；4从OPEN表中找到估价值最小的节点（函数Evaluate）将其取出放入CLOSED表中。5如果OPEN表为空，则失败退出。否则用函数expandHeuristic按Left，Right，Up，Down顺序扩展节点。给子节点的深度赋值，定义其父节点和子节点的指针；6判断扩展后的子节点是否和目标节点相同，如是则成功退出，并用FindPath函数按照其父节点回溯到初始节点以寻找路径，并把所寻每一节点放入PATH表中；如果不是，则判断子节点是否已在CLOSED表和OPEN表中，如果都不在，则放入OPEN表末端；7转步骤4。启发式搜索算法程序流程示意图 （2）程序数据结构描述1 节点状态表示：定义结构体struct Eightpuzzleint depthcurrent;/节点深度int state9;/节点状态struct Eightpuzzle * father;/节点的父节点struct Eightpuzzle * child;/节点的子节点;2 OPEN表 CLOSED表：用MFC中CList类定义CPtrList Open;/OPEN表CPtrList Closed;/CLOSED表CPtrList Path;/用于最后存放路径PATH表（3）函数说明1. 估价函数int Evaluate(Eightpuzzle* current,Eightpuzzle* goal)返回一个int型数值，计算状态current中每个格子的号码与goal中相应号码之间的距离之和。取f(n)=d(n)+h(n),h(n)=P(n);2. enum direction LEFT, RIGHT, UP, DOWN,INVALID;direction MoveDirection(Eightpuzzle *father,Eightpuzzle *child,int &x);定义枚举类型direction，判断返回节点扩展时可以移动的方向。3. 主要函数一览：public:bool NumberCheck(int state9);/检查数据有效性bool Ishavepath(Eightpuzzle *initial, Eightpuzzle *goal);/检查时候有路径bool SearchHeuristic();/启发式搜索bool SearchBFS();/广度优先搜索 bool SearchDFS();/深度优先搜索int Evaluate(Eightpuzzle* current,Eightpuzzle* goal);/计算估价函数取P(n)Eightpuzzle Initstate;/初始节点Eightpuzzle Goalstate;/目标节点CPtrList Open;/OPEN表CPtrList Closed;/CLOSED表CPtrList Path;/用于最后存放路径PATH表int m_ndepth;Eightpuzzle *currentstep;private:enum direction LEFT, RIGHT, UP, DOWN,INVALID;void FindPath(Eightpuzzle *finalnode, Eightpuzzle *initnode);/按各节点父节点寻找路径direction MoveDirection(Eightpuzzle *father,Eightpuzzle *child,int &x);/判断可移动方向bool IsinClosed(Eightpuzzle *curnode);/判断当前扩展的节点是否已存在CLOSED表中bool IsinOpen(Eightpuzzle* curnode);/判断当前扩展的节点是否已存在OPEN表中bool Comparestate(Eightpuzzle * stateone,Eightpuzzle * stateanother);/比较两个节点状态时候相同void Copy8puzzle(Eightpuzzle *stateone, Eightpuzzle *stateanother);/复制节点状态bool MovetoDown(Eightpuzzle *fatherstate, Eightpuzzle *childstate);/向下移动bool MovetoUp(Eightpuzzle *fatherstate, Eightpuzzle *childstate);/向上移动bool MovetoRight(Eightpuzzle *fatherstate, Eightpuzzle *childstate);/向右移动bool MovetoLeft(Eightpuzzle *fatherstate, Eightpuzzle *childstate);/向左移动bool expandnodeBFS(Eightpuzzle *newnode,Eightpuzzle *nodeN,Eightpuzzle* pinit);/广度优先搜索中扩展节点 bool expandnodeDFS(Eightpuzzle *newnode,Eightpuzzle *nodeN,Eightpuzzle* pinit);/深度优先搜索中扩展节点bool expandnodeHeuristic(Eightpuzzle * newnode,Eightpuzzle* pstart);/启发式搜索中扩展节点（4）界面设计77程序调试及心得体会通过网上查找资料，找到了宽度优先搜索、深度优先搜索和启发式搜索的能够运行的程序代码，但是在把三种算法合为一个程序时，总是出现错误，由于自己对C+编程的不熟悉，总是改不成功，后来找了一个能够运行的带有界面的软件，但是对于MFC编程以前没有涉及过，所以通过网上查找资料，学习了mfc编程最初级的步骤，并能够运行自己所找到的软件，后又根据实验要求，在相应的代码中修改了所需的算法，以满足有盲目搜索算法和启发式搜索算法，并修改了性能比较，修改过程中，也是通过搜集的代码，把其整理，找到自己需要的部分，在照样子修改在自己的程序中。在该软件中，自己又对界面的尺寸，位置等做了相应的修改，以使其更加的友好化。在本软件中还有待学习的即是界面的显示的代码编写，以及各种控件的使用。通过本次试验，我对BFS、DFS以及启发式搜索有了更加深入的了解。在试验中，通过用不同的测试数据结果来看，宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少），只要结点间可以到达，就一定可以找到一个最优解。而深度优先搜索具有深度界限，当搜索深度达到深度界限时，停止搜索。所以，深度优先搜索有可能会得不到结果，是一种不安全的搜索方法。但是当结果在搜索界限内时，可以快速的得到结果，时间效率高。故对于深度优先搜索，如何去定义一个较好的搜索界限，是下一步需要继续改进的方面。相比之下，启发式搜索看来更加实用有效，能在较复杂情况下求得更加优质的解，但是对于估价函数的定义趋向多元化，如何更好地定义一个估价函数有待深入讨论。主观认识上，认识到了自己的编程能力很大程度的需要提高，所以在本次实验后，我会根据自己的能力自主去学习有关的编程。8作业自评自评指标: ABCDE算法实现: 盲目搜索A 启发式搜索 B 界面设计:主界面设计A 其它窗体界面设计 性能分析:存储结构 A 启发式函数 B 9参考文献 1刑建垒，用MFC动态编程实现8数码问题求解J.南京师范大学. 2郑阿奇，丁有和，Visual C+教程.北京：清华大学出版社.2003 3张仰森，黄改娟等，人工智能教程.高等教育出版社.2008.03 4吉跟林，数据结构教程.北京：电子工业出版社.2003 5胡敏杰.A*算法的探讨及其对八数码问题的实现J.漳州师范学院学报（自然科学版）.2005(03) 6欧阳林艳.八数码问题的探索算法比较J.洛阳师范学院学报.2011(08)10附录24程序代码/三种算法的实现 8puzzle.cpp: implementation of the C8puzzle class.bool C8puzzle:SearchBFS() Open.RemoveAll();Closed.RemoveAll();Path.RemoveAll();/每次搜索之前清空各链表Initstate.depthcurrent=0;/初始状态参数Initstate.child=NULL;Initstate.father=NULL;Eightpuzzle *newnode=new Eightpuzzle,*pinit;Copy8puzzle(&Initstate,newnode);pinit=newnode;if(Comparestate(&Initstate,&Goalstate) /判断初始和目标状态是否相同，如是则成功退出Path.AddTail(newnode);return true;Open.AddHead(newnode);/把初始节点放入OPEN表中Eightpuzzle* nodeN;while(1) if(Open.IsEmpty()/如OPEN表空，失败退出return false;nodeN = (Eightpuzzle *)Open.GetHead();Closed.AddTail(nodeN);/把OPEN表首端节点取出放入CLOSED表末端Open.RemoveHead();if(nodeN-depthcurrentdepthcurrent+Evaluate(pheadstate,&Goalstate)+1; for(int k=0;kdepthcurrent+Evaluate(popenstate,&Goalstate);if(nevaldepthcurrentstatex = fatherstate-statex-1;/交换数字0和0左方数字的位置childstate-statex-1 = 0;return true;bool C8puzzle:MovetoRight(Eightpuzzle *fatherstate, Eightpuzzle *childstate) int x=0;if(MoveDirection(fatherstate,childstate,x)=RIGHT)return false;childstate-statex = fatherstate-statex+1;/交换数字0和0右方数字的位置childstate-statex+1 = 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;/交换数字0和0正上方数字的位置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 C8puzzle:Copy8puzzle(Eightpuzzle *stateone, Eightpuzzle *stateanother) stateanother-depthcurrent=stateone-depthcurrent;stateanother-father=stateone-father;stateanother-child=stateone-child;for(int i=0;istatei=stateone-statei;bool C8puzzle:Comparestate(Eightpuzzle *stateone, Eightpuzzle *stateanother)for(int i=0;istatei!=stateanother-statei)return false;return true;int C8puzzle:Evaluate(Eightpuzzle *current, Eightpuzzle *goal)int xcur9,ycur9,xgoal9,ygoal9;/保存9个坐标int i,j;int value=0;for(i=0;i3;i+)for(j=0;jstate3*i+j=i;ycurcurrent-state3*i+j=j;xgoalgoal-state3*i+j=i;ygoalgoal-state3*i+j=j;for(i=1;i9;i+)value=value+abs(xcuri-xgoali)+abs(ycuri-ygoali); return value;bool C8puzzle:Ishavepath(Eightpuzzle *initial, Eightpuzzle *goal)int res1=0,res2=0;int i,j;int k=0,l=0;int cur18,cur28;for(i=0;istatei!=0)cur1k=initial-statei;k+;for(i=0;istatei!=0)cur2l=goal-statei;l+;for(i=0;i7;i+)for(j=i+1;jcur1j)res1+;for(i=0;i7;i+)for(j=i+1;jcur2j)res2+; res1=res1%2;res2=res2%2;if(res1=res2)return true;elsereturn false;bool C8puzzle:IsinOpen(Eightpuzzle *curnode)if(Open.IsEmpty() return false;for(int i=0;idepthcurrentdepthcurrent)Copy8puzzle(curnode,pcur);return false;bool C8puzzle:IsinClosed(Eightpuzzle *curnode)if(Closed.IsEmpty() return false;for(int i=0;ifather;Path.AddHead(initnode);bool C8puzzle:expandnodeHeuristic(Eightpuzzle *newnode,Eightpuzzle* pinit)if(!Comparestate(newnode, &Goalstate)if(NumberCheck(newnode-state)&(!IsinOpen(newnode) & (!IsinClosed(newnode)Open.AddTail(newnode); return false;else return false;elseFindPath(newnode, pinit);return true;C8puzzle:direction C8puzzle:MoveDirection(Eightpuzzle *father, Eightpuzzle *child,int& x) for(int i=0;istatei=0)x=i;for(int j=0;jstatej=father-statej;child-depthcurrent=father-depthcurrent+1;child-father=father;child-child=NULL;if (x=0)|(x=3)|(x=6) return LEFT;/can not move leftif (x=2)|(x=5)|(x=8) return RIGHT;/can not move right if (x=0)|(x=1)|(x=2) return UP;/can not move upif (x=6)|(x=7)|(x=8) return DOWN;/can not move downreturn INVALID;bool C8puzzle:NumberCheck(int state9) int cur9=0;for(int i=0;i9;i+) if(statei8)/限制数字范围08return false;curstatei+;for(int j=0;jstate)if( nodeN-father != NULL )if(!Comparestate(newnode, nodeN-father)Open.AddTail(newnode);elseOpen.AddTail(newnode);return false;elseFindPath(newnode, pinit);return true;bool C8puzzle:SearchDFS()Open.RemoveAll();Closed.RemoveAll();Path.RemoveAll();/每次搜索之前清空各链表Initstate.depthcurrent=0;/初始状态参数Initstate.child=NULL;Initstate.father=NULL;Eightpuzzle *newnode=new Eightpuzzle,*pinit;Copy8puzzle(&Initstate,newnode);pinit=newnode;if(Comparestate(&Initstate,&Goalstate) /判断初始和目标状态是否相同，如是则成功退出Path.AddTail(newnode);return true;Open.AddHead(newnode);/把初始节点放入OPEN表中Eightpuzzle* nodeN;while(1) if(Open.IsEmpty()/如OPEN表空，失败退出return false;nodeN = (Eightpuzzle *)Open.GetHead(); Closed.AddTail(nodeN);/把OPEN表首端节点取出放入CLOSED表末端Open.RemoveHead();if(nodeN-depthcurrentdepthcurrent=Maxdepth)/若节点n的深度等于最大限制深度，若OPEN表为空，则失败退出if(Open.IsEmpty()return false;bool C8puzzle:expandnodeDFS(Eightpuzzle *newnode, Eightpuzzle *nodeN, Eightpuzzle *pinit)if(!Comparestate(newnode, &Goalstate)/判断初始和目标状态Goalstate是否相同，如是则成功退出if(NumberCheck(newnode-state)if( nodeN-father != NULL )if(!Comparestate(newnode, nodeN-father)Open.AddHead(newnode);/扩展节点n，产生其全部子节点，并将它们放入OPEN表首端elseOpen.AddTail(newnode);return false;elseFindPath(newnode, pinit);return true;void CMy8puzzleDlg:OnButtonHeuristic() inputnumber();if(!(m_8puzzle.NumberCheck(m_8puzzle.Initstate.state)&m_8puzzle.NumberCheck(m_8puzzle.Goalstate.state)MessageBox(数据输入有误，请检查！);return;if(!(m_8puzzle.Ishavepath(&(m_8puzzle.Initstate),&(m_8puzzle.Goalstate)MessageBox(初始状态无法到达目标状态，n请重新输入!,Remind);return;time_t start=clock();if(m_8puzzle.SearchHeuristic()time_t end=clock();m_strstateremind.Format(成功啦，总共需要走 %d 步，扩展过 %d 个节点，用时 %d ms,m_8puzzle.Path.GetCount()-1,m_8puzzle.Closed.GetCount(),end-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:OnButtonBfs() inputnumber();if(!(m_8puzzle.NumberCheck(m_8puzzle.Initstate.state)&m_8puzzle.NumberCheck(m_8puzzle.Goalstate.state)MessageBox(数据输入有误，请检查！);return;if(!(m_8puzzle.Ishavepath(&(m_8puzzle.Init