原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI第三章 搜索推理技术3-1 什么是图搜索过程?其中，重排 OPEN 表意味着什么，重排的原则是什么?图搜索的一般过程如下：(1) 建立一个搜索图 G(初始只含有起始节点 S)，把 S 放到未扩展节点表中（OPEN 表）中。(2) 建立一个已扩展节点表（CLOSED 表） ，其初始为空表。(3) LOOP：若 OPEN 表是空表，则失败退出。(4) 选择 OPEN 表上的第一个节点，把它从 OPEN 表移出并放进 CLOSED 表中。称此节点为节点 n，它是 CLOSED 表中节点的编号(5) 若 n 为一目标节点，则有解并成功退出。此解是追踪图 G 中沿着指针从 n 到 S 这条路径而得到的(指针将在第 7 步中设置)(6) 扩展节点 n，生成不是 n 的祖先的那些后继节点的集合 M。将 M 添入图 G 中。 (7) 对那些未曾在 G 中出现过的(既未曾在 OPEN 表上或 CLOSED 表上出现过的)M 成员设置一个通向 n 的指针，并将它们加进 OPEN 表。对已经在 OPEN 或 CLOSED 表上的每个 M 成员，确定是否需要更改通到 n 的指针方向。对已在 CLOSED 表上的每个 M 成员，确定是否需要更改图 G 中通向它的每个后裔节点的指针方向。(8) 按某一任意方式或按某个探试值，重排 OPEN 表。 (9) GO LOOP。重排 OPEN 表意味着，在第(6)步中，将优先扩展哪个节点，不同的排序标准对应着不同的搜索策略。重排的原则当视具体需求而定，不同的原则对应着不同的搜索策略，如果想尽快地找到一个解，则应当将最有可能达到目标节点的那些节点排在 OPEN 表的前面部分，如果想找到代价最小的解，则应当按代价从小到大的顺序重排 OPEN 表。3-2 试举例比较各种搜索方法的效率。原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI宽度优先搜索(1) 把起始节点放到 OPEN 表中(如果该起始节点为一目标节点，则求得一个解答)。(2) 如果 OPEN 是个空表，则没有解，失败退出；否则继续。(3) 把第一个节点(节点 n)从 OPEN 表移出，并把它放入 CLOSED 扩展节点表中。(4) 扩展节点 n。如果没有后继节点，则转向上述第(2)步。(5) 把 n 的所有后继节点放到 OPEN 表的末端，并提供从这些后继节点回到 n 的指针。(6) 如果 n 的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI有界深度优先搜索(1) 把起始节点 S 放到未扩展节点 OPEN 表中。如果此节点为一目标节点，则得到一个解。(2) 如果 OPEN 为一空表，则失败退出。(3) 把第一个节点(节点 n)从 OPEN 表移到 CLOSED 表。(4) 如果节点 n 的深度等于最大深度，则转向(2)。(5) 扩展节点 n，产生其全部后裔，并把它们放入 OPEN 表的前头。如果没有后裔，则转向(2)。(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI等代价搜索方法以 g(i)的递增顺序扩展其节点，其算法如下：(1) 把起始节点 S 放到未扩展节点表 OPEN 中。如果此起始节点为一目标节点，则求得一个解;否则令 g(S)=0。(2) 如果 OPEN 是个空表，则没有解而失败退出。(3) 从 OPEN 表中选择一个节点 i，使其 g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点 i(要是有目标节点的话)；否则，就从中选一个作为节点 i。把节点 i 从 OPEN 表移至扩展节点表 CLOSED 中。(4) 如果节点 i 为目标节点，则求得一个解。(5) 扩展节点 i。如果没有后继节点，则转向第(2)步。(6) 对于节点 i 的每个后继节点 j，计算 g(j)=g(i)+c(i,j)，并把所有后继节点 j 放进OPEN 表。提供回到节点 i 的指针。(7) 转向第(2)步。3-3 化为子句形有哪些步骤? 请结合例子说明之。原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI任一谓词演算公式可以化成一个子句集。其变换过程由下列九个步骤组成：(1)消去蕴涵符号将蕴涵符号化为析取和否定符号(2)减少否定符号的辖域 每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律(3)对变量标准化对哑元改名以保证每个量词有其自己唯一的哑元(4)消去存在量词引入 Skolem 函数，消去存在量词如果要消去的存在量词不在任何一个全称量词的辖域内，那么我们就用不含变量的 Skolem函数即常量。(5)化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形 = (前缀) (母式) 前缀 = 全称量词串母式 = 无量词公式(6)把母式化为合取范式反复应用分配律，将母式写成许多合取项的合取的形式，而每一个合取项是一些谓词公式和(或) 谓词公式的否定的析取(7)消去全称量词消去前缀，即消去明显出现的全称量词(8)消去连词符号(合取)用合取项 1,合取项 2替换明显出现的合取符号(9)更换变量名称更换变量符号的名称，使一个变量符号不出现在一个以上的子句中3-4 如何通过消解反演求取问题的答案?给出一个公式集 S 和目标公式 L，通过反证或反演来求证目标公式 L，其证明步骤如下：(1)否定 L，得L；(2)把L 添加到 S 中去；(3)把新产生的集合L，S化成子句集；(4)应用消解原理，力图推导出一个表示矛盾的空子句 NIL。原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI3-5 什么叫合适公式?合适公式有哪些等价关系 ?合式公式的递归定义为：(1) 原子谓词公式是合式公式(2) 若 A 为合式公式，则 A 的否定也是合式公式(3) 若 A、B 都是合式公式，则 A AND B, AOR B, AB, AB 也都是合式公式(4) 若 A 是合式公式， x 为 A 中的自由变元，则(ANY x)A 和 (EXT x)A 都是合式公式(5) 只有按规则(1)(4) 求得的公式，才是合式公式等价关系有：否定之否定蕴含与与或形式的等价狄.摩根定律分配律交换律结合律逆否律否定跨越量词全称量词同与或连词量词中的哑元3-6 用宽度优先搜索求图 3.33 所示迷宫的出路。原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI图 3.33 迷宫一例第一步SAB第二步BHBC第三步HGCF最终路径为 SABCF3-7 用有界深度优先搜索方法求解图 3.34 所示八数码难题。2 8 1 2 31 6 3 8 47 5 4 7 6 5So Sg图 3-34 八数码难题按顺时针方向(上、右、下、左 )试探，尝试移动空格，将最大深度定为 5原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAIS0(So)2 81 6 37 5 4S12 8 31 67 5 4S22 8 31 6 47 5S32 8 31 6 47 5S42 8 31 47 6 5S52 31 8 47 6 5S62 31 8 47 6 52 31 8 4原始文档来自 蔡自兴 老师的人工智能课件http:/netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm仅用于学习交流 _) 请勿用于任何商业用途！ Contact me：http:/hi.baidu.com/xxAI7 6 5S71 2 38 47 6 5S8(Sg)1 2 38 47 6 53-8 应用最新的方法来表达传教士和野人问题，编写一个计算机程序，以求得安全渡过全部 6 个人的解答。提示：在应用状态空间表示和搜索方法时，可用(N m，N c)来表示状态描述，其中 Nm和 Nc 分别为传教士和野人的人数。初始状态为(3，3) ，而可能的中间状态为 (0，1)，(0，2)，(0 ，3)，(1，1)，(2 ，1)，(2 ，2)，(3，0) ，(3，1)和(3 ，2)等。3-9 试比较宽度优先搜索、有界深度优先搜索及有序搜索的搜索效率，并以实例数据加以说明。3-10 一个机器人驾驶卡车，携带包裹 (编号分别为1、2 和3)分别投递到林(LIN)、吴(WU)和胡(HU)3 家住宅处。规定了某些简单的操作符，如表示驾驶方位的 drive(x,y)和表示卸下包裹的 unload(z) ；对于每个操作符，都有一定的先决条件和结果。试说明状态空间问题求解系统如何能够应用谓词演算求得一个操作符序列，该序列能够生成一个满足 AT(#1，LIN)A