人工智能-启发式搜索.doc

实验报告 姓名： 叶子烽 学号： 2220132380 班级： 软件二班实验名称： 启发式搜索课程名称： 人工智能实验日期： 2015.11.09实验环境：Visual C+实验目的以及内容：1、 实验内容：使用启发式搜索算法求解八数码问题。（1）编制程序实现求解八数码问题A*算法，采用估价函数 其中：d(n)是搜索树中节点n的深度；w(n)为节点n的数据库中错放的棋子个数；p(n)为节点n的数据库中的每个棋子与其目标位置之间的距离的总和。（2） 分析上述（1）中的两种估价函数求解八数码问题的效率差别，给出一个是p(n)的上界的h(n)的定义，并测试使用该估价函数是否使算法失去可采纳性。2、实验目的：熟练的掌握启发式搜索A*算法及其可采纳性。3. 实验原理 ：八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。代码：#includestdio.h #define num 3 void show(int beginnumnum) for(int i = 0; i num; i+) for(int j = 0; j num; j+) printf(%d , beginij); printf(n); printf(n); void exchange(int beginnumnum, int row_one, int column_one, int row_two, int column_two) int temp; temp = beginrow_twocolumn_two ; beginrow_twocolumn_two = beginrow_onecolumn_one; beginrow_onecolumn_one = temp; int judge(int beginnumnum, int endnumnum) int count=0; for(int i = 0; i num; i+) for(int j = 0; j = 20) return 0; int node; int temp; for(int q=0; qjishu; q+) node = 1; for(int w=0; wnum & node; w+) for(int r=0; rnum & node; r+) if(ji_shuqwr != beginwr) node = 0; if(node = 1) return 0; for(int i = 0; i num; i+) for(int j = 0; j 0 & biaoji != 0) exchange(begin, row - 1, column, row , column); temp = judge(begin, end); if(temp = right) temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column); if( temp_zhi = 1) return 1; exchange(begin, row - 1, column, row , column); if(column 0 & biaoji != 1) exchange(begin, row, column - 1, row , column); temp = judge(begin, end); if(temp = right) temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column - 1); if(temp_zhi = 1) return 1; exchange(begin, row, column - 1, row , column); if(row num-1 & biaoji != 2) exchange(begin, row + 1, column, row , column); temp = judge(begin, end); if(temp = right) temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column); if(temp_zhi = 1) return 1; exchange(begin, row + 1, column, row , column); if(column num-1 & biaoji != 3) exchange(begin, row, column + 1, row , column); temp = judge(begin, end); if(temp = right) temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1); if(temp_zhi = 1) return 1; exchange(begin, row, column + 1, row , column); return 0; void shuru(int beginnum,int blank) int temp, node, zero = 0; for (int i = 0; i num; i+) for(int j = 0; j num; j+) node = 1; printf(请输入第%d行，第%d列的元素的值：, i+1, j+1); scanf(%d, &temp); for (int q = 0; q = i & node = 1; q+) for (int w = 0; w j; w+) if(temp = beginqw) printf(输入重复，请重新输入n); node = 0; j-; break; if(temp num*num-1) printf(请输入从%d到%d的数n, zero, num*num-1); node = 0; j-; if(node = 1) if(temp = 0) blank0 = i; blank1 = j; beginij = temp; int main() int jishu = 0, ji_shu5033; int row; int column; int beginnumnum, blank2,count=1; int endnumnum = 1, 2, 3, 8, 0, 4, 7, 6, 5; printf (-8数码游戏开始！-n); shuru(begin, blank); row = blank0; column = blank1; if(yidong (begin, end,judge(begin,end),jishu,ji_shu,4,row,column) = 0) printf(n此8数码的问题可能无解！); else show(begin); getchar();getchar(); return 0; 实验截图：实验总结： 1、 A*搜索算法：取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中每一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌