人工智能第二次实验

《人工智能第二次实验》由会员分享，可在线阅读，更多相关《人工智能第二次实验（12页珍藏版）》请在装配图网上搜索。

1、 实验二 用广度优先搜索算法实现九宫图1 实验内容： 运用广度优先搜索的基本原理和方法实现对九宫图的查找，实现具体的编程要能显示正确的结果和图形。2 实验原理 基本思想： 从初节点S0开始，按层对接点进行扩展，并考察它是否为目标节点，在第N层的节点没有扩展之前，不对第N+1层的节点进行扩展。 Open表中节点总是按进入的顺序排列，也就是采用队列的结构。 基本过程： 1 把初节点S0放入OPEN表中2如果OPEN表为空，则问题无解，退出。3把OPEN表的第一个节点取出放入CLOSE表（记为N）4考察节点是否为目标节点，若是，问题解决，退出。5 若是该节点不能扩展，转向26 扩展节点N，将不包括祖

2、先节点的子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第二步。3 实验分析：用广度优先的算法实现九宫重排时要注意以下问题： 1 对于OPEN表应采用什么样的数据结构，由于为广度优先，需采用队列的结构。 2要用算法实现时，需要注意产生的节点不得与祖先节点相同，必须用相应的函数去实现匹配，不相同的才能放入OPEN表中。 3由于广度优先是完备的，故必有解。实验代码如下： 代码简单分析： 其中有两个头文件。 头文件# include list.h中主要实现的功能是把open表建造成队列的形式，并且实现对新节点的插入insertback(const string & valu

3、e)，为其分配父节点指针，以及将表中第一个节点移动到CLOSE表中removefront()。 头文件# include jgwt.h中实现九宫图放入左，中，右，下的移动函数，以及实现CLOSE表中的节点的扩展cjgwt:iskuozhan()；还有实现比较抛弃那些与祖先节点相同的节点函数cjgwt:isInsertOpen(string &str)/ 判断是否与祖先接点相同，不同则插入。还有对于目标的输出功能void cjgwt:print()。 主函数只要实现动态输入初始节点和目标节点，然后调用头文件里的各函数。# include list.h# include jgwt.h# inclu

4、de # include using namespace std;int main()string yuanstr,mustr;cout例如：283104765 回车 123804765 endl; cout 初始数据:yuanstr;cout 目标数据:mustr;cjgwt tr(mustr,yuanstr);tr.cpjg();return 0;# ifndef jgwt_h# define jgwt_h# include # include # include list.hclass cjgwtpublic:cjgwt(string &,string &);void cpjg();bo

5、ol operate();void iskuozhan();bool isEqualDads(string &);void swap(string &,int ,int);void isInsertOpen(string &);void print();void output(cnode *); int jds;private:string yuan;string mubiao;clist open;clist closed;cjgwt:cjgwt(string &str1,string &str2) :yuan(str1),mubiao(str2),jds(0) void cjgwt:cpj

6、g()int flag=0;open.insertfront(yuan);/ 在OPEN中放致初接点S0；flag=operate();cout扩展的节点数为： ;coutjds个endl;if(flag=1)print();else cout对不起，在1000步之内做不出GetData()=mubiao)/ 判断CLOSED表中的LASTPTR是否为目标接点flag=1;break;else /*if(iskuozhan()=0)/continue;elsezhankai();*/iskuozhan();/判断是否能展开，若能则展开，不能则做下一次循环i+;if(i=1000)break;/

7、coutiGetData();string str1,str2,str3,str4;str1=str2=str3=str4=temp;type=temp.find(0)+1;switch(type)case 1:/string str1=temp,str2=temp;swap(str1,0,1);isInsertOpen(str1);swap(str2,0,3); isInsertOpen(str2);break;case 2:/string str1=temp,str2=temp,str3=temp;swap(str1,1,0);isInsertOpen(str1);swap(str2,1,

8、2);isInsertOpen(str2);swap(str3,1,4);isInsertOpen(str3);break;case 3:swap(str1,2,1);isInsertOpen(str1);swap(str2,2,5);isInsertOpen(str2);break;case 4:swap(str1,3,0);isInsertOpen(str1);swap(str2,3,4);isInsertOpen(str2);swap(str3,3,6);isInsertOpen(str3);break;case 5:swap(str1,4,1);isInsertOpen(str1);s

9、wap(str2,4,3);isInsertOpen(str2);swap(str3,4,5);isInsertOpen(str3);swap(str4,4,7);isInsertOpen(str4);break;case 6:swap(str1,5,2);isInsertOpen(str1);swap(str2,5,4);isInsertOpen(str2);swap(str3,5,8);isInsertOpen(str3);break;case 7:swap(str1,6,3);isInsertOpen(str1);swap(str2,6,7);isInsertOpen(str2);bre

10、ak;case 8:swap(str1,7,4);isInsertOpen(str1);swap(str2,7,6);isInsertOpen(str2);swap(str3,7,8);isInsertOpen(str3);break;case 9:swap(str1,8,5);isInsertOpen(str1);swap(str2,8,7);isInsertOpen(str2);break;default:couttypesetDadptr(closed.lastptr);jds+;/open.lastptr-dadptr=closed.lastptr;/value=1;bool cjgw

11、t:isEqualDads(string &str)/是否与祖先接点相同函数/*cnode *currptr=closed.lastptr;string temp=currptr-GetData();while(currptr!=NULL & temp!=str)currptr=currptr-getDadptr();if(currptr=NULL)return 0;else return 1;*/cnode *currptr=closed.lastptr;string temp;while(currptr!=NULL)temp=currptr-GetData();if(temp!=str)c

12、urrptr=currptr-getDadptr();else break;if(currptr!=NULL)return 1;else return 0;void cjgwt:print()cnode *currptr=closed.lastptr;while(currptr!=NULL)output(currptr);currptr=currptr-getDadptr();void cjgwt:output(cnode *value)string temp=value-GetData();for(int i=0;i9;i+)if(tempi=0)cout ;if(i=8 | i=5 | i

13、=2)coutendl;elsecouttempi ; if(i=2 | i=5 |i=8)coutendl;cout*endl;# endif# ifndef clist_h# define clist_h# include # include node.h# include # include # include using namespace std;class clistfriend class cjgwt;public:clist();clist();void insertfront(const string &);void insertfront(cnode *);void ins

14、ertback(const string &);void insertback(cnode *);cnode *removefront();bool removeback(string &);string firstvalue() return firstptr-data;bool isempty() const;void print() const;private:cnode *firstptr;cnode *lastptr;cnode *getnew(const string &);clist:clist():firstptr(0),lastptr(0) ;clist:clist()if(

15、!isempty()/coutdestroying nodesnextptr;delete tempptr;void clist:insertfront(const string & value)cnode *newptr=getnew(value);if(isempty()firstptr=lastptr=newptr;elsenewptr-nextptr=firstptr;firstptr=newptr;void clist:insertfront(cnode * value)if(isempty()firstptr=lastptr=value;elsevalue-nextptr=firs

16、tptr;firstptr=value;void clist:insertback(const string & value)cnode *newptr=getnew(value);if(isempty()firstptr=lastptr=newptr;elselastptr-nextptr=newptr;lastptr=newptr;newptr-nextptr=NULL;void clist:insertback(cnode *value)if(isempty()firstptr=lastptr=value;elselastptr-nextptr=value;lastptr=value;v

17、alue-nextptr=NULL;cnode *clist:removefront()if(isempty()/return false;elsecnode *tempptr;/value=firstptr-data;tempptr=firstptr;firstptr=firstptr-nextptr;/delete tempptr;/return true;return tempptr;bool clist:removeback( string & value)if(isempty()return false;elsecnode *currentptr=firstptr,*tempptr=

18、lastptr;if(firstptr=lastptr)firstptr=lastptr=NULL;elsewhile(currentptr-nextptr!=lastptr)currentptr=currentptr-nextptr; lastptr=currentptr;currentptr-nextptr=NULL;value=tempptr-data;delete tempptr;return true;bool clist:isempty() constreturn firstptr=NULL;void clist:print() constcnode *currentptr=fir

19、stptr;while(currentptr!=NULL)coutdatanextptr;coutendl;cnode *clist:getnew(const string & value)cnode *ptrnew=new cnode(value);assert(ptrnew);return ptrnew;# endif# ifndef node_h# define node_h# include # include using namespace std;class cnodefriend class clist;public:cnode();cnode(const string &);v

20、oid setDadptr(cnode *value) dadptr=value;cnode *getDadptr() return dadptr; string GetData() const return data;private:string data;cnode *nextptr;cnode *dadptr;cnode:cnode() : nextptr(0),dadptr(0) cnode:cnode(const string &value) : data(value),nextptr(0),dadptr(0) # endif实验结果截屏：由结果知，从初始节点到目标节点共扩展了45个节点，且最短路径显示如上图。实验小结：通过本次实验，对于广度优先算法的原理理解更透彻，锻炼了自己的编程能力和实践能力，花费很多精力，也出现了很多错误，但是收获很大。人工智能第二次实验 电信学院计算机0510055115韩宁