《人工智能第二次实验》由会员分享，可在线阅读，更多相关《人工智能第二次实验（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)currptr=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();
