《人工智能》实验报告

1、人工智能实验报告学生班级 网络工程 学生姓名 学号 8 实验时间 2012-09-17 实验地点 C5-713 实验名称 八数码问题 实验成绩 1、 实验目的实现八数码问题：在3X3九宫格棋盘上摆有8个将牌，每一个将牌都可有1-8数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称为初始状态）和一个目标布局（称为目标状态），问如何移动将牌实现从初始状态到目的状态的转变，问题的解答就是给出一个合法的走步序列。设评价函数f(n) = d(n)+W(n),其中d(n)表示结点的深度，

2、W(n)表示不在位的将牌数，f(n）可估计出通向目标结点的希望程度。2、 实验过程八数码问题的关键在于求出每个状态估计函数的大小并刷新open表将open表按评价函数值的大小从小到大进行排序。由于要避免结点在之前是否被搜索过，所以要对链表进行for循环判断。每一次刷新open表时都需要将最小的元素置顶，相同的元素较前出现的置前，每个节点都有一个指向父节点的指针一遍最后得出最终路径。数据结构：struct Nodeint array33;int quanzhi;Node *parent;Node *next;int level;下面是设置的各函数：/复制数组void copyArray(int

3、c33,int d33)/初始化结点void InitNode(node &l)/确认插入的位置int Locate(node a,Node b)/插入结点int InsertNode(node a,int i,Node b)/删除结点int DeleteNode(node a,int i)/判断两数组是否相同，相同返回truebool isSame(int c33,int d33)/在链表中查找结点，找到返回truebool isfind(node a,Node b)/在链表中查找结点，若找到返回该节点的深度int find(AndGetLevelnode a,Node b)/在链表中查找结

4、点并返回该节点在链表中的位置。int findAndGetIndex(node a,Node b)/计算不在位的将牌数int computeF(int c33,int d33)/输出该节点的数组void print(int w3,int i,int j)/根据父节点返回路径并输出路径void shuchu(node a)3、 实验结果开始结点：目标结点：初始结点：目标结点：初始结点目标结点四、讨论与分析实现过程由以下伪代码： 读入初始状态和目标状态，并计算初始状态评价函数值f；把初始状态假如open表中；While（未找到解&状态表非空）在open表中找到评价值最小的节点，作为当前结点；判断当

5、前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；把当前结点从open表中移除；End while五、实验总结与思考本次实验主要是考察对 A*算法的了解，通过这次作业我更加了解了图搜索的方法并且在脑海里形成了一定的思维方法，做题目时有了一定的步骤和想法，但是作业过程中由于对链表指针操作的不熟悉导致了很多错误，指向父节点的parent指针总会在经过一系列操作后消失不见，导致最后午饭从目标结点沿路返回，不过

6、经过一系列调试后最终解决。六、附录：关键代码#include#include#includeusing namespace std;struct Nodeint array33;int quanzhi;/不在位的将牌数Node *parent;Node *next;/在open表中指向下一个元素int level;typedef Node * node;/复制数组void copyArray(int c33,int d33)for(int i1=0;i1=2;i1+) for(int j1=0;j1parent=NULL;l-next=NULL;/确认插入的位置int Locate(node

7、a,Node b)/a为open表的首头结点 int i=0; node p=a-next; while(p) i+; if(p-quanzhi+p-level)(b.quanzhi+b.level)/判断双方估计函数值大小 return i; if(p-quanzhi+p-level)=(b.quanzhi+b.level) int j=i+1; return j; p=p-next; return (i+1);/插入结点int InsertNode(node a,int i,Node b)int j=0;node s,p=a;while(p&jnext; s=(node)malloc(si

8、zeof(Node);copyArray(s-array,b.array); /复制数组s-level=b.level;s-parent=b.parent;s-quanzhi=b.quanzhi;s-next=p-next;p-next=s;return 1;/删除结点int DeleteNode(node a,int i)int j=0;node q,p=a;while(p&jnext; if(!p-next|ji-1) return 0;q=p-next;p-next=q-next;return 1;/判断两数组是否相同，相同返回truebool isSame(int c33,int d3

9、3)for(int i1=0;i1=2;i1+) for(int j1=0;j1next; while(p) if(compare1(p-array,b.array)=1) return true; p=p-next; return false;/在链表中查找结点并返回该节点的深度int find(AndGetLevelnode a,Node b) int i=0; node p=a-next; while(p) i+; if(compare1(p-array,b.array)=1) return p-level; p=p-next; return 1000;/在链表中查找结点并返回该节点在链

10、表中的位置。int findAndGetIndex(node a,Node b) int i=0; node p=a-next; while(p) i+; if(compare1(p-array,b.array)=1) return i; p=p-next; /计算估计函数int computeF(int c33,int d33) int count=0;for(int i = 0; i3; i+) for (int j = 0;j3; j+) for (int k = 0; k3; k+) for (int l = 0; l3; l+) if (cij = dkl&cij!=0) count

11、 +=abs(i - k)+abs(j - l);return count;/输出该节点的数组void print(int w3,int i,int j)for(int i0=0;i0=i;i0+)coutendl;for(int j0=0;j0=j;j0+)coutnext; int u=0; while(b) u=u+1; copyArray(solutionlistu.array,b-array); b=b-parent; for(int i=u;i=1;i-) print(solutionlisti.array,2,2);coutendl; coutendl;int main() in

12、t a33;int i;int j;int i0;int j0;int top=1;/输入数据coutinput the data:endl;for(i=0;i=2;i+)for(j=0;jaij; coutnext-array,goalNode)!=1)/当前结点与目标结点不一致时进行while循环node aa=l-next;Node bb=*aa;InsertNode(r,h,bb);h+;int m,m0;copyArray(d,aa-array);copyArray(arr1,aa-array);copyArray(arr2,aa-array);copyArray(arr3,aa-a

13、rray);copyArray(arr4,aa-array);/找出当前点的空格位置 for(i=0;i=2;i+) for(j=0;j=0)/向左移动 arr1i0j0=arr1i0-1j0; arr1i0-1j0=0; Node node; copyArray(node.array,arr1); node.parent=aa; node.level=(aa-level)+1; node.quanzhi=computeF(node.array,goalNode); node.next=NULL; if(!isfind(l,node) if(!isfind(r,node) m=Locate(l

14、,node); InsertNode(l,m,node); else int y=findAndGetLevel(r,node); if(node.levely) m0=Locate(l,node); InsertNode(l,m0,node); else int x=findAndGetLevel(l,node); if(x=0)/向上?移?动 arr2i0j0=arr2i0j0-1; arr2i0j0-1=0; Node zuo1; copyArray(zuo1.array,arr2); zuo1.parent=aa; zuo1.level=aa-level+1; zuo1.quanzhi

15、=computeF(arr2,goalNode); if(!isfind(l,zuo1) if(!isfind(r,zuo1) m=Locate(l,zuo1); InsertNode(l,m,zuo1); else int y=findAndGetLevel(r,zuo1); if(zuo1.levely) m0=Locate(l,zuo1); InsertNode(l,m0,zuo1); else int x=findAndGetLevel(l,zuo1); if(x=zuo1.level) else int k=findAndGetIndex(l,zuo1); DeleteNode(l,

16、k); m=Locate(l,zuo1); InsertNode(l,m,zuo1); if(i0+1level+1; xia1.quanzhi=computeF(arr3,goalNode); if(!isfind(l,xia1) if(!isfind(r,xia1) m=Locate(l,xia1); InsertNode(l,m,xia1); else int y=findAndGetLevel(r,xia1); if(xia1.levely) m0=Locate(l,xia1); InsertNode(l,m0,xia1); else int x=findAndGetLevel(l,xia1); if(x=xia1.level) else int k=findAndGetIndex(l,xia1); DeleteNode(l,k); m=Locate(l,xia1); InsertNode(l,m,xia1); if(j0+1level+1; you1.quanzhi=computeF(arr4,goalNode); if(!isfind(l,you1) if(isfind(r,you1) m=Locate(l,you1); InsertNode(l,m,you1); else int