第9章启发式搜索案例

[高中信息技术]“启发式搜索与人机博弈”的教学设计人工智能是一门研究运用计算机模拟和延伸人脑功能的综合性学科，在教学中难度较大。

因此，我们试图在人工智能的教学过程中，创设一些学生能够接收的、有兴趣的实践活动。

通过活动让学生进行思考，并让学生自己得出相关的结论。

我们希望学生得出的结论是无统一答案的，能体现学生想象力、创造力的结论。

并将学生的结论发布在网络的论坛上，在师生讨论这些结论的过程中，进一步提升全体学生对人工智能的认识，感受人工智能技术的丰富魅力。

下面就“启发式搜索与人机博弈”的两节课，根据上述思路进行教学设计。

在进行“启发式搜索与人机博弈”教学之前，学生已经学习了穷举式搜索的知识，如宽度优先搜索和深度优先搜索；已经了解了状态空间、状态空间搜索及启发式搜索的基本概念。

在“启发式搜索与人机博弈”的教学中，将通过相关活动，让学生进一步了解启发式搜索的过程、启发式搜索与穷举式搜索的不同之处。

在“启发式搜索与人机博弈”的任务驱动法中，如何设计学生活动是至关重要的。

好的学生活动将激发学生的学习兴趣，活跃学生的思维，因此，在下面的具体的教学设计中，重点给出我们设计的教学活动。

抛砖引玉，希望同行们能给出更多、更好的学生活动。

一、“启发式搜索与人机博弈”的第一堂课教学任务：任务1：让学生实际操作电子字典(例如文曲星)或博弈网站中的“黑白棋”游戏，写出该游戏的规则，并在“玩”的过程中，总结出自己设想的“致胜”法则。

任务2：进入因特网，查找“人机博弈”的相关资料。

课前准备：·让学生准备带有黑白棋的电子字典。

（或者在网络教室的每一台学生机上，安装黑白棋程序。

）·在教师机中，设置“教学资料”只读共享文件夹，存放有表格一和表格二的Word文档。

·在教师机中，设置“作业上交”完全共享文件夹，学生完成的作业上交至该文件夹中。

教学过程：表格一：黑白棋的游戏规则表格二：你认为的“致胜”法则注：尽量标明“致胜”法则的优先级。

实验一启发式搜索算法学号：**********班级：计科二班姓名：***一、实验内容：使用启发式搜索算法求解8数码问题。

1、编制程序实现求解8数码问题A *算法，采用估价函数()()()()w n f n d n p n ⎧⎪=+⎨⎪⎩， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。

2、 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界 的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。

二、实验目的：熟练掌握启发式搜索A *算法及其可采纳性。

三、实验原理：（一）问题描述在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。

这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。

现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。

该问题称八数码难题或者重排九宫问题。

（二）问题分析八数码问题是个典型的状态图搜索问题。

搜索方式有两种基本的方式，即树式搜索和线式搜索。

搜索策略大体有盲目搜索和启发式搜索两大类。

盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。

启发式搜索:由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。

所以引入启发式搜索策略。

启发式搜索就是利用启发性信息进行制导的搜索。

它有利于快速找到问题的解。

由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。

所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。

即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。

绪论单元测试1、1956年达特茅斯会议上，学者们首次提出“artificial intelligence（人工智能）”这个概念时，所确定的人工智能研究方向不包括：A:研究如何用计算机表示人类知识B:研究智能学习的机制C:研究人类大脑结构和智能起源D:研究如何用计算机来模拟人类智能答案: 【研究人类大脑结构和智能起源】2、在现阶段，下列哪项尚未成为人工智能研究的主要方向和目标：A:研究如何用计算机模拟人类大脑的网络结构和部分功能B:研究如何用计算机延伸和扩展人类智能C:研究机器智能与人类智能的本质差别D:研究如何用计算机模拟人类智能的若干功能，如会听、会看、会说答案: 【研究机器智能与人类智能的本质差别】3、下面哪个不是人工智能的主要研究流派？A:符号主义B:经验主义C:连接主义D:模拟主义答案: 【模拟主义】4、从人工智能研究流派来看，西蒙和纽厄尔提出的“逻辑理论家”方法用，应当属于：A:经验主义，行为主义B:符号主义，连接主义C:连接主义，经验主义D:理性主义，符号主义答案: 【理性主义，符号主义】5、从人工智能研究流派来看，明斯基等人所推荐的“人工神经网络”方法用计算机模拟神经元及其连接，实现自主识别、判断，应当属于：A:理性主义，符号主义B:符号主义，连接主义C:经验主义，行为主义D:连接主义，经验主义答案: 【连接主义，经验主义】6、“鸟飞派”指的是人类研究人工智能必须要完全符合智能现象的本质A:错B:对答案: 【错】7、人工智能受到越来越多的关注，许多国家出台了支持人工智能发展的战略计划A:对B:错答案: 【对】8、人工智能将脱离人类控制，并最终毁灭人类A:对B:错答案: 【错】9、人工智能目前仅适用于特定的、专用的问题A:对B:错答案: 【对】10、通用人工智能的发展正处于起步阶段A:对B:错答案: 【对】第一章单元测试1、以下组合最能全面包括所有知识表示形式的是A:谓词逻辑、经验主义、网络权重B:符号主义、经验主义、连接主义C:产生式系统、特征表示、连接主义D:符号主义、特征表示、语义向量答案: 【符号主义、经验主义、连接主义】2、以下用谓词表示的命题错误的是A:老王的生日在4月：birthday（老王，4月）B:小博不在实验室：in(小博，实验室)C:我爸爸喜欢吃鸡蛋并且我妈妈喜欢吃西红柿：like_eat(father(我)，鸡蛋) ∨like_eat(mother(我)，西红柿)D:大亮的老师擅长打羽毛球和网球：good_at(teacher(大亮)，羽毛球) good_at(teacher(大亮)，网球)答案: 【我爸爸喜欢吃鸡蛋并且我妈妈喜欢吃西红柿：like_eat(father(我)，鸡蛋) ∨like_eat(mother(我)，西红柿)】3、哪种知识表示的样本数据的特征表示，就对应了某种知识。

九宫格的启发式搜索班级：计算机一班姓名：覃荣锦学号：*******目录一、实验目的 (3)二、实验语言环境 (3)三、实现设计 (3)1.状态表示： (3)2.算法介绍： (3)1)广度优先搜索： (3)2)深度优先搜索： (4)3.初始化节点以及判断目标节点 (5)4.拓展节点 (6)5.搜索算法 (7)四、程序全部代码 (8)五、分析总结 (15)1.数据结构分析 (15)2.拓展方法分析 (15)3.搜索算法分析 (15)六、运行结果 (16)七、遇见的问题以及解决方法 (16)一、实验目的加深对局部择优搜索以及全局择优搜索的熟悉程度。

了解局部择优搜索以及全局择优搜索的区别。

二、实验语言环境系统：微软Window7系统开发工具：visual c/c++ 6.0语言：c语言三、实现设计1.状态表示：九宫格状态以一组一维数组表示。

1~8分别表示8个对应的数字，0表示空格，数据结构如下：Typedef struct{Int data[9];}Data;九宫格节点为以线性表表示的树的节点，因此需要加入指向该节点父母的指针，在这里用下标表示，同时由于不同节点有不同的估值，因此需要加入表示其值变量。

完整的数据结构如下：typedef struct{int data[9];int parent;int value;} Data;2.算法介绍：1)局部择优搜索：第一步：把初始节点S0放入open表。

第二步：如果open表为空，则问题无解，退出。

第三步：把OPEN表的第一个节点取出放入CLOSE表，记该节点为节点n。

第四步：观察节点n是否为目标节点，若是，则求得问题的解，退出。

第五步：拓展节点n，将扩展的的节点排序后放入open表，将合法节点放入open表中。

然后转到第二步。

2)全局择优搜索：第一步：把初始节点S0放入open表。

第二步：如果open表为空，则问题无解，退出。

第三步：把OPEN表的最后一个节点取出放入CLOSE表，记该节点为节点n。

实验报告姓名：***学号：**********班级：软件二班实验名称：启发式搜索课程名称：人工智能实验日期：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个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

代码：#include"stdio.h"#define num 3void show(int begin[num][num]){for(int i = 0; i < num; i++){for(int j = 0; j < num; j++)printf("%d ", begin[i][j]);printf("\n");}printf("\n");}void exchange(int begin[num][num], int row_one, int column_one, int row_two, int column_two){int temp;temp = begin[row_two][column_two] ;begin[row_two][column_two] = begin[row_one][column_one];begin[row_one][column_one] = temp;}int judge(int begin[num][num], int end[num][num]){int count=0;for(int i = 0; i < num; i++)for(int j = 0; j < num; j++){if(begin[i][j] == end[i][j] && end[i][j] != 0)count++;}return count;}int yidong(int begin[num][num], int end[num][num], int right, int jishu, int ji_shu[50][3][3], int biaoji, int row, int column){int temp_zhi;show(begin);if(jishu >= 20)return 0;int node;int temp;for(int q=0; q<jishu; q++){node = 1;for(int w=0; w<num && node; w++)for(int r=0; r<num && node; r++)if(ji_shu[q][w][r] != begin[w][r])node = 0;if(node == 1){return 0;}}for(int i = 0; i < num; i++)for(int j = 0; j < num; j++)ji_shu[jishu][i][j] = begin[i][j];if(right == num * num - 1)return 1;if(row > 0 && biaoji != 0){exchange(begin, row - 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row - 1, column, row , column);else 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)exchange(begin, row, column - 1, row , column);else 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)exchange(begin, row + 1, column, row , column);else 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)exchange(begin, row, column + 1, row , column);else 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 begin[][num],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 == begin[q][w]){printf("输入重复，请重新输入\n");node = 0;j--;break;}if(temp < 0 || temp > num*num-1){printf("请输入从%d到%d的数\n", zero, num*num-1);node = 0;j--;}if(node == 1){if(temp == 0){blank[0] = i;blank[1] = j;}begin[i][j] = temp;}}}int main(){int jishu = 0, ji_shu[50][3][3];int row;int column;int begin[num][num], blank[2],count=1;int end[num][num] = {1, 2, 3, 8, 0, 4, 7, 6, 5};printf ("-------8数码游戏开始！--------\n");shuru(begin, blank);row = blank[0];column = blank[1];if(yidong (begin, end,judge(begin,end),jishu,ji_shu,4,row,column) == 0)printf("\n此8数码的问题可能无解！");elseshow(begin);getchar();getchar();return 0;}实验截图：实验总结：1、A*搜索算法：取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中每一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌）的总和，由于从结点n转换成目标结点至少需要w(n)步，所以对任意n，恒有w(n) ≤h*(n)。