人工智能及其应用,王万良第五章答案

1、5.1 什么是搜索？有哪两大类不同的搜索方法？二者的区别是什么？ 根据实际情况， 按照一定的策略或规则， 从知识库中寻找可利用的知识， 从而构造出一条使 问题获得解决的推理路线的过程， 就称为搜索 搜索一般分为盲目搜索和启发式搜 索。盲目搜索又称为无信息搜索， 即在搜索过程中， 只按预先规定的搜索控制策略进行 搜索， 而没有任何中间信息来改变这些控制策略。 由于这种搜索的控制策略都是预定的， 不 管什么问题都采用这样的控制策略， 这就使得搜索带有盲目性， 效率不高。 只适用于解决较 简单问题。启发式搜索又称有信息搜索， 它是指在求解过程中， 根据问题本身的特性或搜索过程中产生 的一些信息来不断

2、地改变或调整搜索的方向， 使搜索朝着最有希望的方向前进， 加速问题的 求解， 并找到最优解。 启发式搜索由于考虑到问题本身的特性并利用这些特性， 从而使搜索 求解的效率更高，更易于求解复杂问题5.2 什么是启发式搜索，什么是启发信息？启发式搜索就是在状态 空间中的搜索对每一个 搜索的位置进行 评估 ，得到最好的位置， 再从 这个位置进行搜索直到目标。为减小搜索范围而需要利用某些已知的，有关具体问题领域的特性信息。5.3 请阐述状态空间的一般搜索过程。OPEN表与 CLOSED表的作用是什么？有何区别？1) 把初始节点 S0 放入 OPEN表，并建立只含 S0的图，记为 G2) 检查 OPEN表

3、是否为空，若为空则问题无解，退出3) 把 OPEN表的第一个节点取出放入 CLOSE表，记该节点为节点 n4) 观察节点 n 是否为目标节点，若是，则求得问题的解，退出5) 扩展节点 n，生成一组子节点。 把其中不是节点 n 先辈的那些子节点记作集合 M，并把这 些节点作为节点 n 的子节点加入 G中。6) 针对 M中子节点的不同情况，分别进行如下处理对于那些未曾在 G 中出现过的 M成员设置一个指向父节点( n)的指针，并把它放入 OPEN 表对于那些先前已在 G中出现过的 M成员，确定是否要修改指向父节点的指针 对于那些先前已在 G中出现， 并且已经扩展了的 M成员，确定是否需要修改其后继

4、结点指向 父节点的指针7) 按某种搜索策略对 OPEN表中的节点进行排序8) 转第 2 步OPEN表：用于存放刚生成的节点CLOSE表：用于存放将要扩展或已扩展的节点区别：存放节点节点不同， open 表存放未扩展的节点， closed 表存放已经扩展的节点。 5.55 什么是盲目搜索？主要有几种盲目搜索策略？答：盲目搜索又称无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索， 而没有任何中间信息来改变这些控制策略。主要的盲目搜索策略有：宽度优先搜索、 深度优先搜索、 有界深度优先搜索、代价树的宽度优先搜索和代价树的深度优先搜索。5.7 宽度优先搜索与深度优先搜索有何不同？在何种情

5、况下， 宽度优先搜索优于深度优先搜 索？在何种情况下，深度优先搜索优于宽度优先搜索？宽度搜索又称为广度搜索。 其基本思想是： 从初始节点开始， 逐层对节点进行依次扩展， 并考察它是否为目标节点，在对下层节点进行扩展 （或搜索） 之前， 必须完成对当前层的所 有节点的扩展（或搜索） 。深度搜索也是一种盲目搜索策略。其基本思想是：首先扩展最新产生的 （即最深的）节 点，即从初始节点 S0 开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标 节点， 则对该节点进行扩展，并再从它的后继节点中选择一个节点进行考察。依此类推，一 直搜索下去， 当到达某个既非目标节点又无法继续扩展的节点时， 才选择其兄弟节点进行考 察。 在目标节点距离初始节点较近时，宽度优先搜索优于深度优先搜索5.1 野人与道士发1野人.渡1牧师、渡1野人1牧帅