人工智能导论实验报告.doc

《人工智能导论实验报告.doc》由会员分享，可在线阅读，更多相关《人工智能导论实验报告.doc（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、院 系： 计算机科学学院 专 业： 计算机科学与技术 年 级： 2012级 课程名称： 人工智能 学 号： 姓 名： 王亚戈 指导教师: 尹帆 2014年 6月 24 日年级 2012级班级 3班学号专业计算机科学与技术姓名 王亚戈实验名称八数码问题实验类型设计型综合型创新型实验目的或要求实验题目：实验原理（算法流程）#include#include#include#define Overflow 1#define N 3int goalNN=1,2,3,8,0,4,7,6,5;int zero2,NodeQTY=0;int *z=zero;/记录0的位置，zero0:r行；zero1:c列

2、typedef int Piece;struct Chessboard/棋盘信息 Piece posNN;/记录每个数码a的位置r行c列int d,f,move;/d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 ;struct LNodeChessboard board;LNode *parent,*next;bool flag;typedef LNode* List;int* Findzero(LNode* &Node)int i,j,zr2;int *z=zr;for(i=0;iN;i+)for(j=0;jboard.posij=0)zr0=i+1;zr1=j+1;brea

3、k;return z;int Wrong(LNode *Node)int w=0,i,j;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)w+;return w;int pick(LNode *Node)int w=0,i,j,ii,jj;for(i=0;iN;i+)for(j=0;jboard.posij!=goalij&Node-board.posij!=0)for(ii=0;iiN;ii+)for(jj=0;jjboard.posij=goaliijj) w=w+abs(ii-i)+abs(jj-j);brea

4、k; return w;LNode* extend(LNode *Node,int depth,int zero2,int moveflag,int Choose)LNode* NewNode=new LNode;for(int i=0;iN;i+)for(int j=0;jboard.posij=Node-board.posij;switch(moveflag)case 1:/向左移，不能出界：zero1=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1-2;NewNode-board.poszero0-1zero1

5、-2=0;break;case 2:/向右移，不能出界：zero1board.poszero0-1zero1-1=NewNode-board.poszero0-1zero1;NewNode-board.poszero0-1zero1=0;break;case 3:/向上移，不能出界：zero0=2NewNode-board.poszero0-1zero1-1=NewNode-board.poszero0-2zero1-1;NewNode-board.poszero0-2zero1-1=0;break;case 4:/向下移，不能出界：zero0board.poszero0-1zero1-1=N

6、ewNode-board.poszero0zero1-1;NewNode-board.poszero0zero1-1=0;break;NewNode-board.d=depth+1;switch(Choose)case 1:NewNode-board.f=NewNode-board.d+Wrong(NewNode);break; case 2:NewNode-board.f=NewNode-board.d+pick(NewNode);break; NewNode-board.move=moveflag;NewNode-parent=Node;NodeQTY+; return NewNode;v

7、oid InitList(LNode* &Open,LNode* &Close)Open=(List)malloc(sizeof(LNode);Close=(List)malloc(sizeof(LNode);if(!Open&!Close)exit(Overflow);Open-next=NULL;Close-next=NULL;int ListInsert(List &L,LNode* NewNode)List p=L;while(p-next)p=p-next;NewNode-next=p-next;p-next=NewNode;return true;LNode* Getminf(Li

8、st &L)List p=L,q=L-next,r=L,min;min=q;/p,q寻找f最小值的指针，r指向表L中min前一个元素 if(!q)return NULL;while(q)if(min-board.fq-board.f)r=p;min=q;p=q;q=q-next;r-next=min-next;min-next=NULL;return min;int main()int i,j,choose;List Open,Close;LNode *Best,*current;LNode *Start=new LNode;printf(ttt八 数 码 问 题 求 解n); printf(

9、n请输入初始状态：);for(i=0;iN;i+)for(j=0;jboard.posij);printf(注:The flag of movement-1:左移;2:右移;3:上移;4:下移)n);printf(初始棋盘状态：n); for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);InitList(Open,Close); printf(请选择(1:A算法;2:A*算法):); scanf(%d,&choose); Start-board.d=0;switch(choose)case 1:Start-board.f=Start-board.d+W

10、rong(Start);break; case 2:Start-board.f=Start-board.d+pick(Start);break; /Start-board.f=0+Wrong(Start);Start-board.move=0;Start-parent=NULL;Start-next=NULL;Start-flag=1;ListInsert(Open,Start);/将S加入到Open表中 while(Open-next)Best=Getminf(Open);ListInsert(Close,Best);if(!(Best-board.f-Best-board.d)printf

11、($*有解！*$n); break;z=Findzero(Best);zero0=*(z+0);zero1=*(z+1);if(zero1=N-1&Best-board.move!=2)ListInsert(Open,extend(Best,Best-board.d,zero,1,choose);if(zero1board.move!=1)ListInsert(Open,extend(Best,Best-board.d,zero,2,choose);if(zero0=N-1&Best-board.move!=4)ListInsert(Open,extend(Best,Best-board.d,

12、zero,3,choose);if(zero0board.move!=3)ListInsert(Open,extend(Best,Best-board.d,zero,4,choose);printf(本算法搜索图中总共扩展的节点数为：%dn,NodeQTY); printf(t最佳路径如下所示：n); if(Open-next)while(Best-parent)Best-flag=1;Best=Best-parent;List p=Close-next,q=Close-next;if(p=Start) q=p-next;else exit(1);int Step=0; while(p&q)/

13、在Close表中依标记找到路径 if(q-flag=1&q-parent=p)printf(Step %d:0 move as the %d-flag of movement.n,+Step,q-board.move);for(i=0;iN;i+)for(j=0;jboard.posij);printf(|n);p=q;/记住父节点 q=q-next;printf(到达目标状态！n); elseprintf(该问题无法求解！n);组内分工（可选） 实验结果分析及心得体会实验截图1、A算法： 2、A*算法： 心得体会通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所

14、扩在的节点数来看，看来比更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数来说，它的定义趋向多元化，只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path来找到路径，这样节省了存储空间，更利于搜索。通过实验结果来看，这两个函数都是可采纳的，尽管存在不必要的扩展。成绩评定教师签名： 2014年 月 日备注：源代码附后，源代

15、码要求有注释说明年级 2012级班级 3班学号专业 计算机科学与技术姓名 王亚戈实验名称水壶问题实验类型设计型综合型创新型实验目的或要求实验原理（算法流程）#include #include #include #include #include #define M 1000int visM+5M+5;int aNum, bNum, cNum;struct Node /* 状态节点 */ int x; int y; int step;struct parent /* 记忆表 */ int px; int py;prevM+5M+5;void dfs(int x, int y) if (prevx

16、y.px+prevxy.py != 0) dfs(prevxy.px, prevxy.py); /* End of If */ int prex = prevxy.px; int prey = prevxy.py; /* Fill(A) */ if (prex!=aNum & x=aNum & y=prey) printf(Fill(A)n); return ; /* Fill(B) */ if (prey!=bNum & y=bNum & x=prex) printf(Fill(B)n); return ; /* Empty(A) */ if (prex!=0 & x=0 & y=prey)

17、 printf(Empty(A)n); return ; /* Empty(B) */ if (prey!=0 & y=0 & x=prex) printf(Empty(B)n); return ; /* Pour(A,B) or Pour(B,A) */ if (prex+prey = x+y) /* 倒水前后总水量不变 */ if (x=0 | y=bNum) printf(Pour(A, B)n); else printf(Pour(B, A)n); return ; /* dfs */void BFS() int IsSolve = 0; /* 问题求解标志，初始时问题未被求解 */

18、int rear = -1; /* 队列尾指针 */ int front = -1; /* 队首指针 */ Node cur, next; Node queueM+10=0; cur.x = 0; /* 当前水壶 A 状态 */ cur.y = 0; /* 当前水壶 B 状态 */ cur.step = 0; /* 记录当前步数 */ queue+rear = cur; /* 初始状态入队 */ vis00 = 1; /* 初始状态设为已被访问 */ while (front != rear) /* 队列不为空时循环 */ cur = queue+front; if (cur.x=cNum |

19、 cur.y=cNum) IsSolve = 1; printf(Total Step : %dn, cur.step); dfs(cur.x, cur.y); /* dfs 回溯打印可行方案 */ break; /* End of If */ /* operation step add one */ next.step = cur.step + 1; /* OP 1: Fill(A) */ next.x = aNum; next.y = cur.y; if (!visnext.xnext.y) visnext.xnext.y = 1; prevnext.xnext.y.px = cur.x;

20、 /* 记忆表的实现 */ prevnext.xnext.y.py = cur.y; queue+rear = next; /* OP 2: Fill(B) */ next.x = cur.x; next.y = bNum; if (!visnext.xnext.y) visnext.xnext.y = 1; prevnext.xnext.y.px = cur.x; prevnext.xnext.y.py = cur.y; queue+rear = next; /* OP 3: Empty(A) */ next.x = 0; next.y = cur.y; if (!visnext.xnext

21、.y) visnext.xnext.y = 1; prevnext.xnext.y.px = cur.x; prevnext.xnext.y.py = cur.y; queue+rear = next; /* OP 4: Empty(B) */ next.x = cur.x; next.y = 0; if (!visnext.xnext.y) visnext.xnext.y = 1; prevnext.xnext.y.px = cur.x; prevnext.xnext.y.py = cur.y; queue+rear = next; /* OP 5: Pour(A, B) */ next.y

22、 = (cur.x+cur.y)bNum ? (cur.x+cur.y) : bNum; next.x = cur.x - (next.y - cur.y); if (!visnext.xnext.y) visnext.xnext.y = 1; prevnext.xnext.y.px = cur.x; prevnext.xnext.y.py = cur.y; queue+rear = next; /* OP 6: Pour(B, A) */ next.x = (cur.x+cur.y)aNum ? (cur.x+cur.y) : aNum; next.y = cur.y - (next.x -

23、 cur.x); if (!visnext.xnext.y) visnext.xnext.y = 1; prevnext.xnext.y.px = cur.x; prevnext.xnext.y.py = cur.y; queue+rear = next; /* End of While */ if (!IsSolve) printf(No Solution.n); /* BFS */int main() while (scanf(%d %d %d, &aNum, &bNum, &cNum) /* Reset the array */ memset(vis, 0, sizeof(vis); m

24、emset(prev, 0, sizeof(prev); BFS(); /* 利用广度优先搜索找出所有可能解 */ /* End of While */ return 0;组内分工（可选） 实验结果分析及心得体会实验截图 心得体会 本实验利用广度优先搜索找出所有可能解，进一步加深了我对该算法的理解。成绩评定教师签名： 2014年 月 日备注：源代码附后，源代码要求有注释说明年级2012级班级 3班 学号 专业计算机科学与技术姓名王亚戈实验名称遗传算法实验类型设计型综合型创新型实验目的或要求实验原理（算法流程）#include #include #include #include const i

25、nt maxn = 50; /* 种群数的上限 */ double r, x, y;double xxmaxn = 0; /* 逼近最优解的 x 坐标 */ double yymaxn = 0; /* 逼近最优解的 y 坐标 */ int main() for (int i=1; i=20; +i) /* 区间 1, 20 的 x，y 初始化 */ xxi = i*1.0; yyi = 10*sin(5*i)+7*cos(4*i); /* End of For */ srand(unsigned)time(NULL); for (int k=0; k=10; +k) for (int j=1;

26、 j yyj) /* 动态逼近 */ xxj = x; /* 逼近最优解的 x */ yyj = y; /* 逼近最优解的 y */ /* End of For */ / Display printf(n | x yn-n); for (int l=1; l=20; +l) printf( | %6.2lf %6.2lfn, xxi, yyl); printf(n); return 0;组内分工（可选） 实验结果分析及心得体会实验截图 心得体会 在遗传算法中，种群内进行交配、变异、选择，从而产生最优解。该实验加深了我对遗传算法的理解和体会，进一步了解了它的用途和好处。成绩评定教师签名： 2014年 月 日