第三章习题-搜索策略

迷宫问题：分别用宽度优先、深度优先和有界深度搜索算法求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）三人中至少录用一人；