人工智能实验报告完整版八数码+验证(共36页)

1、把数码问题(wnt)就是把一串数字变成下面这个样子:1 2 38 0 4 7 6 5实现(shxin)方法1.过程(guchng)表示源代码：#includestatic int style9=1,2,3,6,7,4,5,8,0;/输入的数码/2,5,4,3,0,7,1,8,6 3,2,1,8,0,4,7,6,5 1,0,4,2,7,3,8,5,6 1,0,3,8,2,4,7,6,5static int arrayStep416=5,4,3,6,7,8;/第四步和第六步共用的数组，所以设为全局量static int arrayStep714=3,6,7,4;static int local;/

2、空格的位置int i,j;/所用到的变量int number=0;/记录移动步数void print();void step1();void step2();void step3();void step4();void step5();void step6();void step7();void step8();void step9();void exchange(int x,int y);void judge();void judge()/判断空格位置number = 0;for(i=0;i9;i+)if(stylei=0)local=i;return;void exchange(int x

3、,int y)/交换(jiohun)两个数int temp;print();temp=stylex;stylex=styley;styley=temp;local=y;number+;void step1()int arrayStep115=3,0,1,2,5;int arrayStep126=6,7,8,5,2,1;if(style2!=0)&style2!=1)return;elseif(local=2)if(style1=1)exchange(2,5);elseexchange(2,1);return;elseif(local=4)exchange(4,1);i=2;while(loca

4、l!=5)exchange(arrayStep11i,arrayStep11i+1);i+;return;for(i=0;i3;i+)if(arrayStep11i=local)while(local!=5)exchange(arrayStep11i,arrayStep11i+1);i+;return;for(i=0;i4;i+)if(arrayStep12i=local)while(local!=1)exchange(arrayStep12i,arrayStep12i+1);i+;return;return;void step2()int arrayStep218=0,3,6,7,8,5,4

5、,1;for(i=0;i8;i+)if(arrayStep21i=local)while(style0!=1)exchange(arrayStep21i%8,arrayStep21(i+1)%8);i+;break;void step3()int arrayStep318=2,1,4,3,6,7,8,5;for(i=0;i8;i+)if(arrayStep31i=local)while(style1!=2)exchange(arrayStep31i%8,arrayStep31(i+1)%8);i+;break;void step4()for(i=0;i6;i+)if(arrayStep41i=

6、local)while(style4!=3)exchange(arrayStep41i%6,arrayStep41(i+1)%6);i=(i+1)%6;while(local!=3)exchange(arrayStep41i%6,arrayStep41(i+5)%6);i=(i+5)%6;break;void step5()int arrayStep519=3,0,1,4,5,2,1,0,3;i=0;doexchange(arrayStep51i,arrayStep51i+1);i+;while(local!=3);void step6()for(i=0;i6;i+)if(arrayStep4

7、1i=local)while(style5!=4)exchange(arrayStep41i%6,arrayStep41(i+1)%6);i+;if(local=8)exchange(8,7);break;return;void step7()for(i=0;i4;i+)if(arrayStep71i=local)while(style4!=5)exchange(arrayStep71i%4,arrayStep71(i+1)%4);i=(i+1)%4;while(local!=3)exchange(arrayStep71i%4,arrayStep71(i+3)%4);i=(i+3)%4;bre

8、ak;void step8()int arrayStep8113=3,0,1,2,5,4,7,8,5,2,1,0,3;i=0;doexchange(arrayStep81i,arrayStep81i+1);i+;while(local!=3);void step9()for(i=0;i4;i+)if(arrayStep71i=local)while(style7!=6)exchange(arrayStep71i%4,arrayStep71(i+1)%4);i=(i+1)%4;while(local!=4)exchange(arrayStep71i%4,arrayStep71(i+3)%4);i

9、=(i+3)%4;break;void print()for(j=0;j9;j+)if(stylej=0)printf( t);elseprintf(%dt,stylej);if(j+1)%3=0)printf(n);printf(* %d *n,number);void loop()printf(请输入(shr)数码：n);for(i=0;i9;i+)scanf(%d,&stylei);judge();step1();step2();step3();if(style2!=3)step4();step5();step6();if(style8!=5)step7();step8();step9(

10、);print();if(!(style3=8)&(style6=7)printf(用书上所给算法(sun f)来看此数码错误！n);void main()while(1)loop();深度优先(yuxin)实现/*说明(shumng)* 用宽度优先搜索算法实现八数码问题 */#include#include#include#include #include string.h #include assert.h #include windows.h using namespace std;int wholeStyle9 = 2,8,3,1,6,4,7,0,5;int standard19 =

11、1,2,3,8,0,4,7,6,5;int local,i,j;int startKey = 0,endKey = 0,equalKey = 1,tempSpace;struct node *openHead,*open; /open表struct node *closedHead,*closed; /closed表struct node *tempNode; /临时(ln sh)节点struct node *answer; /找到的路径(ljng)int num = 0;struct nodeint style9;struct node *next;struct node *father;v

12、oid updateData() /更新(gngxn)要判断数据int i;printf(请输入八数码原始状态：n);for(i = 0;i 9;i+)scanf(%d,&wholeStylei);printf(请输入八数码最终状态：n);for(i = 0;i 9;i+)scanf(%d,&standard1i);void judge1(struct node *head)/判断空格位置for(i = 0;i stylei = 0)local = i;return;int judge2(struct node *head) /判断是否与标准八数码相等，不相等返回值为0for(i = 0;i

13、stylei != standard1i)if(i = 3)&(head-style3 = standard16);else if(i = 6)&(head-style6 = standard13);else return 0;return 1;void judge3() /判断新生成的八数码是否就是最终状态(zhungti)或者在open、closed表中出现if(judge2(tempNode)endKey = 1;elsewhile(openHead-next-next-style0 != 9)for(i = 0;i next-next-stylei != tempNode-stylei

14、)equalKey = 1;break;elseequalKey = 0;if(equalKey)/不相等(xingdng)openHead = openHead-next;elsebreak;openHead = open-next;if(equalKey)/不相等(xingdng)while(closedHead-next-style0 != 9)for(i = 0;i next-stylei != tempNode-stylei)equalKey = 1;break;elseequalKey = 0;if(!equalKey)/相等(xingdng)break;elseclosedHea

15、d = closedHead-next;closedHead = closed-next;if(equalKey)/不相等(xingdng)open-next = tempNode;tempNode-next = openHead;tempNode-father = openHead-next;open = open-next;void print(struct node *temp) /输出(shch)八数码表for(j = 0;j stylej = 0)printf( t);elseprintf(%dt,temp-stylej);if(j + 1) % 3 = 0)printf(n);vo

16、id write2txt()ofstream out(F:out_details.txt,ios:app);if( out.fail() )cerr未找到文件endl;out 第+num步n;outnext-style0 != 9)for(i = 0;i 9;i +)outnext-styleit;if(i+1) % 3 = 0)outn;outnext;openHead = openHead-next;out*n;outnext-style0 != 9)for(i = 0;i 9;i +)outnext-styleit;if(i + 1) % 3 =0)outn;outnext;closed

17、Head = closedHead-next;out-n;out.close();void main()/updateData();/输入(shr)八数码数据for(i = 0;i style0 = 9;openHead-next = open;for(i = 0;i stylei = wholeStylei;open-next = openHead;open-father = openHead;closedHead = new node();closed = new node();closedHead-style0 = 9;closedHead-next = closedHead;close

18、d = closedHead;while(open-style0 != 9)/当open表不为空时一直(yzh)循环judge1(openHead-next);if(local % 3 0)/右移equalKey = 1;tempNode = new node();for(i = 0;i stylei = openHead-next-stylei;tempSpace = tempNode-stylelocal - 1;tempNode-stylelocal - 1 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if

19、(endKey)break;if(local 2)/下移equalKey = 1;tempNode = new node();for(i = 0;i stylei = openHead-next-stylei;tempSpace = tempNode-stylelocal - 3;tempNode-stylelocal - 3 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;if(local % 3 2)/左移equalKey = 1;tempNode = new node();for

20、(i = 0;i stylei = openHead-next-stylei;tempSpace = tempNode-stylelocal + 1;tempNode-stylelocal + 1 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;if(local 6)/上移equalKey = 1;tempNode = new node();/tempNode = malloc(sizeof(struct node);for(i = 0;i stylei = openHead-next

21、-stylei;tempSpace = tempNode-stylelocal + 3;tempNode-stylelocal + 3 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;closed-next = openHead-next;/把open的标头添加(tin ji)到closed表中openHead-next = openHead-next-next; closed = closed-next;closed-next = closedHead;write2txt();ope

22、n-next = tempNode;/把找到的新节点(ji din)添加到open表中tempNode-next = openHead;tempNode-father = openHead-next;open = open-next;closed-next = openHead-next;/把open的标头添加(tin ji)到closed表中openHead-next = openHead-next-next; closed = closed-next;closed-next = closedHead;write2txt();answer = new node();tempNode = ne

23、w node();tempNode = open;while(tempNode-style0 != 9)/将结果路径存于answeranswer = tempNode;tempNode = tempNode-father;tempNode-next = answer;num = 0;while(answer-next-style0 != 9)/输出answerprintf(*第%d步*n,num+);print(answer);answer = answer-next;printf(n);printf(*第%d步*n,num+);print(answer);if(answer-style3 !

24、= standard13)printf(n!输入的八数码不合法，不能从初始状态到最终状态nnnn);return;宽度(kund)优先：/*说明(shumng)* 用宽度(kund)优先搜索算法实现八数码问题 */#include#include#include#include #include string.h #include assert.h #include windows.h using namespace std;int wholeStyle9 = 2,8,3,1,6,4,7,0,5;int standard19 = 1,2,3,8,0,4,7,6,5;int local,i,j;

25、int startKey = 0,endKey = 0,equalKey = 1,tempSpace;struct node *openHead,*open; /open表struct node *closedHead,*closed; /closed表struct node *tempNode; /临时节点struct node *answer; /找到的路径int num = 0;struct nodeint style9;struct node *next;struct node *father;void updateData() /更新要判断数据int i;printf(请输入八数码原

26、始状态：n);for(i = 0;i 9;i+)scanf(%d,&wholeStylei);printf(请输入八数码最终状态：n);for(i = 0;i 9;i+)scanf(%d,&standard1i);void judge1(struct node *head)/判断(pndun)空格位置for(i = 0;i stylei = 0)local = i;return;int judge2(struct node *head) /判断是否与标准(biozhn)八数码相等，不相等返回值为0for(i = 0;i stylei != standard1i)if(i = 3)&(head-

27、style3 = standard16);else if(i = 6)&(head-style6 = standard13);else return 0;return 1;void judge3() /判断新生成的八数码是否(sh fu)就是最终状态或者在open、closed表中出现if(judge2(tempNode)endKey = 1;elsewhile(openHead-next-next-style0 != 9)for(i = 0;i next-next-stylei != tempNode-stylei)equalKey = 1;break;elseequalKey = 0;if

28、(equalKey)/不相等(xingdng)openHead = openHead-next;elsebreak;openHead = open-next;if(equalKey)/不相等(xingdng)while(closedHead-next-style0 != 9)for(i = 0;i next-stylei != tempNode-stylei)equalKey = 1;break;elseequalKey = 0;if(!equalKey)/相等(xingdng)break;elseclosedHead = closedHead-next;closedHead = closed

29、-next;if(equalKey)/不相等open-next = tempNode;tempNode-next = openHead;tempNode-father = openHead-next;open = open-next;void print(struct node *temp) /输出八数码表for(j = 0;j stylej = 0)printf( t);elseprintf(%dt,temp-stylej);if(j + 1) % 3 = 0)printf(n);void write2txt()ofstream out(F:out_details.txt,ios:app);

30、if( out.fail() )cerr未找到文件(wnjin)endl;out 第+num步n;outnext-style0 != 9)for(i = 0;i 9;i +)outnext-styleit;if(i+1) % 3 = 0)outn;outnext;openHead = openHead-next;out*n;outnext-style0 != 9)for(i = 0;i 9;i +)outnext-styleit;if(i + 1) % 3 =0)outn;outnext;closedHead = closedHead-next;out-n;out.close();void m

31、ain()/updateData();/输入八数码(shm)数据for(i = 0;i style0 = 9;openHead-next = open;for(i = 0;i stylei = wholeStylei;open-next = openHead;open-father = openHead;closedHead = new node();closed = new node();closedHead-style0 = 9;closedHead-next = closedHead;closed = closedHead;while(open-style0 != 9)/当open表不为

32、空时一直(yzh)循环judge1(openHead-next);if(local % 3 0)/右移(yu y)equalKey = 1;tempNode = new node();for(i = 0;i stylei = openHead-next-stylei;tempSpace = tempNode-stylelocal - 1;tempNode-stylelocal - 1 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;if(local 2)/下移equalKey = 1;

33、tempNode = new node();for(i = 0;i stylei = openHead-next-stylei;tempSpace = tempNode-stylelocal - 3;tempNode-stylelocal - 3 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;if(local % 3 2)/左移equalKey = 1;tempNode = new node();for(i = 0;i stylei = openHead-next-stylei;te

34、mpSpace = tempNode-stylelocal + 1;tempNode-stylelocal + 1 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;if(local 6)/上移equalKey = 1;tempNode = new node();/tempNode = malloc(sizeof(struct node);for(i = 0;i stylei = openHead-next-stylei;tempSpace = tempNode-stylelocal +

35、 3;tempNode-stylelocal + 3 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;judge3();if(endKey)break;closed-next = openHead-next;/把open的标头添加(tin ji)到closed表中openHead-next = openHead-next-next; closed = closed-next;closed-next = closedHead;write2txt();open-next = tempNode;/把找到的新节点(ji din)添加到open

36、表中tempNode-next = openHead;tempNode-father = openHead-next;open = open-next;closed-next = openHead-next;/把open的标头添加(tin ji)到closed表中openHead-next = openHead-next-next; closed = closed-next;closed-next = closedHead;write2txt();answer = new node();tempNode = new node();tempNode = open;while(tempNode-s

37、tyle0 != 9)/将结果(ji gu)路径存于answeranswer = tempNode;tempNode = tempNode-father;tempNode-next = answer;num = 0;while(answer-next-style0 != 9)/输出(shch)answerprintf(*第%d步*n,num+);print(answer);answer = answer-next;printf(n);printf(*第%d步*n,num+);print(answer);if(answer-style3 != standard13)printf(n!输入的八数码

38、(shm)不合法，不能从初始状态到最终状态nnnn);return;A算法/*说明* * A算法实现八数码问题 * */#include#include#includeusing namespace std;void print(struct node *temp);int wholeStyle9 = 2,8,3,1,6,4,7,0,5;int standard19 = 1,2,3,8,0,4,7,6,5;int local,i,j;int tempSpace;struct node *openHead,*open; /open表struct node *closedHead,*closed;

39、 /closed表struct node *tempNode; /临时节点struct node *answer; /找到的路径(ljng)int num = 0;bool endKey;struct nodeint depth;int judgement_based;int style9;struct node *next;struct node *father;void updateData() /更新(gngxn)要判断数据int i;cout请输入(shr)八数码原始状态：endl;for(i = 0;i wholeStylei;cout请输入八数码最终状态：endl;for(i =

40、0;i standard1i;int judge1(struct node *head)/判断空格位置for(i = 0;i stylei = 0)return i;int evaluation_function(struct node *head) /计算不在正确位置的点的个数int not_correct_position = 0;for(i = 0;i stylei != 0)&(head-stylei != standard1i)not_correct_position+;return not_correct_position;void print(struct node *temp)

41、 /输出八数码表for(j = 0;j stylej = 0)cout t;elsecoutstylejt;if(j + 1) % 3 = 0)coutendl;void write2txt() /将过程(guchng)记录到文本文档中ofstream out(F:out_details4.txt,ios:app);if( out.fail() )cerr未找到文件(wnjin)endl;out 第+num步n;outnext-style0 != 9)for(i = 0;i 9;i +)outnext-styleit;if(i+1) % 3 = 0)outn;out估值：;outnext-ju

42、dgement_basednext;openHead = openHead-next;out*n;outnext-style0 != 9)for(i = 0;i 9;i +)outnext-styleit;if(i + 1) % 3 =0)outn;out深度(shnd)：next-depth 估值：next-judgement_basednext;closedHead = closedHead-next;outfather)/当新生成节点的空格位置与closed父亲(f qn)节点的空格位置不相等tempNode-father = closed; /新生成节点(ji din)的指向它的父亲节

43、点tempNode-depth = closed-depth + 1;/深度加1tempNode-judgement_based = evaluation_function(tempNode) + tempNode-depth;/计算估值while(openHead-next-style0 != 9)if(tempNode-judgement_based openHead-next-judgement_based)openHead = openHead-next;elsetempNode-next = openHead-next;openHead-next = tempNode;openHea

44、d = open-next;return;/插入的值比最后一个还大 进行下面的操作openHead = open-next;/先恢复表头 否则Head指向为最后一个open-next = tempNode;tempNode-next = openHead;open = open-next;return;void main()/updateData();/输入八数码数据openHead = new node(); /初始化open表open = new node();openHead-style0 = 9;openHead-next = open;for(i = 0;i stylei = who

45、leStylei;open-next = openHead;open-father = openHead;open-depth = 0;open-judgement_based = evaluation_function(open) + open-depth;/这行可以(ky)不写closedHead = new node(); /初始化closed表closed = new node();closedHead-style0 = 9;closedHead-next = closedHead;closed = closedHead;int min_judgement1 = open-judgem

46、ent_based;while(open-style0 != 9)/当open表不为空时一直(yzh)循环/updateData();/输入八数码(shm)数据write2txt();closed-next = openHead-next; /把open表中第一组八数码移到closed表中openHead-next = openHead-next-next;closed = closed-next;closed-next = closedHead;if(openHead-next-style0 = 9)/如果是第一次 则open暂时指向openHeadopen = openHead;if(cl

47、osed-judgement_based = closed-depth)/判断新移进closed表中的八数码的f值是否等于它的层数coutsucceed!style0 != 9) /将结果存于answer表中answer = closed;closed = closed-father;closed-next = answer;num = 0;while(answer-style0 != 9) /控制台显示步骤cout*第num+步*n;print(answer);coutnext;return;else /如果closed表末的八数码是最终(zu zhn)状态 则拓展新的八数码local =

48、judge1(closed);if(local % 3 0)/右移(yu y)tempNode = new node();for(i = 0;i stylei = closed-stylei;tempSpace = tempNode-stylelocal - 1;tempNode-stylelocal - 1 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;basic_exchange_oper();if(local 6)/上移tempNode = new node();for(i = 0;i stylei = closed-stylei;tempSpace = tempNode-stylelocal + 3;tempNode-stylelocal + 3 = tempNode-stylelocal;tempNode-stylelocal = tempSpace;basic_exchange_oper();if(local 2)/下移tempNode = new node();for(i = 0;i style