代价树如下图所示分别给出宽度优先及深度优先搜索策略-Read.doc

: .
第 3 章作业题参考答案
2. 综述图搜索的方式和策略。
答：用计算机来实现图的搜索， 有两种最基本的方式： 树式搜索和线 式搜索。
树式搜索就是在搜索过程中记录所经过的所有节点和边。
线式搜索就是在搜索过程中只记录那些当前认为是处在所 找路径上的节点和边。 线式搜索的基本方式又可分为不回溯和可 回溯的的两种。
图搜索的策略可分为：盲目搜索和启发式搜索。
盲目搜索就是无向导的搜索。 树式盲目搜索就是穷举式搜索。 而线式盲目搜索， 对于不回溯的就是随机碰撞式搜索， 对于回溯 的则也是穷举式搜索。
启发式搜索则是利用“启发性信息”引导的搜索。启发式搜 索又可分为许多不同的策略， 如全局择优、 局部择优、最佳图搜 索等。
5. (供参考)解： 引入一个三元组 (q0,q1,q2) 来描述总状态，开状态 为 0，关状态为 1 ，全部可能的状态为 ：
Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0)
Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1)
Q6=(1,1,0) ; Q7=(1,1,1)
翻动琴键的操作抽象为改变上述状态的算子，即 F= {a, b, c}
a:把第一个琴键qO翻转一次
b:把第二个琴键q1翻转一次
c:把第三个琴键q2翻转一次
问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}>
问题的状态空间图如下页所示：从状态空间图，我们可以找到
Q5到Q7为3的两条路径，而找不到Q5到Q0为3的路径，因此, 初始状态“关、开、关”连按三次琴键后只会出现“关、关、关” 的状态。
c
(0
，0，
a
(1
，0，
0，
b
c
c，
(1，1,
：用四元组(f、w s、g)表示状态，f代表农夫，w代表狼，s
代表羊，g代表菜，其中每个元素都可为0或1，用0表示在左
岸，用1表示在右岸 。
初始状态SO: (0,0,0,0) 目标状态：(1,1,1,1)
不合法的状态：(1,0,0,*),(1,*,0,0),(0,1,1,*),(0,*,1,1)
操作集 F={P1, P2, P3, P4, Q1, Q2 Q3, Q4}
操作符
条件
动作
pl
f=0 , w=0, s 和 g 相异
f=1 , w=1
p2
f=0 , s=0,
f=1 , s=1
p3
f=0 , g=0, w和 s 相异
f=1 , g=1
qO
f=1 , s和g相异，w和
s相异
f=0
qi
f=1 , w= 1, s 和 g 相异
f=0 , w= 0
q2
f=1 , s= 1,
f=0 , s = 0
q3
f=1 , g= 1, w和 s 相异
f=0 , g= 0
方案有两种：p2 q0 p3 q2 T p2 T q0 T p2
p2^ q0 t plT q2 宀 p3^ qO^ p2
12 一棵解树由 S0,A,D,t1,t2,t3 组成；另一棵解树由 S0,B,E,t4,t5 组成。
左边的解树：按