第三章習題-搜索策略

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

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

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

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

(2)任何一個將牌可相隔1個其它的將牌跳入空格，其代價為跳過將牌的數目加1。游戲要達到的目標是把所有W都移到B的左邊。對這個問題，請定義一個啟發函數h(n)，并給出用這個啟發函數產生的搜索樹。BBWWE解：啟發函數h(n)=每個w左邊B的個數，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.設有如圖所示與或樹，請分別用與或樹的廣度優先和深度優先搜索求出解樹。BCt1t2t3t4t5ADBt1t2A解：（1）與/或樹的廣度優先搜索先擴展節點A,得到節點B和C，再擴展節點B,得節點t1、t2，因為t1、t2為可解節點，故節點B可解，從而可節點A可解。所以求得解樹為：Ct3t4t5AD（2）與/或樹的深度優先搜索先擴展節點A,得到節點B和C,再擴展節點C,得節點D和t5,t5為可解節點，再擴展節D，得節點t3、t4，因為t3、t4為可解節點，故節點D可解，因為節點D和t5可解，故節點C可解，從而可節點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設有如圖博弈樹，其中最下面的數字是假設的估值，（1）計算各節點的倒推值；（2）利用α-β剪枝技術剪去不必要的分枝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）跟隨王買同樣的商品。請應用歸結反演證明方法回答以下問題：（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）是商品且超市賣自行車：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)構造其重言式：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班的一門課程；用定義的謂詞將已知事實和結論表示為謂詞形式：(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）三人中至少錄用一人；