第三章习题--搜索策略.ppt

1、迷宫问题： 分别用宽度优先、深度优先和有界深度搜索算法求AF的路径,列出搜索中OPEN、CLOSED表的内容 。 要求：深度值相同时，按字母序扩展 有界深度dm=3,I,E,G,OPEN,CLOSED,A,在OPEN表中调整C的父指针,在OPEN表中调整G的父指针,解为：A-D-G-F,宽度优先,OPEN,CLOSED,I,F,E,G,A,深度优先,OPEN,CLOSED,I,F,E,G,A,深度优先,OPEN,CLOSED,I,F,E,G,A,深度优先,OPEN,CLOSED,I,F,E,G,A,深度优先,OPEN,CLOSED,I,F,E,G,A,深度优先,解为：A-C-E-G-F,I,F

2、,E,G,OPEN,CLOSED,A,B,C,D,I,E,G,在CLOSED表中调整G的父指针,解为：A-D-G-F,有界深度优先,设有如下结构的移动将牌游戏： 其中，B表示黑色将牌，W表是白色将牌，E表示空格。游戏的规定走法是： (1) 任意一个将牌可移入相邻的空格，规定其代价为1； (2) 任何一个将牌可相隔1个其它的将牌跳入空格，其代价为跳过将牌的数目加1。 游戏要达到的目标是把所有W都移到B的左边。对这个问题，请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索树。,解：启发函数h(n)=每个w左边B的个数，f(n)=d(n)+3*h(n) W可以移到B右边的三种情况：,代价：2

3、,代价：2,代价：3,f=0+3*4=12,f=1+3*4=13,f=1+3*4=13,f=2+3*3=11,f=2+3*4=14,f=3+3*3=12,f=4+3*2=10,f=5+3*1=8,f=6+3*1=9,f=7+0=7,2.设有如图所示与或树，请分别用与或树的广度优先和深度优先搜索求出解树。,解：（1）与/或树的广度优先搜索 先扩展节点A,得到节点B和C，再扩展节点B,得节点t1、t2，因为t1、t2为可解节点，故节点B可解，从而可节点A可解。 所以求得解树为：,（2）与/或树的深度优先搜索 先扩展节点A, 得到节点B和C,再扩展节点C, 得节点D和t5,t5为可解节点，再扩展节D

4、，得节点t3、t4，因为t3、t4为可解节点，故节点D可解，因为节点D和t5可解，故节点C可解，从而可节点A可解。 所以求得解树为：,3.设有如图所示与或树，分别用和代价法、最大代价法求解树的代价。,若按和代价法，则该解树的代价为： h(A)=2+3+2+5+2+1+6=21 若按最大代价法，则该解树的代价为： h(A)=maxh(B)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6 = max(max(2, 3)+2)+5, max(2, 1)+6 =max(5+5, 2+6)=10,设有如图博弈树，其中最下面的数字是假设的估值，（1）计算各节点的倒推值； （2）利用-剪

5、枝技术剪去不必要的分枝,0,5,-3,3,3,6,-2,5,6,8,-3,G,H,C,D,A,M,9,N,B,S0,I,J,E,F,3,4,-3,0,K,L,0, 0, 0, -3,-3,0, 0,3, 3,3,0,剪枝,剪枝,4, 4, -3,剪枝,-3,4, 4,6, 6,剪枝,6,4,4,1、已知下列事实： （1）超市（Supermarket）卖（Sail）的商品(Goods)便宜(Cheap)。 （2）王（Wang）买（Buy）需要的（Want）便宜商品。 （3）自行车（Bicycle）是商品且超市卖自行车。 （4）王需要自行车。 （5）赵（Zhao）跟随王买同样的商品。 请应用归结反

6、演证明方法回答以下问题： （1）王买自行车吗？ （2）赵买什么商品？,定义谓词 Goods(x): x是商品 Cheap(x)：x便宜 Sail(super,x)：超市卖x Buy(x,y)：x买y Want(x,y) ：x需要y 用谓词写事实、规则 超市（Supermarket）卖（Sail）的商品(Goods)便宜(Cheap)： (x)( Sail(super，x) Goods(x) Cheap(x) 王（Wang）买（Buy）需要的（Want）便宜商品： (x)( Want(Wang，x) cheap(x) Buy(Wang，x) 自行车（Bicycle）是商品且超市卖自行车： Goo

7、ds（bike）Sail(super，bike) 王需要自行车： Want（Wang，bike） 赵（Zhao）跟随王买同样的商品： (x)( Goods(x) Buy(Wang，x) Buy(Zhao，x) Q1：Buy(Wang，bike) Q1：Buy(Wang，bike) Q2：Buy(Zhao，a) 构造其重言式：Q2Q2: Buy(Zhao，a) Buy(Zhao，a),2、已知下列事实： 凡是容易的课程小李（Li）都喜欢； C班的课程都是容易的； ds是C班的一门课程。 证明：小李喜欢ds这门课程。,首先定义谓词： Easy(x) 表示x是容易的； Like(x,y) 表示x喜欢y； C(x) 表示x是C班的一门课程； 用定义的谓词将已知事实和结论表示为谓词形式： (x)(Easy(x)Like(Li,x)； (x)(C(x)Easy(x)； C(ds); Q：Like(Li,ds),3、某公司招聘工作人员，A，B，C三人应试。面试后，公司表示如下意见： （1）三人中至少录用一人； （2）如果录用A而不录用B，则一定录用C； （3）如果录用B，则一定录用C； 求证：公司一定录用C。,定义谓词：accept (x)：录用x 表示已知事实： （1）三人中至少录用一人； accept (A) accept