《人工智能》之《确定性推理》习题解析

2024-02-06 17:44| 来源: 网络整理| 查看: 265

教材：《人工智能及其应用》，蔡自兴等，2016m清华大学出版社（第5版）

参考书：在这里插入图片描述

对应同系列博客：《人工智能》之《确定性推理》

《人工智能》之《确定性推理》习题解析 1 什么是图搜索过程？其中，重排OPEN表意味着什么，重排的原则是什么？2 试举例比较各种搜索方法的效率3 化为子句形有哪些步骤？请结合例子说明4 如何通过消解反演求取问题的答案？5 什么叫合式公式？合式公式有哪些等价关系？6 用宽度优先搜索求迷宫的出路7 用有界深度优先搜索方法求解八数码难题10 机器人驾驶卡车11 规则演绎系统和产生式系统有哪几种推理方式？各自的特点是什么？12 单调推理有何局限性？什么叫缺省推理？非单调推理系统如何证实一个节点的有效性？13 在什么情况下需要采用非单调推理？14 下列语句是一些几何定理，把这些语句表示为基于规则的几何证明系统的产生式规则

1 什么是图搜索过程？其中，重排OPEN表意味着什么，重排的原则是什么？

图搜索过程如下：

建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未拓展节点表中。建立一个叫做CLOSED的已拓展节点表，初始化为空表。LOOP：若OPEN表是空表，则失败退出。选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的。扩展节点n，生成后继节点集合M。对那些未曾在G中出现过的（既未曾在OPEN表上，也未在CLOSED表上出现过的）M成员设置其父节点指针指向n并加入OPEN表。对已经在OPEN或CLOSED表中出现过的每一个M成员，确定是否需要将其原来的父节点改为n。对已在CLOSED表上的每个M成员，若修改了其父节点，则将该节点从CLOSED表中移出，重新加入OPEN表中。按某一任意方式或按某个探试值，重排OPEN表。GO LOOP。

重排OPEN表意味着，选出一个“最好”的节点在第6步进行扩展，不同的排序方式也会使图搜索过程的搜索策略不一样。

重排的原则应当视具体需求而定，不同的原则对应不同的搜索策略。一般地，重排的原则是：根据相应的图搜索策略，将“最好”的节点（即最有可能达到目标节点的节点）放在最前面。

2 试举例比较各种搜索方法的效率

这些搜索方法都大同小异，差别在于拓展节点n时，把n的所有后裔放在OPEN表的前端还是末端。

如，宽度优先搜索的框图：在这里插入图片描述

3 化为子句形有哪些步骤？请结合例子说明消去蕴涵符号将蕴涵符号转换为∨和符号，如A∨B替换A→B。减少否定符号的辖域每个否定符号最多只用到一个谓词符号上，并反复应用狄摩根定律。如用A∨B代替（A∧B），用(∃x)(A)代替(∀x)A。对变量标准化改名哑元（受量词约束的变元），保证每个量词用唯一的哑元，即不同量词约束的变元有不同的名字。如对 (∀x)(P(x)∧(∃x)Q(x)) 标准化得 (∀x)(P(x)∧(∃y)Q(y))。消去存在量词对全程量词辖域内的存在量词，以Skolem函数代替存在量词内的约束变量。对自由的存在量词，以一个新常量替代。如 ((∀y)P(g(y),y)) 代替 (∀y)(∃x)P(x,y)，其中g(y)为Skolem函数。又如 P(A) 代替 (∃x)P(x)，其中A为不含变量的Skolem函数即常量。化为前束形把所有全称量词移到公式的左边，并使每个量词的辖域包括这个量词后面公式的整个部分。前束形 = {前缀} {母式} （全称量词串）（无量词公式）把母式化为合取范式任何母式都可写成由一些谓词公式和谓词公式的否定的析取（子句）的有限集组成的合取。如 (A∨B)∧(A∨C) 代替 A∨(B∧C)。消去全称量词余下的量词均被全称量词量化了。同时全称量词的次序也不重要。因此，可以消去前缀，即消去明显出现的全称量词。消去连词符号∧ 用{A, B}代替(A∧B)，消去符号∧。最后得到一个有限子句集，其中每个公式（子句）是文字的析取。更换变量名称更换变量符号，使一个变量符号只出现在一个子句中。如P(x)∨Q(x)和P(x)∨P(y)，更换变量符号后为P(x1)∨Q(x1)和P(x2)∨P(y)。 4 如何通过消解反演求取问题的答案？给出公式集{S}和目标公式L；否定L，得到~L；把~L添加到S中；把新产生的集合{~L，S}化成子句集；应用消解原理，推导出一个表示矛盾的空子句。 5 什么叫合式公式？合式公式有哪些等价关系？

一阶逻辑中合式公式，被递归定义如下：

原子是合式公式；若A是合式公式，则()也是合式公式；若A，B是合式公式，则也是合式公式；若A是合式公式，是A中的变量符号，则也是合式公式；只有限次地使用1～4所生成的符号串才是合式公式。

等价关系有：

否定之否定、蕴含与与或形式的等价狄摩根定律分配律交换律结合律逆否律 6 用宽度优先搜索求迷宫的出路

设起点为S，搜索树为：在这里插入图片描述路径为：S→A→B→C→F