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