第三章习题--搜索策略

1 搜索策略搜索策略是指在搜索过程中如何选择扩展节点的次序问题。

一般来说，搜索策略就是采用试探的方法。

它有两种类型：一类是回溯搜索，另一类是图搜索策略。

2 盲目的图搜索策略图搜索策略又可分为两种：一种称为盲目的图搜索策略，或称无信息图搜索策略；而另一种称为启发式搜索策略，又称为有信息的图搜索策略。

最常用的两种无信息图搜索策略是宽度优先搜索和深度优先搜索。

2.1 宽度优先搜索它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。

所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。

这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。

2.2 深度优先搜索它是从根节点开始，首先扩展最新产生的节点，即沿着搜索树的深度发展下去，一直到没有后继结点处时再返回，换一条路径走下去。

就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。

这种方法的搜索树是从树根开始一枝一枝逐渐形成的。

由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。

为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的。

另外，应用此策略得到的解不一定是最佳解（最短路径）举例BFS搜索的一般过程。

POJ 2251Dungeon Master#include<iostream>#include<stdio.h>#include<algorithm>#include<queue>using namespace std;#define MMax 31struct node//入队的每个节点的信息{int x,y,z,t;};char map[MMax][MMax][MMax];int r,c,l;node start,end;//上，下，左，右，前，后六个方向，三维地图的搜索intdis[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};/*二维的有左，右，前，后方向：int dis[4][2]={{0,1},{0,-1},{1,0},{-1,0}}*//*当然，还有相应的八个方向的搜索什么的，修改一下dis就可以了*/bool judge(node a)//判断节点a有无越界{return(a.x>=0&&a.x<l&&a.y>=0&&a.y<r&&a.z>=0&&a.z<c);}int bfs(){node now,next;queue<node>Q;//申请一个结构体node类型的队列Qstart.t=0;//开始节点Q.push(start);//开始节点入队map[start.x][start.y][start.z]='#';//标记while(!Q.empty())//判断队是否为空，空返回true{now=Q.front();//出队一个节点给nowQ.pop();//删除队头元素/*上面两个一般是连起来用的*/for(int i=0;i<6;i++)//枚举6个方向{//next为该方向要搜的那个点next.x=now.x+dis[i][0];next.y=now.y+dis[i][1];next.z=now.z+dis[i][2];if(judge(next)&& map[next.x][next.y][next.z]!='#')//条件{next.t=now.t+1;if(map[next.x][next.y][next.z]=='E')//搜到了return next.t;map[next.x][next.y][next.z]='#';//标记Q.push(next);//入队}}}return-1;}int main(){//freopen("D://1.txt","r",stdin);while(scanf("%d%d%d",&l,&r,&c)!=EOF){if(l+r+c==0)break;for(int i=0;i<l;i++){for(int j=0;j<r;j++){//cin>>map[i][j];scanf("%s",map[i][j]);for(int k=0;k<c;k++){if(map[i][j][k]=='S')start.x=i,start.y=j,start.z=k;//开始节点else if(map[i][j][k]=='E')end.x=i,end.y=j,end.z=k;//}}}int ans=bfs();if(ans==-1)printf("Trapped!\n");else printf("Escaped in %d minute(s).\n",ans);}return0;}。

人工智能第三版课件第3章搜索的基本策略搜索引擎是当今互联网时代不可或缺的工具，而人工智能技术在搜索引擎中起着举足轻重的作用。

本文将介绍《人工智能第三版课件》中第3章的内容，讨论搜索的基本策略。

基于这些策略，搜索引擎能够更加高效、准确地满足用户的信息需求。

1. 初始搜索空间在进行搜索之前，需要建立一个初始的搜索空间，即包含可能相关信息的一组文档或网页。

这个搜索空间的建立可以通过爬虫程序和抓取技术来收集网络上的信息，并将其存储在搜索引擎的数据库中。

2. 关键词匹配搜索引擎通过用户输入的关键词与搜索空间中的文档进行匹配，以找到与用户需求相关的内容。

关键词匹配可以使用词频、倒排索引等算法来实现。

其中，词频是指对于一个给定的关键词，在搜索空间中出现的频率；倒排索引则是一种将关键词与对应的文档进行关联的索引结构。

3. 分析用户意图搜索引擎还需要通过分析用户的搜索历史、点击行为等数据来了解用户的真实意图。

这可以通过机器学习算法来实现，例如基于用户行为的推荐系统。

通过了解用户的意图，搜索引擎可以更加准确地推荐相关内容。

4. 搜索结果排序搜索引擎会对匹配到的文档进行排序，以便将最相关的结果显示在前面。

排序算法通常通过计算文档与用户查询的相似度来实现。

相似度计算可以使用向量空间模型、BM25等算法。

5. 反馈与迭代搜索引擎不断根据用户的反馈进行迭代，以提供更好的搜索结果。

用户的反馈可以包括点击率、停留时间等指标，这些指标可以通过机器学习算法来进行分析和预测。

搜索引擎可以根据用户的反馈来调整排序算法，从而不断改进搜索结果的准确性和相关性。

综上所述，搜索引擎的基本策略包括建立初始搜索空间、关键词匹配、分析用户意图、搜索结果排序以及反馈与迭代。

这些策略通过人工智能技术的应用，使得搜索引擎能够更加智能化地满足用户的信息需求。

未来随着人工智能技术的不断发展，搜索引擎将会变得更加准确、个性化，并为用户提供更多智能化的服务。

⼈⼯智能习题作业搜索策略I习题答案第三章搜索策略课后习题及答案⼀、选择题：1. 启发式搜索中，通常OPEN表上的节点按照它们f函数值的_____顺序排列。

（ D ）A平均值 B 递减 C 最⼩ D递增2. 按尼尔逊(Nilsson)提出的有序搜索基本算法指出,⼀个节点的希望程度⼤，则f值_____。

（ B ）A 不变化B ⼩C ⼤D 为03. 如果重排OPEN表是依据f(x)=g(x)+h(x)进⾏的，则称该过程为_____。

（ B ）A A*算法B A算法 C有序搜索 D启发式搜索4. 在与或树和与或图中，我们把没有任何⽗辈节点的节点叫做_____。

（ C ）A 叶节点 B端节点 C根节点 D 起始节点5. 对于⼋数码问题：起始棋局 —> ⽬标局棋2 83 1 2 31 6 4 8 47 5 7 6 5取h(n)=W(n)， W(n)⽤来计算对应于节点n的数据库中错放的棋⼦个数。

请问需要扩展多少个节点才能到达⽬标？（ C ）A 20B 13C 6D 116. α-β剪枝技术中，⼀个MIN节点的β值等于其后继节点当前（）的最终倒推值。

（ A ）A 最⼩B 最⼤C 平均D α值7. α-β剪枝技术中，“或”节点n的α值如果不能降低其⽗节点的β值，则对节点n以下的分枝可停⽌搜索，并使节点n的倒推值为α。

这种剪枝称为_____。

（ A ）A β剪枝B α剪枝C α-β剪枝 D极⼩极⼤分析法8. 宽度优先搜索⽅法能够保证在搜索树中找到⼀条通向⽬标节点的_____途径(如果有路径存在时)。

（ B ）A 可⾏B 最短C 最长D 解答9. A*算法是⼀种_____。

（ ABD ）A 图搜索策略B 有序搜索算法C 盲⽬搜索D 启发式搜索10. 应⽤某个算法(例如等代价算法)选择OPEN表上具有最⼩f值的节点作为下⼀个要扩展的节点。

这种搜索⽅法的算法就叫做_____。

（ C ）A 盲⽬搜索B 深度优先搜索C 有序搜索算法D 极⼩极⼤分析法⼆、填空题：1. OPEN表⽤于存放未扩展的节点，CLOSED表存放_已扩展_的节点。

第三章练习题1. 根据图1，单独执行以下操作，正确的是（）A) 将Ａ文件夹拖到Ｂ文件夹中B) 将cc.doc文件拖到dd.doc文件中C) 将cc.doc文件与Ａ文件夹拖到dd.doc文件中D) 将Ａ文件夹拖到cc.doc文件中图12. 图1中，H盘根文件夹下有（）A) 5个文件B) 3个文件夹C) 2个文件D) 3个文件2个文件夹３．根据图1，将cc.doc文件与dd.doc文件同时拖到Ａ文件夹中，再将Ａ文件夹拖到Ｂ文件夹中，dd.doc所在的文件夹是（）Ａ) A B) B C) H:\A D) H:\B４. 执行第3题后, CC.doc存放的文件路径是（）A) H:/B/A B) H:/A/BC) H:/A D) H:\B\A５. 根据图2, 作业.doc文件的路径是（）A) H:/A/C/B/作业B) A\B\C\作业C) H:\A\C\B\作业D) H:\A\C\B图2６. 如图2，作业.doc所在的文件夹是（）A) 我的文档B) H:\ C) 作业D) 全错７. 设置如图3，搜索框里输入“A?.DOC”，搜索的结果是（）Ａ) AB.doc文件与ABC.DOC文件Ｂ) A ?.DOC 文件C）AB.doc文件与AB.PPT文件Ｄ) A B.DOC文件图38. Windows是一个（）操作系统A) 单用户单任务B) 单用户多任务C) 多用户多任务D) 多用户单任务9. 双击一个文档文件图标的功能是（）A) 打开该文档文件B) 运行创建该文档文件的应用程序C) 运行创建该文档文件的应用程序并打开该文档文件D) 以上均错10. 指向某图标右单击的功能是（）A) 弹出一个菜单项B) 弹出一个菜单C) 选中该图标D) 弹出一个与该对象相关的快捷菜单11. 将当前(活动)窗口作为图像送剪贴板的按键是（）A) Ctrl+shift B) Alt+PrintScreenC) PrintScreen D) Ctrl+SpaceE) Ctrl+Esc F) Ctrl+Alt+Del12. 程序文件的扩展名是（）A) .exe B) .doc C) .txt D) .ppt13. 指向某文件夹右单击，在弹出的快捷菜单中选择( )命令可以设置文件夹的隐藏属性。

《人工智能》课程习题第一章绪论1-1. 什么是人工智能？试从学科和能力两方面加以说明。

1-2. 在人工智能的发展过程中，有哪些思想和思潮起了重要作用？1-3. 为什么能够用机器（计算机）模仿人的智能？1-4. 现在人工智能有哪些学派？它们的认知观是什么？1-5. 你认为应从哪些层次对认知行为进行研究？1-6. 人工智能的主要研究和应用领域是什么？其中，哪些是新的研究热点？第二章知识表示方法2-1状态空间法、问题归约法、谓词逻辑法和语义网络法的要点是什么？它们有何本质上的联系及异同点?2-2设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。

该船的负载能力为两人。

在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。

他们怎样才能用这条船安全地把所有人都渡过河去?再定义描述过河方案的谓词：L-R(x, x1, y, y1,S)：x1个修道士和y1个野人渡船从河的左岸到河的右岸条件：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(L,S)动作：Safety(L,x-x1,y-y1,S’)∧Safety(R,3-x+x1,3-y+y1,S’)∧Boat(R,S’)R-L (x, x1, y, y1,S)：x2个修道士和y2个野人渡船从河的左岸到河的右岸条件：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(R,S)动作：Safety(R,3-x-x2,3-y-y2,S’)∧Safety(L,x+x2,y+y2,S’)∧Boat(L,S’)(2) 过河方案Safety(L,3,3,S0)∧Safety(R,0,0,S0)∧Boat(L,S0)L-R(3, 1, 3, 1,S0) L-R(3, 0, 3, 2,S0)Safety(L,2,2,S1)∧Safety(R,1,1,S1)∧Boat(R,S1)Safety(L,3,1,S1’)∧Safety(R,0,2,S1’)∧Boat(R,S1’)R-L (2, 1, 2, 0,S1) R-L (3,0, 1, 1,S1’)Safety(L,3,2,S2)∧Safety(R,0,1,S2)∧Boat(L,S2)L-R(3, 0, 2, 2,S2)Safety(L,3,0,S3)∧Safety(R,0,3,S3)∧Boat(R,S3)R-L (3, 0, 0, 1,S3)Safety(L,3,1,S4)∧Safety(R,0,2,S1)∧Boat(L,S4)L-R(3, 2, 1, 0,S4)Safety(L,1,1,S5)∧Safety(R,2,2,S5)∧Boat(R,S5)R-L (1, 1, 1, 1,S5)Safety(L,2,2,S6)∧Safety(R,1,1,S6)∧Boat(L,S6)L-R(2, 2, 2, 0,S6)Safety(L,0,2,S7)∧Safety(R,3,1,S7)∧Boat(R,S7)R-L (0, 0, 2, 1,S7)Safety(L,0,3,S8)∧Safety(R,3,0,S8)∧Boat(L,S8)L-R(0, 0, 3, 2,S8)Safety(L,0,1,S9)∧Safety(R,3,2,S9)∧Boat(R,S9)R-L (0, 1, 1, 0,S9)Safety(L,1,1,S10)∧Safety(R,2,2,S10)∧Boat(L,S10)2-3利用图2.3，用状态空间法规划一个最短的旅行路程：此旅程从城市A开始，访问其他城市不多于一次，并返回A。

1、Internet网络管理框架由哪些部分组成？支持SNMP的体系结构由哪些协议层组成？1、RFC1155定义了管理信息结构（SMI），即规定了管理对象的语法和语义2、RFC1212说明了定义MIB模块的方法3、RFC1213定义了MIB-2管理对象的核心集合，这些管理对象是任何SNMP系统必须实现的4、RFC1157是SNMPV1协议的规范文件。

应用层协议，UDP协议，TCP/IP2、SNMP环境中的管理对象是如何组织的？这种组织方式有什么意义？组织：分层的树结构。

意义：1、表示管理和控制关系2、提供了结构化的信息组织技术3、提供了对象命名机制3、MIB-2中的应用类型有哪些？计数器类型和计量器类型有什么区别？应用类型有：NetworkAddress、internetOBJECTIDENTIFIER、IpAddress、Counter、Gauge、TimeTicks、Opaque。

计数器可用于计算收到的分组数或字节数等，计量器可用于表示存储在缓冲队列中的分组数。

两种类型的最大值是2的32次方减1。

计数器类型Counter：：=可以增加，但不能减少，达到最大值回零。

计量器类型Cauge：：=其值可以增加，也可以减少，大到最大值后不回零，锁定在2的32次方减1。

4、RFC1212给出的宏定义由哪些部分组成？试按照这个宏定义产生一个宏实例宏定义由类型表示（TYPE NOTATION）、值表示（VALUE NOTATION）和支持产生式（supporting syntax）3部分组成，而最后部分是任选的，是关于宏定义体中类型的详细语法说明。

宏实例（即ASN.1类型）的定义首先是对象名，然后是宏定义的名字，最后是宏定义规定的宏体部分。

下面给出对象定义的示例，对Internet控制报文协议流入的信息计数。

icmpIlMsgs OBJECT-TYPESYNTAX CounterACCESS read-onlySTATUS mandatory：：=｛icmp 1｝5、MIB－2 的管理对象分为哪几个组？MIB-2包括11个功能组，分别是：System组、Interfaces组、At组、Ip组、Icmp 组、Tcp 组、Udp组、Egp组、Cmot组、Transmission组、Snmp组。

习题一、选择题1 .关于“与/或”图表示法的叙述中，正确的是（）A用“AND”和“OR”连续各部分的图形，用来描述各部分的因果关系B用“AND”和“OR”连续各部分的图形，用来描述各部分之间的不确定关系C是用“与”节点和“或”节点组合起来的树形图，用来描述某类问题的求解过程D是用“与”节点和“或”节点组合起来的树形图，用来描述某类问题的层次关系2 .在与或树和与或图中，把没有任何父辈节点的节点叫做：A叶节点B端节点C根节点D起始节点3 .启发式搜索中，通常OPEN表上的节点按照它们的估价函数f值的（）顺序排列：A递增B平均值C递减D最小4 .启广度优先搜索方法能够保证在搜索树种找到一条通向目标节点的（）路径（如果有路径存在时）。

A可行B最短C最长D解答5 .下列属于遗传算法的基本内容的是（）A图像识别B遗传算子C语音识别D神经调节6 .A*算法是一种（）。

A图搜索策略B有序搜索算法C盲目搜索D启发式搜索二、简答题1 .什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？2 .什么是与树？什么是或树？什么是与/或树？什么是可解节点？什么是解树？3 .何为股价函数？估价函数中，g（n）和h（n）各起什么作用？4 .什么是遗传算法？简述其基本思想和基本结构。

5 .常用的适应度函数有哪几种？参考答案一、选择题1. D2.C3.D4.A5.B6.D二、简答题1 .向这种根据世界情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。

简单地说，搜索就是利用已知条件在(知识)寻求解决问题办法的过程。

根据是否采用智能方法，搜索算法分为盲目搜索算法和智能搜索算法。

3 .用于估价结点重要性的函数称为估价函数，其一般形式为：/(n)=gQ)+h(n)其中，g(〃)是代价函数，表示从初始结点S。

到结点〃已经实际付出的代价；力(〃)是启发式函数，表示从结点〃到目标结点Sg的最优路径的估计代价。

搜索策略部分参考答案1 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。

题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。

解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。

第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。

由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。

第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。

由于农夫必须在船上，故对农夫的表示省略。

搜索策略部分参考答案1 有一农夫带一条狼，一只羊和一框青菜与从河的左岸乘船倒右岸，但受到下列条件的限制：(1) 船太小，农夫每次只能带一样东西过河；(2)如果没有农夫看管，则狼要吃羊，羊要吃菜。

请设计一个过河方案，使得农夫、浪、羊都能不受损失的过河，画出相应的状态空间图。

题示：(1) 用四元组（农夫，狼，羊，菜）表示状态，其中每个元素都为0或1，用0表示在左岸，用1表示在右岸。

(2) 把每次过河的一种安排作为一种操作，每次过河都必须有农夫，因为只有他可以划船。

解：第一步，定义问题的描述形式用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。

第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。

由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。

第三步，定义操作，即用于状态变换的算符组F由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。

由于农夫必须在船上，故对农夫的表示省略。