搜索深度优先剪枝PPT课件.ppt

,教学目标深度优先搜索的一般步骤如何剪枝如何编程内容要点复杂问题如何切入化简思维深度优先搜索的一般步骤写好递归程序,1,任务：登山人选问题攀登一座高山，假定匀速前进，从山脚登到山顶需走N天，下山也需N天。山上没有水和食品，给养要靠登山队员携带，而每个队员所携带的给养量要少于他登顶再返回山脚所消耗的给养量。因此，一定要组成一个登山队，在多人支援的情况下，保证有一个人登顶。现在登山俱乐部有P个人待选，我们将P个人依次编号为k=1,2,P，令Ek表示编号为k的人每日消耗的给养量，Mk表示编号为k的人最多可携带的给养量。登山计划要求所组成的登山队所有成员同时出发，其中一些人分别在启程若干天后返回，最终保证出发N天后至少有一人登顶，出发2N天后所有人都已返回山脚，无人滞留山上。,2,编程要求：用键盘输入天数N（NNP;for(inti=1;iEi;for(inti=1;iMi;,27,定义递归函数Search(intk,intdayUse)其中k表示要挑选登山队伍中的第k个人，dayUse表示目前队伍每天消耗的给养量。为了记录目前哪些人已被选入登山队伍中，我们用一个数组intwhoMAXP来记录，而数组元素的下标正好可以表示搜索树中的层数，即表示该队员是登顶者还是第几号支援者。Search函数可以实现如下：,28,voidSearch(intk,intdayUse)if(kP)return;/所有人均已入选，递归终止for(inti=1;i=minNeed)/所需太多continue;/换人再试（剪枝）takek=takek-1+Mi;,30,if(needk=takek)/组队完成，更新最优解/ifminNeed=needk;minP=k;takek=needk;/最后一人不必满负荷for(intj=1;jp;coutclubi.need;/forcoutclubi.take;clubi.t=(float)clubi.take/(float)clubi.need;/for,42,voidsort()/排序（对俱乐部的人，按独行天数从大到小排序）for(j=1;jclubi.t)q=clubi+1;clubi+1=clubi;clubi=q;,43,intcm(inta,intb)/向上取整函数if(a%b=0)returna/b;elsereturn(a/b)+1;,44,voiddisplay(intk1)/输出函数cout登山人数为k1,最小消耗为mimneedendl;for(i=1;i=k1;i+)cout入队者的号为listi.No登高为listi.hhkneed)/k个人所带已大于所需kd=0;/置所差为0elsekd=kneed-ktake;/计算k个人所差,47,intknd=0;/计算入队的k个人每日的消耗总和for(intm=1;m=k;m+)knd=clubm.need+knd;kh=cm(kd,knd);/计算对入队的k个人的支援高度,48,listk.No=clubi.No;/记第k个入队者的编号listk.hh=h;/记第k个入队者的支援高度if(kh=0)/不需支援了，队已组成/ifkhif(kneedmimneed)/如果k个人所需小于前次mimneed=kneed;/更新最小消耗值kk=k;/入队人数/ifkh,49,elseSe