《华工人工智能平时作业所有实验代码》由会员分享，可在线阅读，更多相关《华工人工智能平时作业所有实验代码（14页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 14 页过河问题#includeusing namespace std;bool backtrack(int church,int wild,bool boat,int rulei,int rulej,int loopNum)if(church = 0 & wild = 0 & boat = false)cout= 25)return false;if( (church != 0 & church 0 & i 0 & i #include#includeint startState33=2,8,3,1,6,4,7,0,5;int endState33=1,2,3,8,0,4,7
2、,6,5;int openNode=0; struct Nodeint s33;int f;int g;struct Node *nextNode;第 3 页 共 14 页struct Node *previousNode;/添加节点函数入口，方法：通过插入排序向指定表添加void addNodeFunction( struct Node *head, struct Node *p)struct Node*q;if(head-nextNode) q = head-nextNode;if(p-f nextNode-f)p-nextNode = head-nextNode; head-nextNo
3、de = p; else while(q-nextNode)if(q-f f |q-f = p-f) & (q-nextNode-f p-f | q-nextNode-f = p-f)p-nextNode = q-nextNode;q-nextNode = p;break;q = q-nextNode;if(q-nextNode = NULL) q-nextNode = p;else head-nextNode = p;/删除节点函数入口void deleteNodeFunction(struct Node * head, struct Node *p )struct Node *q;q =
4、head;while(q-nextNode)第 4 页 共 14 页if(q-nextNode = p)q-nextNode = p-nextNode;p-nextNode = NULL;if(q-nextNode = NULL) return;q = q-nextNode;/判断两个数组是否相等函数入口int arrayEqual(int s133, int s233)int i,j,flag=0;for(i=0; inextNode;int flag = 0;while(q)if(arrayEqual(q-s,s) flag=1; Old_Node-nextNode = q; return
5、 1;第 5 页 共 14 页else q = q-nextNode;if(!flag) return 0;/计算 p(n)放错位的数码与其正确的位置之间距离之和的函数入口int wrongNumber(int s33)int i,j,fi,fj,sum=0;for(i=0 ; isij = BESTNODE-sij;for(i=0; isij = 0)i_0 = i; j_0 = j;break;第 6 页 共 14 页switch(direction)case 0:if(i_0-1)-1 )temp = Successor-si_0j_0;Successor-si_0j_0 = Succe
6、ssor-si_0-1j_0;Successor-si_0-1j_0 = temp;return 1;else return 0;case 1: if(j_0-1)-1)temp = Successor-si_0j_0;Successor-si_0j_0 = Successor-si_0j_0-1;Successor-si_0j_0-1 = temp;return 1;else return 0;case 2: if( (j_0+1)si_0j_0;Successor-si_0j_0 = Successor-si_0j_0+1;Successor-si_0j_0+1 = temp;return
7、 1;else return 0;case 3: if(i_0+1)si_0j_0;Successor-si_0j_0 = Successor-si_0+1j_0;Successor-si_0+1j_0 = temp;return 1;else return 0;第 7 页 共 14 页/处理后继结点void dealLaterNodes(struct Node * Open, struct Node * BESTNODE,struct Node * Closed,struct Node *Successor)struct Node * Old_Node = (struct Node *)ma
8、lloc(sizeof(struct Node);Successor-previousNode = BESTNODE;Successor-g = BESTNODE-g + 1;if( judgeNodeFunction(Open, Successor-s, Old_Node) )if(Successor-g g)Old_Node-nextNode-previousNode = BESTNODE;Old_Node-nextNode-g = Successor-g;Old_Node-nextNode-f = Old_Node-g + wrongNumber(Old_Node-s);deleteNo
9、deFunction(Open, Old_Node);addNodeFunction(Open, Old_Node);else if( judgeNodeFunction(Closed, Successor-s, Old_Node)if(Successor-g g)Old_Node-nextNode-previousNode = BESTNODE;Old_Node-nextNode-g = Successor-g;Old_Node-nextNode-f = Old_Node-g + wrongNumber(Old_Node-s);deleteNodeFunction(Closed, Old_N
10、ode);addNodeFunction(Closed, Old_Node); else Successor-f = Successor-g + wrongNumber(Successor-s); addNodeFunction(Open, Successor); openNode+;/从 OPen 表获取最佳节点函数入口struct Node * getBestNode(struct Node *Open)第 8 页 共 14 页return Open-nextNode;/输出最佳路径函数入口void PrintPath(struct Node * head)struct Node *q,
11、*q1,*p;int i;int j;int count=1;p = (struct Node *)malloc(sizeof(struct Node);p-previousNode = NULL;q = head;while(q)q1 = q-previousNode;q-previousNode = p-previousNode;p-previousNode = q;q = q1;q = p-previousNode;while(q)if(q = p-previousNode)printf( 问题的初始状态：nn);else if(q-previousNode = NULL)printf(
12、 问题的目标状态：nn);else printf( 问题的中间状态 %d：nn,count+);for(i=0; isij!=0)printf(%3d,q-sij);第 9 页 共 14 页elseprintf( );if(j = 2)printf(n);printf(n);q = q-previousNode;/八数码问题的启发函数为：f(n)=d(n)+p(n)void dealAlgorithm(struct Node * Open, struct Node * Closed)int i,j;struct Node * BESTNODE, *inital, * Successor;ini
13、tal = (struct Node * )malloc(sizeof(struct Node);for(i=0; isij = startStateij;inital-f = wrongNumber(startState);inital-g = 0;inital-previousNode = NULL;inital-nextNode = NULL;addNodeFunction(Open, inital);openNode+;while(1) if(openNode = 0)printf(failure!); return;else BESTNODE = getBestNode(Open);
14、deleteNodeFunction(Open, BESTNODE);openNode-;addNodeFunction(Closed, BESTNODE);if(arrayEqual(BESTNODE-s, endState) printf(*成功找到问题解决方案*nn);PrintPath(BESTNODE);第 10 页 共 14 页return;elseSuccessor = (struct Node * )malloc(sizeof(struct Node); Successor-nextNode = NULL;if(getNextNodes(BESTNODE, 0, Success
15、or)dealLaterNodes( Open, BESTNODE, Closed, Successor);Successor = (struct Node * )malloc(sizeof(struct Node);Successor-nextNode = NULL;if(getNextNodes(BESTNODE, 1, Successor)dealLaterNodes( Open, BESTNODE, Closed, Successor);Successor = (struct Node * )malloc(sizeof(struct Node); Successor-nextNode = NULL;if(getNextNodes(BESTNODE,
