《搜索深度优先剪枝.ppt》由会员分享，可在线阅读，更多相关《搜索深度优先剪枝.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、搜索，深度优先搜索，深度优先剪枝剪枝登山计划问题登山计划问题1 教学目标教学目标 深度优先搜索的一般步骤 如何剪枝 如何编程 内容要点内容要点 复杂问题如何切入 化简思维 深度优先搜索的一般步骤 写好递归程序 2n n任务：登山人选问题任务：登山人选问题任务：登山人选问题任务：登山人选问题n n攀登一座高山，假定匀速前进，从山脚登到山攀登一座高山，假定匀速前进，从山脚登到山顶需走顶需走 N N天，下山也需天，下山也需 N N天。山上没有水和食天。山上没有水和食品，给养要靠登山队员携带，而每个队员所携品，给养要靠登山队员携带，而每个队员所携带的给养量要少于他登顶再返回山脚所消耗的带的给养量要少于
2、他登顶再返回山脚所消耗的给养量。因此，一定要组成一个登山队，在多给养量。因此，一定要组成一个登山队，在多人支援的情况下，保证有一个人登顶。人支援的情况下，保证有一个人登顶。n n现在登山俱乐部有现在登山俱乐部有P P个人待选，我们将个人待选，我们将P P个人依个人依次编号为次编号为 k=1,2,Pk=1,2,P，令令Ek Ek 表示编号为表示编号为k k的的人每日消耗的给养量，人每日消耗的给养量，MkMk表示编号为表示编号为k k的人的人最多可携带的给养量。登山计划要求所组成的最多可携带的给养量。登山计划要求所组成的登山队所有成员同时出发，其中一些人分别在登山队所有成员同时出发，其中一些人分别
3、在启程若干天后返回，最终保证出发启程若干天后返回，最终保证出发N N天后至少天后至少有一人登顶，出发有一人登顶，出发 2N 2N 天后所有人都已返回山天后所有人都已返回山脚，无人滞留山上。脚，无人滞留山上。3 编程要求：编程要求：用键盘输入天数用键盘输入天数N N（N10N10）、）、俱乐部人俱乐部人数数P P（P10P N P;cin N P;for(int i=1;i=P;i+)for(int i=1;i Ei;cin Ei;for(int i=1;i=P;i+)for(int i=1;i Mi;cin Mi;28 定义递归函数 Search(int k,int dayUse)其中k表示要
4、挑选登山队伍中的第k个人，dayUse表示目前队伍每天消耗的给养量。为了记录目前哪些人已被选入登山队伍中，我们用一个数组 int whoMAXP来记录，而数组元素的下标正好可以表示搜索树中的层数，即表示该队员是登顶者还是第几号支援者。Search函数可以实现如下：29 void Search(int k,int dayUse)void Search(int k,int dayUse)if(k P)return;/if(k P)return;/所有人均已入选，递归终止所有人均已入选，递归终止所有人均已入选，递归终止所有人均已入选，递归终止 for(int i=1;i=P;i+)for(int i
5、=1;i=P;i+)bool bSelected=false;/bool bSelected=false;/预置该队员尚未入选预置该队员尚未入选预置该队员尚未入选预置该队员尚未入选for(int j=1;j k;j+)for(int j=1;j Mi)/如果该队员无法独自登至高度如果该队员无法独自登至高度Hk-1 continue;/换人再试换人再试whok=i;/i#入选为第入选为第k个登山人个登山人needk=needk-1+2*Hk-1*Ei;if(needk=minNeed)/所需太多所需太多 continue;/换人再试（剪枝）换人再试（剪枝）takek=takek-1+Mi;31
6、if(needk=takek)if(needk=takek)/组队完成，更新最优解组队完成，更新最优解组队完成，更新最优解组队完成，更新最优解 /if /ifminNeed=needk;minNeed=needk;minP=k;minP=k;takek=needk;takek=needk;/最后一人不必满负荷最后一人不必满负荷最后一人不必满负荷最后一人不必满负荷for(int j=1;j=k;j+)for(int j=1;j=k;j+)/for j /for j minTakej=takej-takej-1;minTakej=takej-takej-1;minHj=Hj-1;minHj=Hj-
7、1;/for j /for j /if /if32 elseelse/需要支援需要支援需要支援需要支援/else/else int d=needk-takek;/int d=needk-takek;/缺的给养量缺的给养量缺的给养量缺的给养量 int dayUseNow=dayUse+Ei;int dayUseNow=dayUse+Ei;/新的每日消耗量新的每日消耗量新的每日消耗量新的每日消耗量 int w=d/dayUseNow;int w=d/dayUseNow;/计算新的支援高度计算新的支援高度计算新的支援高度计算新的支援高度 if(w*dayUseNow=d)if(w*dayUseNow
8、=d)/dayUseNow/dayUseNow整除整除整除整除d dHk=w;Hk=w;else elseHk=w+1;Hk=w+1;Search(k+1,dayUseNow);Search(k+1,dayUseNow);/递归搜索下一层递归搜索下一层递归搜索下一层递归搜索下一层 /else/else /33 为了正确调用Search函数，需要先初始化有关变量，使 need0=take0=0;H0=N;minNeed=(unsigned)-1;然后调用Search(1,0)。如果函数调用后minNeed不等于初始值，说明搜索得到组队计划，可以输出。34n n对于题目中要求的另一组队方案，即参加
9、登山对于题目中要求的另一组队方案，即参加登山的人数最少，且在满足这一条件之下消耗的总的人数最少，且在满足这一条件之下消耗的总给养量最少的组队方案，剪枝时应首先考虑当给养量最少的组队方案，剪枝时应首先考虑当前参与登山的人数前参与登山的人数k k是否大于是否大于minPminP，然后可再，然后可再考虑考虑needkneedk是否大于是否大于minNeedminNeed。请读者自行完。请读者自行完成递归函数，同时确定函数调用前该如何初始成递归函数，同时确定函数调用前该如何初始化相关变量，函数调用后如何判断搜索得到组化相关变量，函数调用后如何判断搜索得到组队计划。队计划。n n回顾解决这个问题的过程，
10、在解题思路上，我回顾解决这个问题的过程，在解题思路上，我们先主动降低题目难度，从简单情况入手，等们先主动降低题目难度，从简单情况入手，等到明确题目含义，并找到规律和思路后，再回到明确题目含义，并找到规律和思路后，再回到题目要求的难度，将已有思路推广和完善；到题目要求的难度，将已有思路推广和完善；在程序设计上，我们采用递归函数来实现深度在程序设计上，我们采用递归函数来实现深度搜索，同时采用分支定界的方法实现动态剪枝，搜索，同时采用分支定界的方法实现动态剪枝，从而提高搜索速度。从而提高搜索速度。35改进措施先按独行能力排序队员号 负载量 每天消耗 可独行天数 排序 4#18 2 9 1 3#17
11、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 636 4#6#上山消耗上山消耗上山消耗上山消耗4242 4#3#1#上山消耗上山消耗上山消耗上山消耗3838 24 24 3 3 4#4#24 24 4 4 3#6#5#1#2#3#6#5#1#2#30 30 1 1 30 30 2 2 32 32 3 3 3#6#5#1#2#4#6#5#1#2#3#6#5#1#2#4#6#5#1#2#42 42 0 0 42 42 1 1 42 42 2 2 48 48 2 2 48 48 2 2 6#5#1#2#3#6#5#2#4#6#5#2#6#5#
12、1#2#3#6#5#2#4#6#5#2#42 42 0 0 42 0 38 42 0 38 0 0 40 40 0 0 38 38 0 0 42 42 0 0 42 42 0 0 38 38 1 1 44 44 1 1 50 50 1 1 50 50 1 1 44 44 3 337k k 登山人登山人登山人登山人 k k个人所需个人所需个人所需个人所需 k k个人所带个人所带个人所带个人所带 k k个人所差个人所差个人所差个人所差 需支援高度需支援高度需支援高度需支援高度 结点评价结点评价结点评价结点评价1 4#24 18 6 3 (24,3)1 4#24 18 6 3 (24,3)2 4#3
13、#36 35 1 1 (36,1)2 4#3#36 35 1 1 (36,1)3 4#3#6#42 42 0 0 (42,0)3 4#3#6#42 42 0 0 (42,0)3 4#3#5#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)3 4#3#1#38 38 0 0 (38,0)V V 3 4#3#2#40 40 0 0 (40,0)3 4#3#2#40 40 0 0 (40,0)X X2 4#6#42 42 0 02 4#6#42 42 0 0 (42,0)(42,0)V V 2 4#5#42 40 2 1
14、 (42,1)2 4#5#42 40 2 1 (42,1)X X2 4#1#30 25 5 3 (30,2)2 4#1#30 25 5 3 (30,2)3 4#1#3#38 38 0 0 (38,0)3 4#1#3#38 38 0 0 (38,0)X X3 4#1#6#42 42 0 0 (42,0)3 4#1#6#42 42 0 0 (42,0)X X3 4#1#5#42 42 0 0 (42,0)3 4#1#5#42 42 0 0 (42,0)X X 3 4#1#2#38 33 5 2 (38,2)3 4#1#2#38 33 5 2 (38,2)X X 38#include#include
15、#include#include using namespace std;using namespace std;const int maxp=10;/const int maxp=10;/俱乐部人数俱乐部人数 int mimneed=1000;int mimneed=1000;/最小消耗，初始化为一个大数最小消耗，初始化为一个大数 int i,j;/int i,j;/整数变量整数变量 int N,p;/int N,p;/整数变量整数变量 int kneed,ktake,kd,kh,kk;/int kneed,ktake,kd,kh,kk;/整数变量整数变量39 struct person s
16、truct person /结构，描述登山俱乐部的每一个人结构，描述登山俱乐部的每一个人 int No;/int No;/编号编号 int need;/int need;/本人每日消耗本人每日消耗 int take;/int take;/本人的携带量本人的携带量 float t;/float t;/本人可独行天数本人可独行天数 int hh;/int hh;/本人支援高度本人支援高度 bool flag;/bool flag;/入选标志，初始化入选标志，初始化 为为0 0 clubmaxp+1,q,listmaxp+1;clubmaxp+1,q,listmaxp+1;/结构变量和结构数组结构变
17、量和结构数组40 void sort();/排序 void display(int);/显示输出 void Search1(int,int,int,int);/搜索组队方案（最小消耗）int cm(int,int);/求整数值 void ReadData();/输入数据 41 int main()int main()for(i=1;i=p;i+)/for(i=1;i=p;i+)/初始化初始化 clubi.flag=0;/clubi.flag=0;/置未入队标志置未入队标志 ReadData();/ReadData();/输入数据输入数据 sort();/sort();/排序排序 Search1
18、(1,0,0,N);/Search1(1,0,0,N);/调用搜索函数调用搜索函数 display(kk);/display(kk);/输出组队信息输出组队信息 return 0;return 0;42void ReadData()/void ReadData()/输入数据输入数据 cout cout输入山高输入山高N,N,俱乐部人数俱乐部人数pendl;/p N p;cin N p;cout cout输入输入p p个人每个人的每日消耗个人每个人的每日消耗endl;/endl;/提示信息提示信息 for(i=1;i=p;i+)for(i=1;i clubi.need;cin clubi.nee
19、d;/for /for cout cout输入输入p p个人每个人所带的给养个人每个人所带的给养endl;/endl;/提示信息提示信息 for(i=1;i=p;i+)for(i=1;i clubi.take;cin clubi.take;clubi.t=(float)clubi.take/(float)clubi.need;clubi.t=(float)clubi.take/(float)clubi.need;/for /for 43 void sortvoid sort()()/排序（对俱乐部的人，按独行天数从大到小排序）排序（对俱乐部的人，按独行天数从大到小排序）for(j=1;jp;j
20、+)for(j=1;jp;j+)for(i=1;i=p-j;i+)for(i=1;iclubi.t)if(clubi+1.tclubi.t)q=clubi+1;q=clubi+1;clubi+1=clubi;clubi+1=clubi;clubi=q;clubi=q;44 int cm(int a,int b)/向上取整函数 if(a%b=0)return a/b;else return(a/b)+1;45void display(int k1)/输出函数 cout登山人数为k1 ,最小消耗为mimneedendl;for(i=1;i=k1;i+)cout入队者的号为listi.No 登高为
21、listi.hhendl;46void Search1(int k,int need,int take,int h)void Search1(int k,int need,int take,int h)/搜索组队方案搜索组队方案 /for(i=1;i=p;i+)for(i=1;ih)if(clubi.flag=0)&(clubi.th)/if club /if club kneed=need+clubi.need*2*h;kneed=need+clubi.need*2*h;/k/k个人所需个人所需 if(kneedmimneed)continue;if(kneedmimneed)continu
22、e;/换人再试换人再试 clubi.flag=1;/clubi.flag=1;/标标标标i i已入队已入队已入队已入队 ktake=take+clubi.take;ktake=take+clubi.take;/计算计算计算计算k k个人所带个人所带个人所带个人所带47 if(ktakekneed)/k个人所带已大于所需kd=0;/置所差为0else kd=kneed-ktake;/计算k个人所差48int knd=0;/计算入队的k个人每日的消耗总和for(int m=1;m=k;m+)knd=clubm.need+knd;kh=cm(kd,knd);/计算对入队的k个人的支援高度49 lis
23、tk.No=clubi.No;/listk.No=clubi.No;/记第记第记第记第k k个入队者的编号个入队者的编号个入队者的编号个入队者的编号 listk.hh=h;/listk.hh=h;/记第记第记第记第k k个入队者的支援高度个入队者的支援高度个入队者的支援高度个入队者的支援高度 if(kh=0)/if(kh=0)/不需支援了，队已组成不需支援了，队已组成不需支援了，队已组成不需支援了，队已组成 /if kh/if kh if(kneedmimneed)if(kneedmimneed)/如果如果如果如果k k个人所需小于前次个人所需小于前次个人所需小于前次个人所需小于前次 mimneed=kneed;/mimneed=kneed;/更新最小消耗值更新最小消耗值更新最小消耗值更新最小消耗值 kk=k;/kk=k;/入队人数入队人数入队人数入队人数 /if kh /if kh50 else Search1(k+1,kneed,ktake,kh);/搜索下一个入队者搜索下一个入队者 clubi.flag=0;/回溯回溯 /if club/for/51结结 束束52