搜索深度优先剪枝.ppt

1,搜索，深度优先 剪枝 登山计划问题,2,教学目标 深度优先搜索的一般步骤 如何剪枝 如何编程 内容要点 复杂问题如何切入 化简思维 深度优先搜索的一般步骤 写好递归程序,3,任务：登山人选问题 攀登一座高山，假定匀速前进，从山脚登到山顶需走 N天，下山也需 N天。山上没有水和食品，给养要靠登山队员携带，而每个队员所携带的给养量要少于他登顶再返回山脚所消耗的给养量。因此，一定要组成一个登山队，在多人支援的情况下，保证有一个人登顶。 现在登山俱乐部有P个人待选，我们将P个人依次编号为 k=1, 2, , P，令Ek 表示编号为k的人每日消耗的给养量，Mk表示编号为k的人最多可携带的给养量。登山计划要求所组成的登山队所有成员同时出发，其中一些人分别在启程若干天后返回，最终保证出发N天后至少有一人登顶，出发 2N 天后所有人都已返回山脚，无人滞留山上。,4,编程要求：用键盘输入天数N（N10）、俱乐部人数P（P10）之后，依次输入Ek和Mk，k=1, 2, , P，分别输出两个登山组队计划， 计划1，要求参加登山的人数最少，在满足这一条件之下消耗的总给养量最少。 计划2，要求消耗的总给养量最少。 输出的内容是：有多少队员参加登山，消耗的总给养量，在出发时每人分别携带多少给养，每人分别在出发几天后返回（几天后开始下山）。题目数据保证有解。 【输入格式】第1行为2个小于10的整数N和P, 两个整数之间有一个空格。第2行为P个整数，分别是E1,E2,EP, 相邻两整数之间有一个空格。第3行为P个整数，分别是M1,M2,MP, 相邻两整数之间有一个空格。,5,【输出格式】第1行到第3行为计划1的内容，第1行有两个整数，前者是参加登山人数Q1，后者是消耗的总给养量。第2行是Q1个整数，表示Q1个人在出发时每人携带的给养。第3 行是Q1个整数，表示Q1个人中的每个人在出发几天后返回。第4行到第6行为计划2的内容，第4行有两个整数，前者是参加登山人数Q2，后者是消耗的总给养量。第5行是Q2个整数，表示Q2个人在出发时每人携带的给养。第6行是Q2个整数，表示Q2个人中的每个人在出发几天后返回。,6,【输入样例】 6 6 1 2 2 2 3 3 7 8 17 18 22 25 【输出样例】 2 42 18 24 6 3 3 38 18 17 3 6 3 1 输出表明： 计划1中有2个人组队，分别携带18和24的给养量，分别在出发6天和3天之后返回； 计划2中有3个人组队，分别携带18、17和3的给养量，分别在出发后6天、3天和1天之后返回。,7,登山人选解题思路 当我们遇到一道难题时，先要想到：一、可不可以先从一个较简单的情况分析起，把难度先降低一些，等从中总结出规律性的认识后，再回到原题的要求上来；二、能不能先从一个特殊的例子分析起，再推广到一般情况。 为了简化问题，理出思路，可先将问题化简为：每人所能携带的给养量相同，且每人每天消耗的给养量也相同，选择一座不高的山，用一组人数不多的具体数据。比如有如下一组数据： N = 4 从山脚到山顶需4天路程 P = 6 登山俱乐部成员人数 E = 1 每人每天消耗的给养量 M = 5 每人最多携带的给养量,8,为了便于分析，图1画出了用上述数据组队登山的思路图。 4 下 返回高度 1 1 山 3 3 2 1 2 2 2 2 3 1 3 2 3 3 1 1 上 4 1 4 2 4 3 4 4 山0 0 1号队员 2号队员 3号队员 4号队员,9,1#2#3#的支援点 h 1#2#的支援点 1#的支援点 4 3 2 2 1 1 4 3 0 0 1 2 3 4 5 6 7 8 t 4人登山的高度与时间图,10,在图中，山高是以（路程）天为单位的。山顶的高度是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之后才能下山。,11,因此，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天下山。,12,定义 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 = 8 take(1) = M = 5 d(1) = need(1) take(1) = 8 5 = 3 号队员如果单枪匹马登顶，缺3天给养， 因此需别人支援，要计算需队友支援的高度 H1 = d(1) / 1 = 3,13,k = 2，让1号队员与2号队员携手登山， 2号队员只需上到H1高度，故 need(2) = need(1) + 2 * H1 = 8 + 2 * 3 = 14 take(2) = 2 * M = 2 * 5 = 10 d(2) = need(2) take(2) = 14 10 = 4 两个人登山共缺4份给养，分属两人，每人缺2天，故需队友支援的高度为 H2 = d(2) / 2 = 4 / 2 = 2 k = 3，让1号、2号和3号队员一起登山， 3号队员只需上到H2高度 need(3) = need(2) + 2 * H2 = 14 + 2 * 2 = 18 take(3) = 3 * M = 3 * 5 = 15 d(3) = need(3) take(3) = 18 15 = 3,14,三个人登山共缺3份给养，分属三人，每人缺1天，故需队员支援的高度为 H3 = d(3) / 3 = 1 k = 4，让1号、2号、3号和4号组队登山， 4号队员只需上到H3高度 need(4) = need(3) + 2 * H3 = 18 + 2 * 1 = 20 take(4) = 4 * M = 20 d(4) = need(4) take(4) = 20 20 = 0 说明四人一起登山所需和所用相等，可以保证一人登顶，其他人也可安全返回。 我们可以将上述计算数据归纳成表1。,15,表 1 登山者 k个人所需 k个人所带 k个人所差 对k个人需 k need(k) take(k) d(k) 支援高度 1 1# 8 5 3 3 2 1#2# 14 10 4 2 3 1# 2# 18 15 3 1 3# 4 1# 2# 20 20 0 0 3# 4#,16,以上是简单情况下的解题思路，由于每个队员的携带量与消耗量相同，所以实际上计算的是给养如何分配。 现在将难度加大到题目的要求，即要考虑每个队员的携带量与消耗量各不相同的情况。沿用前面的思路，现在需要明确区分谁是登顶者？谁第一支援？谁第二支援？,17,在前面登山计划的计算过程中，当挑选第k个人作为支援者时，认为他的登山高度为 Hk-1，并计算下一个支援者的登山高度为Hk，算法隐含着Hk-1Hk。因为计算过程中认为第k个人的总消耗量为2 * Hk-1* Ek， 如果Hk-1Hk的话，队伍的总消耗量计算就不正确，从而迭代计算得到的支援高度也不正确。若第k个人刚巧独立登至Hk-1并消耗完自带给养，则前面的迭代计算将得到 Hk-1Hk，虽然实际上没有起到支援的作用，但迭代过程的计算还是正确的。因此，在已知需支援高度为H时，并不是任选一名队员都可作为支援者的，支援者应保证 H * E M 。,18,可以采用深度优先策略来搜索可能的组队计划。题目要求输出不同条件下的最优解，所以在实际搜索过程中，不一定要枚举所有可能的登山组队情况。例如在搜索给养总消耗量最小的组队计划时，若挑选某队员进行支援，发现因此计算得到的队伍给养总消耗量已经大于之前某个成功登顶计划的总消耗量，那就不用再枚举之后的支援者了。,19,表2给出了题目示例数据下给养消耗总量最小的登山计划的部分计算过程，相应的搜索树如图2所示。在图2中，搜索树的根结点是虚设的，视作第0层；第1层结点表示登顶者；第2层结点表示第一支援；第3层结点表示第二支援；表2和图2中，红色表示该队员无法提供支援，绿色表示找到一个当前的最优解，粉红色表示搜索至该队员时进行剪枝。,20,【输入样例】 6 6 山高为6（天的路程） 1 2 2 2 3 3 7 8 17 18 22 25 队员 每日消耗给养 自带给养 1# 1 7 2# 2 8 3# 2 17 4# 2 18 5# 3 22 6# 3 25,21,登山者 k人需 k个人带 k人差 对k人需 k need(k) take(k) d(k) 支援高度 说明 1 1# 12 7 5 5 2 1#2# 2#走不到高度5 2 1#3# 32 24 8 3 3 1#3#2# 44 32 12 3 4 1#3# 56 50 6 1 2#4# 5人组队 5 1#3#2# 62 62 0 0 总消耗62 4#5#,22,k 登山者 need(k) take(k) d(k) 支援高度 说明 5 1#3#2# 不小于62 4#6# 62 剪枝 4 1#3# 62 不小于62 2#5# 剪枝 4 1#3# 62 不小于62 2#6# 剪枝 3 1#3#4# 44 42 2 1 4 1#3#4# 48 48 0 0 4人组队 2# 总消耗48,23,k 登山者 need(k) take(k) d(k) 支援高度 说明 4 1#3#4#2# 48 48 0 0 48 4 1#3#4#5# 50 剪枝 4 1#3#4#6# 50 剪枝 4 1#3#5# 50 剪枝 4 1#3#6# 50 剪枝 4 1#3#4#5# 50 剪枝 2 1#4# 32 25 7 3 3 1#4#2# 44 33 11 3 4 1#4#2#3# 56 剪枝 4 1#4#2#5# 62 剪枝 4 1#4#2#6# 62 剪枝,24,k 登山者 need(k) take(k) d(k) 支援高度 说明 3 1#4#3# 44 42 2 1 4 1#4#3#5# 50 剪枝 4 1#4#3#6# 50 剪枝 3 1#4#5# 50 剪枝 3 1#4#6# 50 剪枝,25,0 登顶者 12 1 2 3 4 5 6 不可能 第1支援 2 32 3 32 4 5 6 第2支援 44 2 44 4 5 6 2 3 5 6 50 50 44 44 50 50 第3支援 4 5 6 56 62 62 2 5 6 3 5 6 3 5 6 48 50 50 56 62 62 48 50 50 第4支援 5 6 62 62,26,我们可以用递归来实现深度搜索。以搜索给养总消耗量最小的登山计划为例，为了实现上述迭代计算过程，需要定义need、take和H数组，分别表示前k个人的登山给养总需求量、总携带量和需支援的高度，同时定义minNeed、minP、minTake和minH分别表示成功的组队计划中最小给养总消耗量、组队人数、每人携带量和每人登山高度，以便保存当前最优解用于剪枝，如下所示：,27,const int MAXP = 10; int N, P, EMAXP, MMAXP; int needMAXP = 0, takeMAXP = 0， HMAXP = 0; int minNeed = -1, minP = 0, minTakeMAXP = 0, minHMAXP = 0;,28,读数据，可用以下函数实现（为了与前面的计算过程一致，我们让数据从数组下标1开始）： void ReadData() cin N P; for (int i = 1; i Ei; for (int i = 1; i Mi; ,29,定义递归函数 Search(int k, int dayUse) 其中k表示要挑选登山队伍中的第k个人，dayUse表示目前队伍每天消耗的给养量。为了记录目前哪些人已被选入登山队伍中，我们用一个数组 int whoMAXP来记录，而数组元素的下标正好可以表示搜索树中的层数，即表示该队员是登顶者还是第几号支援者。 Search函数可以实现如下：,30,void Search( int k, int dayUse ) if (k P) return; / 所有人均已入选，递归终止 for ( int i = 1; i = P; i+ ) bool bSelected = false; / 预置该队员尚未入选 for ( int j = 1; j k; j+ ) if ( whoj = i ) bSelected = true; /记 该队员已入选 if ( bSelected ) / 如果该队员已入选 continue;,31,if (Hk-1 * Ei Mi) / 如果该队员无法独自登至高度Hk-1 continue; /换人再试 whok = i; / i#入选为第k个登山人 needk = needk-1 + 2 * Hk-1 * Ei; if (needk = minNeed) /所需太多 continue; /换人再试（剪枝） takek = takek-1 + Mi;,32,if (needk = takek) / 组队完成，更新最优解 /if minNeed = needk; minP = k; takek = needk; / 最后一人不必满负荷 for ( int j = 1; j = k; j+) /for j minTakej = takej - takej-1; minHj = Hj-1; /for j /if,33,else / 需要支援 / else int d = needk - takek; / 缺的给养量 int dayUseNow = dayUse + Ei; / 新的每日消耗量 int w = d / dayUseNow; / 计算新的支援高度 if (w * dayUseNow = d) / dayUseNow整除d Hk = w; else Hk = w + 1; Search(k+1, dayUseNow); / 递归搜索下一层 / else / /,34,为了正确调用Search函数，需要先初始化有关变量，使 need0 = take0 = 0; H0 = N; minNeed = (unsigned)-1; 然后调用Search(1, 0)。如果函数调用后minNeed不等于初始值，说明搜索得到组队计划，可以输出。,35,对于题目中要求的另一组队方案，即参加登山的人数最少，且在满足这一条件之下消耗的总给养量最少的组队方案，剪枝时应首先考虑当前参与登山的人数k是否大于minP，然后可再考虑needk是否大于minNeed。请读者自行完成递归函数，同时确定函数调用前该如何初始化相关变量，函数调用后如何判断搜索得到组队计划。 回顾解决这个问题的过程，在解题思路上，我们先主动降低题目难度，从简单情况入手，等到明确题目含义，并找到规律和思路后，再回到题目要求的难度，将已有思路推广和完善；在程序设计上，我们采用递归函数来实现深度搜索，同时采用分支定界的方法实现动态剪枝，从而提高搜索速度。,36,改进措施 先按独行能力排序 队员号 负载量 每天消耗 可独行天数 排序 4# 18 2 9 1 3# 17 2 8.5 2 6# 25 3 8.3 3 5# 23 3 7.3 4 1# 7 1 7 5 2# 8 2 4 6,37,4# 6#上山消耗42 4#3#1#上山消耗38 24 3 4# 24 4 3# 6# 5# 1# 2# 30 1 30 2 32 3 3# 6# 5# 1# 2# 4# 6# 5# 1# 2# 42 0 42 1 42 2 48 2 48 2 6# 5# 1# 2# 3# 6# 5# 2# 4# 6# 5# 2# 42 0 42 0 38 0 40 0 38 0 42 0 42 0 38 1 44 1 50 1 50 1 44 3,38,k 登山人 k个人所需 k个人所带 k个人所差 需支援高度 结点评价 1 4# 24 18 6 3 (24,3) 2 4#3# 36 35 1 1 (36,1) 3 4#3#6# 42 42 0 0 (42,0) 3 4#3#5# 42 42 0 0 (42,0) 3 4#3#1# 38 38 0 0 (38,0)V 3 4#3#2# 40 40 0 0 (40,0)X 2 4#6# 42 42 0 0 (42,0) V 2 4#5# 42 40 2 1 (42,1) X 2 4#1# 30 25 5 3 (30,2) 3 4#1#3# 38 38 0 0 (38,0) X 3 4#1#6# 42 42 0 0 (42,0) X 3 4#1#5# 42 42 0 0 (42,0) X 3 4#1#2# 38 33 5 2 (38,2) X,39,#include #include using namespace std; const int maxp = 10; /俱乐部人数 int mimneed=1000; /最小消耗，初始化为一个大数 int i,j; / 整数变量 int N,p; /整数变量 int kneed,ktake,kd,kh,kk; /整数变量,40,struct person /结构，描述登山俱乐部的每一个人 int No; /编号 int need; /本人每日消耗 int take; /本人的携带量 float t; /本人可独行天数 int hh; /本人支援高度 bool flag; /入选标志，初始化 为0 clubmaxp+1,q,listmaxp+1; /结构变量和结构数组,41,void sort(); /排序 void display(int); /显示输出 void Search1(int,int,int,int); /搜索组队方案（最小消耗） int cm(int,int); /求整数值 void ReadData(); /输入数据,42,int main() for(i=1;i=p;i+) /初始化 clubi.flag=0; /置未入队标志 ReadData(); /输入数据 sort(); /排序 Search1(1,0,0,N); /调用搜索函数 display(kk); /输出组队信息 return 0; ,43,void ReadData() /输入数据 cout N p; cout clubi.need; /for cout clubi.take; clubi.t=(float)clubi.tak