第三章習題-搜索策略

迷宮問題：分別用寬度優(yōu)先、深度優(yōu)先和有界深度搜索算法求A——F的路徑,列出搜索中OPEN、CLOSED表的內(nèi)容

。要求：深度值相同時，按字母序擴展有界深度dm=3 ABCDIFEGABCDIFEG節(jié)點父節(jié)深度A0OPENCLOSED節(jié)點父節(jié)深度ABCDBA1CA1DA1A0BA1IIB2CB2CA1EEC2DA1GGD2IB2EC2在OPEN表中調(diào)整C的父指針GE3在OPEN表中調(diào)整G的父指針GD2FFG3FG3解為：A-D-G-F寬度優(yōu)先節(jié)點父節(jié)深度A0OPENCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1DA1ABCDIFEGABCDI深度優(yōu)先節(jié)點父節(jié)深度A0OPENCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1DA1IB2CB2IB2CA1ABCDIFEGABCDI深度優(yōu)先E節(jié)點父節(jié)深度A0OPENCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1DA1IB2CB2IB2CA1EC2EC2ABCDIFEGABCDI深度優(yōu)先EG節(jié)點父節(jié)深度A0OPENCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2DA1GE3ABCDIFEGABCDI深度優(yōu)先EGF節(jié)點父節(jié)深度A0OPENCLOSED節(jié)點父節(jié)深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2FG4GE3DA1FG4ABCDIFEGABCDI深度優(yōu)先EGF解為：A-C-E-G-F

ABCDIFEGOPENCLOSEDABCDIEG在CLOSED表中調(diào)整G的父指針F解為：A-D-G-F有界深度優(yōu)先節(jié)點父節(jié)深度A0節(jié)點父節(jié)深度BA1A0BA1CA1GE3IB2CB2IB2CA1EC2EC2GE3DA1DA1GD2FG3GD2FG3設有如下結(jié)構(gòu)的移動將牌游戲：其中，B表示黑色將牌，W表是白色將牌，E表示空格。游戲的規(guī)定走法是：

(1)任意一個將牌可移入相鄰的空格，規(guī)定其代價為1；

(2)任何一個將牌可相隔1個其它的將牌跳入空格，其代價為跳過將牌的數(shù)目加1。游戲要達到的目標是把所有W都移到B的左邊。對這個問題，請定義一個啟發(fā)函數(shù)h(n)，并給出用這個啟發(fā)函數(shù)產(chǎn)生的搜索樹。BBWWE解：啟發(fā)函數(shù)h(n)=每個w左邊B的個數(shù)，f(n)=d(n)+3*h(n)W可以移到B右邊的三種情況：EBWBWE代價：2代價：2BEW代價：3BBWWEBBWEWBBEWWf=0+3*4=12f=1+3*4=13f=1+3*4=13BEWBWf=2+3*3=11BBEWWf=2+3*4=14EBWBWf=3+3*3=12WBEBWf=4+3*2=10WBWBEf=5+3*1=8WBWEBf=6+3*1=9WEWBBf=7+0=72.設有如圖所示與或樹，請分別用與或樹的廣度優(yōu)先和深度優(yōu)先搜索求出解樹。BCt1t2t3t4t5ADBt1t2A解：（1）與/或樹的廣度優(yōu)先搜索先擴展節(jié)點A,得到節(jié)點B和C，再擴展節(jié)點B,得節(jié)點t1、t2，因為t1、t2為可解節(jié)點，故節(jié)點B可解，從而可節(jié)點A可解。所以求得解樹為：Ct3t4t5AD（2）與/或樹的深度優(yōu)先搜索先擴展節(jié)點A,得到節(jié)點B和C,再擴展節(jié)點C,得節(jié)點D和t5,t5為可解節(jié)點，再擴展節(jié)D，得節(jié)點t3、t4，因為t3、t4為可解節(jié)點，故節(jié)點D可解，因為節(jié)點D和t5可解，故節(jié)點C可解，從而可節(jié)點A可解。所以求得解樹為：3.設有如圖所示與或樹，分別用和代價法、最大代價法求解樹的代價。ABCDt2t3t4t156217223E若按和代價法，則該解樹的代價為：

h(A)=2+3+2+5+2+1+6=21若按最大代價法，則該解樹的代價為：

h(A)=max{h(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設有如圖博弈樹，其中最下面的數(shù)字是假設的估值，（1）計算各節(jié)點的倒推值；（2）利用α-β剪枝技術(shù)剪去不必要的分枝05-3336-2568-3GHCDAM9NBS0IJEF34-30KL0α≥0β≤0β≤-3-30α≥03α≥330α剪枝β剪枝4α≥4β≤-3α剪枝-34β≤46α≥6β剪枝6441、已知下列事實：（1）超市（Supermarket）賣（Sail）的商品(Goods)便宜(Cheap)。（2）王（Wang）買（Buy）需要的（Want）便宜商品。（3）自行車（Bicycle）是商品且超市賣自行車。（4）王需要自行車。（5）趙（Zhao）跟隨王買同樣的商品。請應用歸結(jié)反演證明方法回答以下問題：（1）王買自行車嗎？（2）趙買什么商品？定義謂詞

Goods(x):x是商品

Cheap(x)：x便宜

Sail(super,x)：超市賣x Buy(x,y)：x買y Want(x,y)：x需要y用謂詞寫事實、規(guī)則超市（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）是商品且超市賣自行車：Goods（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)構(gòu)造其重言式：Q2∨～Q2:Buy(Zhao，a)∨～Buy(Zhao，a)2、已知下列事實：凡是容易的課程小李（Li）都喜歡；C班的課程都是容易的；ds是C班的一門課程。證明：小李喜歡ds這門課程。首先定義謂詞：Easy(x)表示x是容易的；Like(x,y)表示x喜歡y；C(x)表示x是C班的一門課程；用定義的謂詞將已知事實和結(jié)論表示為謂詞形式：(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）三人中至少錄用一人；