中南民族大学人工智能导论实验报告.pdf

院系：计算机科学学院专业：xxx年级：xxx 级课程名称：人工智能导论学号：xxx姓名：xxx指导教师:2013 年 12 月 1 日年级xxx 级xxx学号xxx专业xxx姓名xxx实验 名称水壶问题实验 类型设计型综合型创新型√实 验 目 的 或 要 求给定 A，B 两个个水壶，一个最终状态 C ，其中水壶 A 的容量为 V_A, 水壶 B 的 容量为 V_B，求是否可以通过水壶 A 和 B，使得最终 A 或 B 中水的体积为 C实 验 原 理 （ 算 法 流 程 ）约定有 6 中操作，并分别记为操作号 1，2,3,4,5,61. FILL(A)将 A 壶装满 2. FILL(B)将 B 壶装满 3. Empty(A)将 A 壶中的水倒空 4. Empty(B)将 B 壶中的水倒空 5. Pour(A,B)将水从 A 壶倒到 B 壶 6. Pour(B,A)将水从 B 壶倒到 A 壶A， B 壶的初始状态为空，显然这是一颗六叉树，并且这不是一颗完整的六叉树， 因为有一些节点并不符合，对于不合法的节点，将它剪掉（剪枝操作）广度优先搜索（BFS） ：(1) 将首节点（0,0）入队(2) 队列不为空循环[2.1]队首节点出队，判断 A,B 壶中是否至少有一个达到 C 状态[2.2]对于 6 种操作， 每个父节点产生 6 个新的节点， 将合法的节点入 队，不和法的节点剪掉(3) 如果有可行解，打印可行解组 内 分 工 （ 可 选 ）实 验 结 果 分 析 及 心 得 体 会运行结果截图：成 绩 评 定教师签名：2013 年月日备注：源代码附后，源代码要求有注释说明备注：源代码附后，源代码要求有注释说明代码：代码： #include #include #include #include #include #define M 1000int vis[M+5][M+5]; int aNum, bNum, cNum;struct Node/* 状态节点 */ { int x; int y; int step; };struct parent/* 记忆表 */ { int px; int py; }prev[M+5][M+5];void dfs(int x, int y) { if (prev[x][y].px+prev[x][y].py != 0) { dfs(prev[x][y].px, prev[x][y].py); }/* End of If */int prex = prev[x][y].px; int prey = prev[x][y].py;/* Fill(A) */ if (prex!=aNum return ; }/* Fill(B) */ if (prey!=bNum return ; }/* Empty(A) */ if (prex!=0 return ; }/* Empty(B) */if (prey!=0 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;/* 问题求解标志，初始时问题未被求解 */ int rear = -1;/* 队列尾指针 */ int front = -1;/* 队首指针 */ Node cur, next; Node queue[M+10]={0};cur.x = 0;/* 当前水壶 A 状态 */ cur.y = 0;/* 当前水壶 B 状态 */ cur.step = 0;/* 记录当前步数 */ queue[++rear] = cur; /* 初始状态入队 */vis[0][0] = 1;/* 初始状态设为已被访问 */ while (front != rear) {/* 队列不为空时循环 */ cur = queue[++front]; if (cur.x==cNum || cur.y==cNum) { IsSolve = 1; printf(“Total Step : %d\n“, 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 (!vis[next.x][next.y]) { vis[next.x][next.y] = 1;prev[next.x][next.y].px = cur.x;/* 记忆表的实现 */ prev[next.x][next.y].py = cur.y;queue[++rear] = next; }/* OP 2: Fill(B) */ next.x = cur.x; next.y = bNum; if (!vis[next.x][next.y]) { vis[next.x][next.y] = 1; prev[next.x][next.y].px = cur.x; prev[next.x][next.y].py = cur.y;queue[++rear] = next; }/* OP 3: Empty(A) */ next.x = 0; next.y = cur.y; if (!vis[next.x][next.y]) { vis[next.x][next.y] = 1; prev[next.x][next.y].px = cur.x; prev[next.x][next.y].py = cur.y;queue[++rear] = next; }/* OP 4: Empty(B) */ next.x = cur.x; next.y = 0; if (!vis[next.x][next.y]) { vis[next.x][next.y] = 1; prev[next.x][next.y].px = cur.x; prev[next.x][next.y].py = cur.y;queue[++rear] = next; }/* OP 5: Pour(A, B) */ next.y = (cur.x+cur.y) #include #include #include #define N 1000 #define M 1000//#define localjudgeint hash[N+5][M+5][2];/* hash 判重 */ int nNum, mNum, kNum; /* N 个传教士，M 个野人，船一次能载 K 人 */struct Node { int leftMiss;/* 左岸的传教士人数 */ int leftSava;/* 左岸的野人数 */ int step;/* 记录移动步数 */ int boat;/* 表示船的位置，0 代表左岸，1 代表右岸 */ }queue[N*M+5];struct parent { int px; int py; int boat; }prev[N+5][M+5][2];/* 记录移动路径 */int IsLegal(int leftMiss, int leftSava, int boatMiss, int boatSava, int rightMiss, int rightSava) { if (leftMissnNum || leftSava>mNum) { return 0; } if (rightMissnNum || rightSava>mNum) { return 0; } if ((leftMiss /* 种群数的上限 */double r, x, y; double xx[maxn] = {0};/* 逼近最优解的 x 坐标 */ double yy[maxn] = {0};/* 逼近最优解的 y 坐标 */int main() { for (int i=1; i yy[j])/* 动态逼近 */ { xx[j] = x;/* 逼近最优解的 x */ yy[j] = y;/* 逼近最优解的 y */ } } }/* End of For */// Display printf(“\n |xy\n---------------\n“); for (int l=1; l #include #include int M[10];/** 权值 **/ int X[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; /** 输入向量 **/ int Y[10] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 0};/** 理想输出向量, 0 表示奇数， 1 表示偶数 **/ int O[10];/** 保存输出向量 **/ int ST = 51; /** 阈值 **无关随机数，任意值都可以//** 初始化权值 **/ void initM () { int x = 0; srand ((unsigned int)time(0)); for (x = 0; x ST) { return 1; } else { return 0; } }/** 计算输出向量 **/ void calcY () { int x = 0; for (x = 0; x = err) { /** 能够 100 %正确地回答问题了，结束训练 **/ break; } printf (“错误数 %d\n“, err); }printM (); printf (“阈值 %d 训练次数 %d\n“, ST, n);while (1) { int a = 0; scanf (“%i“, if (0 > a || 9 < a) { break; }test (a); } return 0; }。