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

《搜索深度优先剪枝ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教学目标深度优先搜索的一般步骤如何剪枝如何编程内容要点复杂问题如何切入化简思维深度优先搜索的一般步骤写好递归程序1任务：登山人选问题攀登一座高山，假定匀速前进，从山脚登到山顶需走N天，下山也需N天。山上没有水和食品，给养要靠登山队员携带，而每个队员所携带的给养量要少于他登顶再返回山脚所消耗的给养量。因此，一定要组成一个登山队，在多人支援的情况下，保证有一个人登顶。现在登山俱乐部有P个人待选，我们将P个人依次编号为k=1,2,…,P，令E[k]表示编号为k的人每日消耗的给养量，M[k]表示编号为k的人最多

2、可携带的给养量。登山计划要求所组成的登山队所有成员同时出发，其中一些人分别在启程若干天后返回，最终保证出发N天后至少有一人登顶，出发2N天后所有人都已返回山脚，无人滞留山上。2编程要求：用键盘输入天数N（N<10）、俱乐部人数P（P<10）之后，依次输入E[k]和M[k]，k=1,2,…,P，分别输出两个登山组队计划，计划1，要求参加登山的人数最少，在满足这一条件之下消耗的总给养量最少。计划2，要求消耗的总给养量最少。输出的内容是：有多少队员参加登山，消耗的总给养量，在出发时每人分别携带多少给养，每人分

3、别在出发几天后返回（几天后开始下山）。题目数据保证有解。【输入格式】第1行为2个小于10的整数N和P,两个整数之间有一个空格。第2行为P个整数，分别是E[1],E[2],…,E[P],相邻两整数之间有一个空格。第3行为P个整数，分别是M[1],M[2],…,M[P],相邻两整数之间有一个空格。3【输出格式】第1行到第3行为计划1的内容，第1行有两个整数，前者是参加登山人数Q1，后者是消耗的总给养量。第2行是Q1个整数，表示Q1个人在出发时每人携带的给养。第3行是Q1个整数，表示Q1个人中的每个人在出发几

4、天后返回。第4行到第6行为计划2的内容，第4行有两个整数，前者是参加登山人数Q2，后者是消耗的总给养量。第5行是Q2个整数，表示Q2个人在出发时每人携带的给养。第6行是Q2个整数，表示Q2个人中的每个人在出发几天后返回。4【输入样例】661222337817182225【输出样例】24218246333818173631输出表明：计划1中有2个人组队，分别携带18和24的给养量，分别在出发6天和3天之后返回；计划2中有3个人组队，分别携带18、17和3的给养量，分别在出发后6天、3天和1天之后返回。5《

5、登山人选》解题思路当我们遇到一道难题时，先要想到：一、可不可以先从一个较简单的情况分析起，把难度先降低一些，等从中总结出规律性的认识后，再回到原题的要求上来；二、能不能先从一个特殊的例子分析起，再推广到一般情况。为了简化问题，理出思路，可先将问题化简为：每人所能携带的给养量相同，且每人每天消耗的给养量也相同，选择一座不高的山，用一组人数不多的具体数据。比如有如下一组数据：N=4从山脚到山顶需4天路程P=6登山俱乐部成员人数E=1每人每天消耗的给养量M=5每人最多携带的给养量6为了便于分析，图1画出了用上

6、述数据组队登山的思路图。4下返回高度11山3321222231323311上41424344山001号队员2号队员3号队员4号队员71#2#3#的支援点h1#2#的支援点1#的支援点432211430012345678t4人登山的高度与时间图8在图中，山高是以（路程）天为单位的。山顶的高度是4天的路程。在1号队员上下山的示意图中，每个方块代表一天的路程，1号队员被选中为登顶者，用4天路程上山，再用4天路程下山。如果完全自食其力的话，1号队员需要自带8天的给养，而题目限定的每人最多携带给养量M=5。因此，

7、没有同伴支援的话，1号队员是无法登顶的。从1号登顶后能安全下山考虑，下山只有他一个人，只能自己携带给养。因此，在做计划时让1号队员上山时，从山脚（高度0）到高度3使用同伴的给养。过了高度3之后再吃自带的给养。在图中小方块内所填的数字，表示在这一天的路程中由该号队员供应给养。从图可见1号队员上山的第一天（从高度0至高度1）由4号队员提供给养；上山的第2天（从高度1至高度2）由3号队员提供给养；上山的第3天（从高度2至高度3）由2号队员提供给养；上山的第4天（从高度3至高度4）吃自己的给养；登顶成功之后，下

8、山的4天也均自食其力。从1号队员登顶的过程需要2号队员支援的情况看，1号队员需要在第3天吃2号队员携带的给养，这就意味着2号队员要跟1号一起爬到高度3之后才能下山。9因此，2号队员上山走3天，再下山走3天，自己要消耗6天的给养，可是自己只能携带5天的给养，当然还需要3号支援他。可以这样计划：2号队员上山时，第1天由4号队员供给；第2天由3号队员供给；第3天将1份给养支援给1号队员，自己用掉1份给养。到了高度3之后，用还剩下的3份给养安全下山