第三章習題--搜索策略

1、 迷宮問題：迷宮問題： 分別用寬度優(yōu)先、深度優(yōu)先和有界深度分別用寬度優(yōu)先、深度優(yōu)先和有界深度搜索算法求搜索算法求AF的路徑的路徑,列出搜索中列出搜索中OPEN、CLOSED表的內(nèi)容表的內(nèi)容 。要求：深度值相同時，按字母序擴展要求：深度值相同時，按字母序擴展 有界深度有界深度dm=3A AB BC CD DI IF FE EG GA AB BC CD DI IF FE EG G節(jié)點父節(jié)深度A0OPENOPENCLOSEDCLOSED節(jié)點父節(jié)深度A AB BC CD DBA1CA1DA1A0BA1I IIB2CB2CA1E EEC2DA1G GGD2IB2EC2在在OPEN表中調(diào)整表中調(diào)整C的父指

2、針的父指針GE3在在OPEN表中調(diào)整表中調(diào)整G的父指針的父指針GD2F FFG3FG3解為：解為：A-D-G-F 寬度優(yōu)先寬度優(yōu)先 節(jié)點父節(jié)深度A0OPENOPENCLOSEDCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1DA1A AB BC CD DI IF FE EG GA AB BC CD DI I深度優(yōu)先深度優(yōu)先 節(jié)點父節(jié)深度A0OPENOPENCLOSEDCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1DA1IB2CB2IB2CA1A AB BC CD DI IF FE EG GA AB BC CD DI I深度優(yōu)先深度優(yōu)先 E E節(jié)點父節(jié)深度A0OPENOPENCLOSEDCLOSE

3、D節(jié)點父節(jié)深度BA1A0BA1CA1DA1IB2CB2IB2CA1EC2EC2A AB BC CD DI IF FE EG GA AB BC CD DI I深度優(yōu)先深度優(yōu)先 E EG G節(jié)點父節(jié)深度A0OPENOPENCLOSEDCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2DA1GE3A AB BC CD DI IF FE EG GA AB BC CD DI I深度優(yōu)先深度優(yōu)先 E EG GF F節(jié)點父節(jié)深度A0OPENOPENCLOSEDCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2FG4GE3DA1FG4

4、A AB BC CD DI IF FE EG GA AB BC CD DI I深度優(yōu)先深度優(yōu)先 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表中調(diào)整表中調(diào)整G的父指針的父指針F F解為：解為：A-D-G-F 有界深度優(yōu)先有界深度優(yōu)先 節(jié)點父節(jié)深度A0節(jié)點父節(jié)深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2GE3DA1DA1GD2FG3GD2FG3設(shè)有如下結(jié)構(gòu)的移動將牌游戲：設(shè)有如下結(jié)構(gòu)的移動將牌游戲：其中，其中，B表示黑色將

5、牌，表示黑色將牌，W表是白色將牌，表是白色將牌，E表示空格。游戲的表示空格。游戲的規(guī)定走法是：規(guī)定走法是： (1) 任意一個將牌可移入相鄰的空格，規(guī)定其代價為任意一個將牌可移入相鄰的空格，規(guī)定其代價為1； (2) 任何一個將牌可相隔任何一個將牌可相隔1個其它的將牌跳入空格，其代價為個其它的將牌跳入空格，其代價為跳過將牌的數(shù)目加跳過將牌的數(shù)目加1。 游戲要達到的目標是把所有游戲要達到的目標是把所有W都移到都移到B的左邊。對這個問題，的左邊。對這個問題，請定義一個啟發(fā)函數(shù)請定義一個啟發(fā)函數(shù)h(n)，并給出用這個啟發(fā)函數(shù)產(chǎn)生的搜索，并給出用這個啟發(fā)函數(shù)產(chǎn)生的搜索樹。樹。BBW W E解：啟發(fā)函數(shù)解：

6、啟發(fā)函數(shù)h(n)=每個每個w左邊左邊B的個數(shù)，的個數(shù)，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.設(shè)有如圖所示與或樹，請設(shè)有如圖所示與或樹，請分別用與

7、或樹的廣度優(yōu)分別用與或樹的廣度優(yōu)先和深度優(yōu)先搜索求出先和深度優(yōu)先搜索求出解樹。解樹。BCt1t2t3t4t5ADBt1t2A解：（解：（1）與）與/或樹的廣度優(yōu)先搜索或樹的廣度優(yōu)先搜索先擴展節(jié)點先擴展節(jié)點A,得到節(jié)點得到節(jié)點B和和C，再擴展節(jié)點，再擴展節(jié)點B,得節(jié)點得節(jié)點t1、t2，因為，因為t1、t2為可解節(jié)點，故節(jié)點為可解節(jié)點，故節(jié)點B可解，從而可節(jié)點可解，從而可節(jié)點A可解。可解。所以求得解樹為：所以求得解樹為：Ct3t4t5AD（2）與）與/或樹的深度優(yōu)先搜索或樹的深度優(yōu)先搜索先擴展節(jié)點先擴展節(jié)點A, 得到節(jié)點得到節(jié)點B和和C,再擴展節(jié)點再擴展節(jié)點C, 得節(jié)點得節(jié)點D和和t5,t5為可解

8、節(jié)點，再擴展節(jié)為可解節(jié)點，再擴展節(jié)D，得節(jié)點，得節(jié)點t3、t4，因為，因為t3、t4為可解為可解節(jié)點，故節(jié)點節(jié)點，故節(jié)點D可解，因為節(jié)點可解，因為節(jié)點D和和t5可解，故節(jié)點可解，故節(jié)點C可解，可解，從而可節(jié)點從而可節(jié)點A可解?？山狻Ｋ郧蟮媒鈽錇椋核郧蟮媒鈽錇椋?.設(shè)有如圖所示與或樹，分設(shè)有如圖所示與或樹，分別用和代價法、最大代別用和代價法、最大代價法求解樹的代價。價法求解樹的代價。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設(shè)有如圖博弈樹，其中最下面的數(shù)字是假設(shè)的估值，（設(shè)有如圖博弈樹，其中最下面的數(shù)字是假設(shè)的估值，（1）計算各節(jié)點的倒推值；計算各節(jié)點的倒推值；（2）利用）利用-剪枝

10、技術(shù)剪去不必要的分枝剪枝技術(shù)剪去不必要的分枝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）跟隨王買同樣的商品。）跟隨王買同樣的商品。 請應(yīng)用歸結(jié)反演證明方法回答以下問題：請應(yīng)用歸結(jié)反演證明方法回答以下問題： （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用謂詞寫事實、規(guī)則用謂詞寫事實、規(guī)則超市（超市（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) 構(gòu)造其重言式：構(gòu)造其重言式：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班的一門課程；班的一門課程；用定義的謂詞將已知事實和結(jié)論表示為謂詞形式：用定義的謂詞將已知事實和結(jié)論表示為謂詞形式： ( ( 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三人應(yīng)試。面試后，公司表示如下意見：三人應(yīng)試。面試后，公司表示如下意見： （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 (