2024年5月11日发(作者：thinkpad驱动官网)
习题4
4.1理解一般图搜索算法，Open表和Close表的作用是什么？举例说明对三类子节点处理
方式的差异。
解：略。
4.2对比深度优先和宽度优先的搜索方法，为何说它们都是盲目搜索方法？
解：略。
4.3简述有界深度搜索的步骤，并说明有界深度搜索与深度搜索的区别。
解：略。
4.4启发式知识对搜索的指导作用体现在哪些方面？通过其使用的评价函数，理解启发式搜
索算法A*。
解：略。
4.5说明启发式函数h(n)的强弱对搜索效率的影响；实用上，如何使图搜索更为有效？
解：略。
4.6什么是问题规约？为什么应用问题规约得到的状态空间可表示为与或图？
解：略。
4.7举例说明与或图搜索的基本概念：K-连接，根、叶、终节点，解图，解图代价，能解
节点和不能解节点。
解：略。
4.8阐述与或图启发式搜索的算法AO
*
，AO
*
的可采纳性条件是什么？为什么扩展局部解图
时，不必选择h(n)值最小的节点加以扩展？
解：略。
4.9比较搜索算法AO*和A
*
，并说明两者差异的理由。
解：略。
4.10有一农夫带一只狐狸、一只小羊和一蓝菜过河（从左岸到右岸）。假设船太小，农夫每
次只能带一样东西过河；考虑到安全，无农夫看管时，狐狸和小羊不能在一起，小羊和那蓝菜
也不能在一起。请为该问题的解决设计状态空间，并画出状态空间图。
解：过程略。状态空间图如下：
(1,1,l,1)
L(2)
(0,1,0,1)
R(0)
(1,1,0,1)
L(1) L(3)
(0,0,0,1) (0,1,0,0)
R(2)
(1,0,1,1)
L(3)
R(2)
(1,1,1,0)
L(2)
1
(0,0,1,0)
R(0)
(1,0,1,0)
L(2)
(0,0,0,0)
4.11对八数码问题S
0
和Sg （如图4.30所示）：
图4.30 八数码问题
试按宽度优先搜索和深度优先搜索方法，画出状态空间搜索树。
解：宽度优先搜索：
2
发布者：admin，转转请注明出处：http://www.yc00.com/xitong/1715384337a2609946.html
评论列表（0条）