第三章习题--搜索策略

1、 迷宫问题：迷宫问题： 分别用宽度优先、深度优先和有界深度分别用宽度优先、深度优先和有界深度搜索算法求搜索算法求AF的路径的路径,列出搜索中列出搜索中OPEN、CLOSED表的内容表的内容 。要求：深度值相同时，按字母序扩展要求：深度值相同时，按字母序扩展 有界深度有界深度dm=3A AB BC CD DI IF FE EG GA AB BC CD DI IF FE EG G节点父节深度A0OPENOPENCLOSEDCLOSED节点父节深度A AB BC CD DBA1CA1DA1A0BA1I IIB2CB2CA1E EEC2DA1G GGD2IB2EC2在在OPEN表中调整表中调整C的父指

2、针的父指针GE3在在OPEN表中调整表中调整G的父指针的父指针GD2F FFG3FG3解为：解为：A-D-G-F 宽度优先宽度优先 节点父节深度A0OPENOPENCLOSEDCLOSED节点父节深度BA1A0BA1CA1DA1A AB BC CD DI IF FE EG GA AB BC CD DI I深度优先深度优先 节点父节深度A0OPENOPENCLOSEDCLOSED节点父节深度BA1A0BA1CA1DA1IB2CB2IB2CA1A AB BC CD DI IF FE EG GA AB BC CD DI I深度优先深度优先 E E节点父节深度A0OPENOPENCLOSEDCLOSE

3、D节点父节深度BA1A0BA1CA1DA1IB2CB2IB2CA1EC2EC2A AB BC CD DI IF FE EG GA AB BC CD DI I深度优先深度优先 E EG G节点父节深度A0OPENOPENCLOSEDCLOSED节点父节深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2DA1GE3A AB BC CD DI IF FE EG GA AB BC CD DI I深度优先深度优先 E EG GF F节点父节深度A0OPENOPENCLOSEDCLOSED节点父节深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2FG4GE3DA1FG4

4、A AB BC CD DI IF FE EG GA AB BC CD DI I深度优先深度优先 E EG GF F解为：解为：A-C-E-G-F A AB BC CD DI IF FE EG GOPENOPENCLOSEDCLOSEDA AB BC CD DI IE EG G在在CLOSED表中调整表中调整G的父指针的父指针F F解为：解为：A-D-G-F 有界深度优先有界深度优先 节点父节深度A0节点父节深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2GE3DA1DA1GD2FG3GD2FG3设有如下结构的移动将牌游戏：设有如下结构的移动将牌游戏：其中，其中，B表示黑色将

5、牌，表示黑色将牌，W表是白色将牌，表是白色将牌，E表示空格。游戏的表示空格。游戏的规定走法是：规定走法是： (1) 任意一个将牌可移入相邻的空格，规定其代价为任意一个将牌可移入相邻的空格，规定其代价为1； (2) 任何一个将牌可相隔任何一个将牌可相隔1个其它的将牌跳入空格，其代价为个其它的将牌跳入空格，其代价为跳过将牌的数目加跳过将牌的数目加1。 游戏要达到的目标是把所有游戏要达到的目标是把所有W都移到都移到B的左边。对这个问题，的左边。对这个问题，请定义一个启发函数请定义一个启发函数h(n)，并给出用这个启发函数产生的搜索，并给出用这个启发函数产生的搜索树。树。BBW W E解：启发函数解：

6、启发函数h(n)=每个每个w左边左边B的个数，的个数，f(n)=d(n)+3*h(n)W可以移到可以移到B右边的三种情况：右边的三种情况：EBWBW E代价：2代价：2BEW代价：3B B W W EB B W E WB B EW Wf=0+3*4=12f=1+3*4=13f=1+3*4=13B E W B Wf=2+3*3=11B B EW Wf=2+3*4=14EB W B Wf=3+3*3=12W B EB Wf=4+3*2=10W B W B Ef=5+3*1=8W B W E Bf=6+3*1=9W E W B Bf=7+0=72.设有如图所示与或树，请设有如图所示与或树，请分别用与

7、或树的广度优分别用与或树的广度优先和深度优先搜索求出先和深度优先搜索求出解树。解树。BCt1t2t3t4t5ADBt1t2A解：（解：（1）与）与/或树的广度优先搜索或树的广度优先搜索先扩展节点先扩展节点A,得到节点得到节点B和和C，再扩展节点，再扩展节点B,得节点得节点t1、t2，因为，因为t1、t2为可解节点，故节点为可解节点，故节点B可解，从而可节点可解，从而可节点A可解。可解。所以求得解树为：所以求得解树为：Ct3t4t5AD（2）与）与/或树的深度优先搜索或树的深度优先搜索先扩展节点先扩展节点A, 得到节点得到节点B和和C,再扩展节点再扩展节点C, 得节点得节点D和和t5,t5为可解

8、节点，再扩展节为可解节点，再扩展节D，得节点，得节点t3、t4，因为，因为t3、t4为可解为可解节点，故节点节点，故节点D可解，因为节点可解，因为节点D和和t5可解，故节点可解，故节点C可解，可解，从而可节点从而可节点A可解。可解。所以求得解树为：所以求得解树为：3.设有如图所示与或树，分设有如图所示与或树，分别用和代价法、最大代别用和代价法、最大代价法求解树的代价。价法求解树的代价。ABCDt2t3t4t156217223E若按和代价法，则该解树的代价为：若按和代价法，则该解树的代价为： h(A)=2+3+2+5+2+1+6=21h(A)=2+3+2+5+2+1+6=21若按最大代价法，则该

9、解树的代价为：若按最大代价法，则该解树的代价为： h(A)=maxh(B)+5, h(C)+6 = max(h(E)+2)+5, h(C)+6h(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(max(2, 3)+2)+5, max(2, 1)+6=max(5+5, 2+6)=10=max(5+5, 2+6)=10设有如图博弈树，其中最下面的数字是假设的估值，（设有如图博弈树，其中最下面的数字是假设的估值，（1）计算各节点的倒推值；计算各节点的倒推值；（2）利用）利用-剪枝

10、技术剪去不必要的分枝剪枝技术剪去不必要的分枝05-3336-2568-3GHCDAM9NBS0IJEF34-30KL0 0 0 -3-30 03 330剪枝剪枝剪枝剪枝4 4 -3剪枝剪枝-34 46 6剪枝剪枝6441 1、已知下列事实：、已知下列事实：（1 1）超市（）超市（SupermarketSupermarket）卖（）卖（SailSail）的商品）的商品(Goods)(Goods)便宜便宜(Cheap)(Cheap)。 （2 2）王（）王（WangWang）买（）买（BuyBuy）需要的（）需要的（WantWant）便宜商品。）便宜商品。 （3 3）自行车（）自行车（Bicycle

11、Bicycle）是商品且超市卖自行车。）是商品且超市卖自行车。 （4 4）王需要自行车。）王需要自行车。 （5 5）赵（）赵（ZhaoZhao）跟随王买同样的商品。）跟随王买同样的商品。 请应用归结反演证明方法回答以下问题：请应用归结反演证明方法回答以下问题： （1 1）王买自行车吗？）王买自行车吗？ （2 2）赵买什么商品？）赵买什么商品？定义谓词定义谓词Goods(x): xGoods(x): x是商品是商品Cheap(x)Cheap(x)：x x便宜便宜Sail(super,x)Sail(super,x)：超市卖：超市卖x xBuy(x,y)Buy(x,y)：x x买买y yWant(x

12、,y) Want(x,y) ：x x需要需要y y用谓词写事实、规则用谓词写事实、规则超市（超市（SupermarketSupermarket）卖（）卖（SailSail）的商品）的商品(Goods)(Goods)便宜便宜(Cheap)(Cheap)：( ( x)(x)( Sail(super Sail(super，x) x) Goods(x) Goods(x) Cheap(x) Cheap(x) )王（王（WangWang）买（）买（BuyBuy）需要的（）需要的（WantWant）便宜商品：）便宜商品：( ( x)(x)( Want(Wang Want(Wang，x) x) cheap(x

13、) cheap(x) Buy(Wang Buy(Wang，x)x)自行车（自行车（BicycleBicycle）是商品且超市卖自行车：）是商品且超市卖自行车：GoodsGoods（bikebike） Sail(superSail(super，bike)bike)王需要自行车：王需要自行车：WantWant（WangWang，bikebike）赵（赵（ZhaoZhao）跟随王买同样的商品：）跟随王买同样的商品：( ( x)(x)( Goods(x) Goods(x) Buy(WangBuy(Wang，x)x) Buy(Zhao Buy(Zhao，x)x)Q1Q1：Buy(WangBuy(Wang

14、，bike)bike)Q1Q1：Buy(WangBuy(Wang，bike)bike)Q2Q2：Buy(ZhaoBuy(Zhao，a) a) 构造其重言式：构造其重言式：Q2Q2Q2: Buy(ZhaoQ2: Buy(Zhao，a) a) Buy(ZhaoBuy(Zhao，a)a)2 2、已知下列事实：、已知下列事实：凡是容易的课程小李（凡是容易的课程小李（LiLi）都喜欢；）都喜欢；C C班的课程都是容易的；班的课程都是容易的；dsds是是C C班的一门课程。班的一门课程。证明：小李喜欢证明：小李喜欢dsds这门课程。这门课程。首先定义谓词：首先定义谓词： Easy(x) Easy(x) 表

15、示表示x x是容易的；是容易的；Like(x,y) Like(x,y) 表示表示x x喜欢喜欢y y；C(x) C(x) 表示表示x x是是C C班的一门课程；班的一门课程；用定义的谓词将已知事实和结论表示为谓词形式：用定义的谓词将已知事实和结论表示为谓词形式： ( ( x)(Easy(x)x)(Easy(x)Like(Li,x)Like(Li,x)；( ( x)(C(x)x)(C(x)Easy(x)Easy(x)；C(ds);C(ds);Q Q：Like(Li,ds)Like(Li,ds)3 3、某公司招聘工作人员，、某公司招聘工作人员，A A，B B，C C三人应试。面试后，公司表示如下意见：三人应试。面试后，公司表示如下意见： （1 1）三人中至少录用一人；）三人中至少录用一人；（2 2）如果录用）如果录用A A而不录用而不录用B B，则一定录用，则一定录用C C；（3 3）如果录用）如果录用B B，则一定录用，则一定录用C C；求证：公司一定录用求证：公司一定录用C C。定义谓词：定义谓词：accept (x)accept (x)：录用：录用x x 表示已知事实：表示已知事实： （1 1）三人中至少录用一人；）三人中至少录用一人； accept (A) accept (A) accept (