《人工智能及其应用》（蔡自兴）课后习题答案第3章

第三章 搜索推理技术

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.http://m.wodefanwen.com//xxAI

原始文档来自 蔡自兴 老师的《人工智能》课件

http://netclass.csu.edu.cn/jpkc2003/rengongzhineng/rengongzhineng/kechengxiti.htm 仅用于学习交流 ^_)^ 请勿用于任何商业用途！ Contact me：http://hi.http://m.wodefanwen.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.http://m.wodefanwen.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.http://m.wodefanwen.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.http://m.wodefanwen.com//xxAI

本文来源：https://www.bwwdw.com/article/lwn2.html