第3章-图搜索与问题求解作业讲解9页.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)