搜索深度优先剪枝

1教学目标深度优先搜索的一般步骤如何剪枝如何编程内容要点复杂问题如何切入化简思维深度优先搜索的一般步骤写好递归程序2任务：登山人选问题攀登一座高山，假定匀速前进，从山脚登到山顶需走N天，下山也需N天。山上没有水和食品，给养要靠登山队员携带，而每个队员所携带的给养量要少于他登顶再返回山脚所消耗的给养量。因此，一定要组成一个登山队，在多人支援的情况下，保证有一个人登顶。现在登山俱乐部有P个人待选，我们将P个人依次编号为k=1,2,…,P，令E[k]表示编号为k的人每日消耗的给养量，M[k]表示编号为k的人最多可携带的给养量。登山计划要求所组成的登山队所有成员同时出发，其中一些人分别在启程若干天后返回，最终保证出发N天后至少有一人登顶，出发2N天后所有人都已返回山脚，无人滞留山上。3编程要求：用键盘输入天数N（N10）、俱乐部人数P（P10）之后，依次输入E[k]和M[k]，k=1,2,…,P，分别输出两个登山组队计划，计划1，要求参加登山的人数最少，在满足这一条件之下消耗的总给养量最少。计划2，要求消耗的总给养量最少。输出的内容是：有多少队员参加登山，消耗的总给养量，在出发时每人分别携带多少给养，每人分别在出发几天后返回（几天后开始下山）。题目数据保证有解。【输入格式】第1行为2个小于10的整数N和P,两个整数之间有一个空格。第2行为P个整数，分别是E[1],E[2],…,E[P],相邻两整数之间有一个空格。第3行为P个整数，分别是M[1],M[2],…,M[P],相邻两整数之间有一个空格。4【输出格式】第1行到第3行为计划1的内容，第1行有两个整数，前者是参加登山人数Q1，后者是消耗的总给养量。第2行是Q1个整数，表示Q1个人在出发时每人携带的给养。第3行是Q1个整数，表示Q1个人中的每个人在出发几天后返回。第4行到第6行为计划2的内容，第4行有两个整数，前者是参加登山人数Q2，后者是消耗的总给养量。第5行是Q2个整数，表示Q2个人在出发时每人携带的给养。第6行是Q2个整数，表示Q2个人中的每个人在出发几天后返回。5【输入样例】661222337817182225【输出样例】24218246333818173631输出表明：计划1中有2个人组队，分别携带18和24的给养量，分别在出发6天和3天之后返回；计划2中有3个人组队，分别携带18、17和3的给养量，分别在出发后6天、3天和1天之后返回。6《登山人选》解题思路当我们遇到一道难题时，先要想到：一、可不可以先从一个较简单的情况分析起，把难度先降低一些，等从中总结出规律性的认识后，再回到原题的要求上来；二、能不能先从一个特殊的例子分析起，再推广到一般情况。为了简化问题，理出思路，可先将问题化简为：每人所能携带的给养量相同，且每人每天消耗的给养量也相同，选择一座不高的山，用一组人数不多的具体数据。比如有如下一组数据：N=4从山脚到山顶需4天路程P=6登山俱乐部成员人数E=1每人每天消耗的给养量M=5每人最多携带的给养量7为了便于分析，图1画出了用上述数据组队登山的思路图。4下返回高度11山3321222231323311上41424344山001号队员2号队员3号队员4号队员81#2#3#的支援点h1#2#的支援点1#的支援点432211430012345678t4人登山的高度与时间图9在图中，山高是以（路程）天为单位的。山顶的高度是4天的路程。在1号队员上下山的示意图中，每个方块代表一天的路程，1号队员被选中为登顶者，用4天路程上山，再用4天路程下山。如果完全自食其力的话，1号队员需要自带8天的给养，而题目限定的每人最多携带给养量M=5。因此，没有同伴支援的话，1号队员是无法登顶的。从1号登顶后能安全下山考虑，下山只有他一个人，只能自己携带给养。因此，在做计划时让1号队员上山时，从山脚（高度0）到高度3使用同伴的给养。过了高度3之后再吃自带的给养。在图中小方块内所填的数字，表示在这一天的路程中由该号队员供应给养。从图可见1号队员上山的第一天（从高度0至高度1）由4号队员提供给养；上山的第2天（从高度1至高度2）由3号队员提供给养；上山的第3天（从高度2至高度3）由2号队员提供给养；上山的第4天（从高度3至高度4）吃自己的给养；登顶成功之后，下山的4天也均自食其力。从1号队员登顶的过程需要2号队员支援的情况看，1号队员需要在第3天吃2号队员携带的给养，这就意味着2号队员要跟1号一起爬到高度3之后才能下山。10因此，2号队员上山走3天，再下山走3天，自己要消耗6天的给养，可是自己只能携带5天的给养，当然还需要3号支援他。可以这样计划：2号队员上山时，第1天由4号队员供给；第2天由3号队员供给；第3天将1份给养支援给1号队员，自己用掉1份给养。到了高度3之后，用还剩下的3份给养安全下山。同理，在计划3号队员的行程时，要考虑1号和2号队员的情况：1号和2号队员都需要在第2天得到3号队员的支援，因此只需3号队员上山走2天，下山走2天。3号队员上山的第1天使用4号队员支援给他的给养；在第2天，3号队员将自己携带的给养1份给1号队员，另1份给2号队员，自己消耗1份；走到高度2后，带着2份给养下山，走2天回到山脚。同理，计划4号队员的行程时，考虑前3个队员需他支援的时间，都是在上山的第1天。因此，4号队员只需跟着大家走1天上山，然后独自再走1天下山。11定义Hk为队友需对第k号队员支援的高度，对1号队员，H1=3；对2号队员，H2=2；对3号队员，H3=1；4号队员不需他人支援，H4=0。令need(k)表示k个人登山，保证1人登顶所需给养；令take(k)表示k个人登山共携带的给养；令d(k)表示k个人一共差多少给养。还是用图１的情况来说明上述参数的计算方法。k=1，让１号队员独自一人登山need(1)=2*N=2*4=8take(1)=M=5d(1)=need(1)–take(1)=8–5=3１号队员如果单枪匹马登顶，缺3天给养，因此需别人支援，要计算需队友支援的高度H1=d(1)/1=312k=2，让1号队员与2号队员携手登山，2号队员只需上到H1高度，故need(2)=need(1)+2*H1=8+2*3=14take(2)=2*M=2*5=10d(2)=need(2)–take(2)=14–10=4两个人登山共缺4份给养，分属两人，每人缺2天，故需队友支援的高度为H2=d(2)/2=4/2=2k=3，让1号、2号和3号队员一起登山，3号队员只需上到H2高度need(3)=need(2)+2*H2=14+2*2=18take(3)=3*M=3*5=15d(3)=need(3)–take(3)=18–15=313三个人登山共缺3份给养，分属三人，每人缺1天，故需队员支援的高度为H3=d(3)/3=1k=4，让1号、2号、3号和4号组队登山，4号队员只需上到H3高度need(4)=need(3)+2*H3=18+2*1=20take(4)=4*M=20d(4)=need(4)–take(4)=20–20=0说明四人一起登山所需和所用相等，可以保证一人登顶，其他人也可安全返回。我们可以将上述计算数据归纳成表1。14表1登山者k个人所需k个人所带k个人所差对k个人需kneed(k)take(k)d(k)支援高度11#853321#2#14104231#2#1815313#41#2#2020003#4#15以上是简单情况下的解题思路，由于每个队员的携带量与消耗量相同，所以实际上计算的是给养如何分配。现在将难度加大到题目的要求，即要考虑每个队员的携带量与消耗量各不相同的情况。沿用前面的思路，现在需要明确区分谁是登顶者？谁第一支援？谁第二支援？……16在前面登山计划的计算过程中，当挑选第k个人作为支援者时，认为他的登山高度为Hk-1，并计算下一个支援者的登山高度为Hk，算法隐含着Hk-1≥Hk。因为计算过程中认为第k个人的总消耗量为2*Hk-1*Ek，如果Hk-1＜Hk的话，队伍的总消耗量计算就不正确，从而迭代计算得到的支援高度也不正确。若第k个人刚巧独立登至Hk-1并消耗完自带给养，则前面的迭代计算将得到Hk-1＝Hk，虽然实际上没有起到支援的作用，但迭代过程的计算还是正确的。因此，在已知需支援高度为H时，并不是任选一名队员都可作为支援者的，支援者应保证H*E＜M。17可以采用深度优先策略来搜索可能的组队计划。题目要求输出不同条件下的最优解，所以在实际搜索过程中，不一定要枚举所有可能的登山组队情况。例如在搜索给养总消耗量最小的组队计划时，若挑选某队员进行支援，发现因此计算得到的队伍给养总消耗量已经大于之前某个成功登顶计划的总消耗量，那就不用再枚举之后的支援者了。18表2给出了题目示例数据下给养消耗总量最小的登山计划的部分计算过程，相应的搜索树如图2所示。在图2中，搜索树的根结点是虚设的，视作第0层；第1层结点表示登顶者；第2层结点表示第一支援；第3层结点表示第二支援；……表2和图2中，红色表示该队员无法提供支援，绿色表示找到一个当前的最优解，粉红色表示搜索至该队员时进行剪枝。19【输入样例】66山高为6（天的路程）1222337817182225队员每日消耗给养自带给养1#172#283#2174#2185#3226#32520登山者k人需k个人带k人差对k人需kneed(k)take(k)d(k)支援高度说明11#1275521#2#2#走不到高度521#3#32248331#3#2#443212341#3#5650612#4#5人组队51#3#2#626200总消耗624#5#21k登山者need(k)take(k)d(k)支援高度说明51#3#2#不小于624#6#62剪枝41#3#62不小于622#5#剪枝41#3#62不小于622#6#剪枝31#3#4#44422141#3#4#4848004人组队2#总消耗4822k登山者need(k)take(k)d(k)支援高度说明41#3#4#2#4848004841#3#4#5#50剪枝41#3#4#6#50剪枝41#3#5#50剪枝41#3#6#50剪枝41#3#4#5#50剪枝21#4#32257331#4#2#443311341#4#2#3#56剪枝41#4#2#5#62剪枝41#4#2#6#62剪枝23k登山者need(k)take(k)d(k)支援高度说明31#4#3#44422141#4#3#5#50剪枝41#4#3#6#50剪枝31#4#5#50剪枝31#4#6#50剪枝240登顶者12123456不可能第1支援232332456第2支援442444562356505044445050第3支援456566262256356356485050566262485050第4支援56626225我们可以用递归来实现深度搜索。以搜索给养总消耗量最小的登山计划为例，为了实现上述迭代计算过程，需要定义need、take和H数组，分别表示前k个人的登山给养总需求量、总携带量和需支援的高度，同时定义minNeed、minP、minTake和minH分别表示成功的组队计划中最小给养总消耗量、组队人数、每人携带量和每人登山高度，以便保存当前最优解用于剪枝，如下所示：26constintMAXP=10;intN,P,E[MAXP],M[MAXP];intneed[MAXP]={0},take[MAXP]={0}，H[MAXP]={0};intminNeed=-1,minP=0,minTake[MAXP]={0},minH[MAXP]={0};27读数据，可用以下函数实现（为了与前面的计算过程一致，我们让数据从数组下标1开始）：voidReadData(){cinNP;for(inti=1;i=P;i++)cinE[i];for(inti=1;i=P;i++)cinM[i];}28定义递归函数Search(intk,intdayUse)其中k表示要挑选登山队伍中的第k个人，dayU