人工智能实验报告完整版八数码验证解读

1、把数码问题就是把一串数字变成下面这个样子187实现方法1.过程表示源代码：#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,5 static int arrayStep416=5,4,3,6,7,8;/ 第四步和第六步共用的数组，所以设为全局量 static int arrayStep714=3,6,7,4;static int local;/ 空格的位置int i,j;/ 所用到的变量int numb

2、er=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,int y)/ 交换两个数int temp;

3、 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;else if(local=2) if(style1=1) exchange(2,5); else exchange(2,1); return;elseif(local=4) exchange(4,1); i=2;while(local!=5) exchang

4、e(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,1; for

5、(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=loca

6、l)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(arrayStep41

7、i=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)

8、%4;break;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

9、+3)%4);i=(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( 请输入数码： n);for(i=0;i9;i+)scanf(%d,&stylei);judge();step1();step2();step3();if(style2!=3)step4();step5();step6();if(style8!=5)step7();step8(

10、);step9();print();if(!(style3=8)&(style6=7)printf( 用书上所给算法来看此数码错误！ n);void main()while(1) loop();2.深度优先实现/* 说明 * 用宽度优先搜索算法实现八数码问题 */#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,

11、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; /临时节点struct node *answer; / 找到的路径 int num = 0;struct nodeint style9;struct node *next; struct node *father;void updateDa

12、ta() /更新要判断数据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) / 判断是否与标准八数码相等，不相等返回值为for(i = 0;i stylei !=

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

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

15、 closed-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);else printf(%dt,temp-stylej);if(j + 1) % 3 = 0) printf(n);void write2txt()ofstream out(F:out_detail

16、s.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;closedHead = closedHead-next; ou

17、tn;out.close();void main()/updateData();/ 输入八数码数据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(o

18、pen-style0 != 9)/ 当 open 表不为空时一直循环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(endKey)break;if(loc

19、al 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(i = 0;i stylei

20、= 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-stylei; te

21、mpSpace = tempNode-stylelocal + 3; tempNode-stylelocal + 3 = tempNode-stylelocal; tempNode-stylelocal = tempSpace;judge3(); if(endKey) break;closed-next = openHead-next; /把 open 的标头添加至U closed 表中 openHead-next = openHead-next-next;closed = closed-next;closed-next = closedHead;write2txt();open-next =

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

23、Node = 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);nnnn);if(answer-style3

24、!= standard13) printf(n! 输入的八数码不合法，不能从初始状态到最终状态 return;3.宽度优先：/* 说明 * 用宽度优先搜索算法实现八数码问题 */#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;int startKey = 0,e

25、ndKey = 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( 请输入八数码原始状态： n);

26、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;0return;int judge2(struct node *head) / 判断是否与标准八数码相等，不相等返回值为for(i = 0;i stylei != standard1i)if(i = 3)&(head-style3 = standar

27、d16) else if(i = 6)&(head-style6 = standard13) elsereturn 0;return 1;open、 closed 表中出现void judge3() / 判断新生成的八数码是否就是最终状态或者在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(equalKey)/ 不相等openH

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

29、ode; tempNode-next = openHead; tempNode-father = openHead-next; open = open-next;void print(struct node *temp) / 输出八数码表for(j = 0;j stylej = 0) printf( t);else printf(%dt,temp-stylej);if(j + 1) % 3 = 0) printf(n);void write2txt()ofstream out(F:out_details.txt,ios:app); if( out.fail() )cerr 未找到文件 endl

30、;第 +num 步 n; outnext-style0 != 9) outfor(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; outn;out.close();void main()/updateData();/ 输

31、入八数码数据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 表不为空时一直循环judge1(ope

32、nHead-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(endKey)break;if(local 2)/ 下移equalKey = 1;tempNode = new node

33、();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; tempSpace = temp

34、Node-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 + 3; tem

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

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

37、 将结果路径存于 answeranswer = tempNode;tempNode = tempNode-father; tempNode-next = answer;num = 0;第%d 步*n,num+);while(answer-next-style0 != 9)/ 输出 answerprintf(*print(answer);answer = answer-next; printf(n);printf(*第 %d 步*n,num+);print(answer);if(answer-style3 != standard13)printf(n! 输入的八数码不合法，不能从初始状态到最终状

38、态 nnnn); return;4.A 算法*/* 说明 * * A 算法实现八数码问题*/ #include#include #include using 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; /close

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

40、;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;else coutstylejt;if(j + 1) % 3 = 0) coutendl;void write2txt() / 将过程记录到文本文档中ofstream out(F:out_details4.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;out估值：”；outnext-judgement_

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

43、h = closed-depth + 1;/ 深度加 1 tempNode-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; openHead = open-next;return;/插入的值比最后一个还大 进行下面的操作openHead = open-next;/ 先恢复表头 否则 Head 指向为最后一个 open-next =