第5课贪心与动态规划课件

第第5 5课课 贪心与动态规划贪心与动态规划第第5 5课课 贪心与动态规划贪心与动态规划 1 1 贪心算法设计框架贪心算法设计框架 2 2 相对贪心问题相对贪心问题 3 3 绝对贪心问题绝对贪心问题 4 4 动态规划设计框架动态规划设计框架 5 5 多阶段特征动态规划多阶段特征动态规划 6 6 递推特征动态规划递推特征动态规划第第5课课贪贪心与心与动态规动态规划划1贪贪心算法心算法设计设计框架框架 第第5 5课课 贪心与动态规划贪心与动态规划 贪心策略选择贪心策略选择 贪心法又叫登山法贪心法又叫登山法,它的根本思想是逐它的根本思想是逐步到达山顶步到达山顶,即逐步获得最优解。贪心算法即逐步获得最优解。贪心算法没有固定的算法框架，算法设计的关键是没有固定的算法框架，算法设计的关键是贪心策略的选择。一定要注意，选择的贪贪心策略的选择。一定要注意，选择的贪心策略要具有无后向性。心策略要具有无后向性。所谓无后向性，指某状态以后的过程和所谓无后向性，指某状态以后的过程和不会影响以前的状态不会影响以前的状态,只与当前状态或以前只与当前状态或以前的状态有关的状态有关,称这种特性为无后效性。称这种特性为无后效性。2 2 贪心算法贪心算法贪贪心策略心策略选择选择2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 贪心算法的设计思想贪心算法的设计思想 从问题的某一个初始解出发逐步逼近给从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的定的目标，每一步都作一个不可回溯的决策决策,尽可能地求得最好的解。当达到某尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法中的某一步不需要再继续前进时，算法停止。算法停止。2 2 贪心算法贪心算法贪贪心算法的心算法的设计设计思想思想2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 贪心策略的框架贪心策略的框架 从问题的某一个初始解出发逐步逼近给从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决定的目标，每一步都作一个不可回溯的决策；策；尽可能地求出最好的可行解的一个解元尽可能地求出最好的可行解的一个解元素；素；当达到某算法中的某一步不需要再继续当达到某算法中的某一步不需要再继续前进时，算法停止；前进时，算法停止；由所有解组合成该问题的一个可行解。由所有解组合成该问题的一个可行解。2 2 贪心算法贪心算法贪贪心策略的框架心策略的框架2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 贪心算法的基本性质贪心算法的基本性质 对于一个具体的问题，是否可以用贪对于一个具体的问题，是否可以用贪心算法求解此问题，以及能否得到问题心算法求解此问题，以及能否得到问题的最优解，对于这个问题很难给予肯定的最优解，对于这个问题很难给予肯定的回答。但是，从许多可以用贪心算法的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有两求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性质和最优子个重要的性质：贪心选择性质和最优子结构性质。结构性质。2 2 贪心算法贪心算法贪贪心算法的基本性心算法的基本性质质2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 1.1.贪心选择性质贪心选择性质 所谓贪心选择性质是指所所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法可行的第一个基本要素，也是贪心法与动态规划法的主要区别。如是贪心法与动态规划法的主要区别。如活动安排问题、背包问题、单源最短路活动安排问题、背包问题、单源最短路径问题等。径问题等。2 2 贪心算法贪心算法1.贪贪心心选择选择性性质质2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 2.2.最优子结构性质最优子结构性质 该问题解的整体最优性依赖该问题解的整体最优性依赖于其局部子问题解的最优性。这种性于其局部子问题解的最优性。这种性质是可以采用贪心算法解决问题的关质是可以采用贪心算法解决问题的关键特征。例如，活动安排问题，在选键特征。例如，活动安排问题，在选择了一项活动后，它必须是最优的，择了一项活动后，它必须是最优的，否则不能得到全局的最优。否则不能得到全局的最优。2 2 贪心算法贪心算法2.最最优优子子结结构性构性质质2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 贪心算法的适用性贪心算法的适用性 贪贪心心算算法法对对问问题题只只需需考考虑虑当当前前局局部部信信息息就就要要做做出出决决策策，也也就就是是说说使使用用贪贪心心算算法法的的前前提提是是“局局部部最最优优策策略略能能导导致致产产生生全全局局最最优解优解”。该该算算法法的的适适用用范范围围较较小小,若若应应用用不不当当,不不能能保保证证求求得得问问题题的的最最佳佳解解。更更准准确确的的方方法法是是通通过过数数学学方方法法证证明明问问题题对对贪贪心心策策略略的的选用性。选用性。2 2 贪心算法贪心算法贪贪心算法的适用性心算法的适用性2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 绝对贪心问题贪心问题【例例1 1】会议室活动安排问题。会议室活动安排问题。活动安排问题就是要在所给的活动集活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。该问题合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单而又实的活动。贪心算法提供了一个简单而又实用的方法使得公共资源尽可能多地得到利用的方法使得公共资源尽可能多地得到利用。用。2 2 贪心算法贪心算法绝对贪绝对贪心心问题问题2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 会议室活动安排问题的描述会议室活动安排问题的描述 设有设有n n个活动的集合个活动的集合E=1,2,E=1,2,n,n，其中每个活动都要求使用同一资源，如会其中每个活动都要求使用同一资源，如会议室。而在同一时间内只有一个活动能使议室。而在同一时间内只有一个活动能使用这一资源。每个活动用这一资源。每个活动i i都有一个要求使都有一个要求使用该资源的起始时间用该资源的起始时间s si i和一个结束时间和一个结束时间f fi i,且且s si iffi i 。2 2 贪心算法贪心算法会会议议室活室活动动安排安排问题问题的描述的描述2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 如果选择了活动如果选择了活动i i，则它在半开时，则它在半开时间区间间区间ssi i,f,fi i)内占用资源。若区间内占用资源。若区间ssi i,f,fi i)与区间与区间ssj j,f,fj j)不相交，且不相交，且s sj jffi i时，则称活动时，则称活动i i与活动与活动j j是相容是相容的。的。活动安排问题就是要在活动所给的活动安排问题就是要在活动所给的集合中，选出最大的的活动相容子集集合中，选出最大的的活动相容子集合。合。2 2 贪心算法贪心算法如果如果选择选择了活了活动动i，则则它在半开它在半开时间时间区区间间si,fi)内内 第第5 5课课 贪心与动态规划贪心与动态规划 两种不同的选择策略两种不同的选择策略 用贪心选择可以有两种不用贪心选择可以有两种不同的策略：选同的策略：选s si i最小的，这样可以增最小的，这样可以增大场地的利用率；选大场地的利用率；选f fi i最小的，使得最小的，使得下一个活动可以更早开始。由于活动下一个活动可以更早开始。由于活动的占用时间长度没有限制，根据问题的占用时间长度没有限制，根据问题的定义，选择后者更合理。的定义，选择后者更合理。2 2 贪心算法贪心算法两种不同的两种不同的选择选择策略策略2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 适当的预处理适当的预处理 为了在每一次选择时取为了在每一次选择时取当前可以安排的活动中最早结束的当前可以安排的活动中最早结束的活动，应当首先把活动，应当首先把n n项活动按结束时项活动按结束时间的先后进行非递减排序，即，使间的先后进行非递减排序，即，使f f1 1ff2 2ffn n，然后在，然后在s si i值不小于值不小于当前时刻的活动中取当前时刻的活动中取f fi i值最小者。值最小者。2 2 贪心算法贪心算法适当的适当的预处预处理理2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 活动安排问题的算法描述活动安排问题的算法描述 1 1 对活动集对活动集E E中的中的n n个活动按结束时个活动按结束时间的先后进行非递减排序，得到数间的先后进行非递减排序，得到数组组S1.nS1.n，fl.nfl.n，其中，其中 f1f2fnf1f2fn。2 2 选择活动选择活动1 1为开始活动，加入可为开始活动，加入可选活动集。选活动集。2 2 贪心算法贪心算法活活动动安排安排问题问题的算法描述的算法描述2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划3 3 从第从第2 2个活动开始，用开始时间与个活动开始，用开始时间与第第1 1个活动的结束时间比较，若不小个活动的结束时间比较，若不小于，则选中；否则，依次选取后面于，则选中；否则，依次选取后面的活动比较。的活动比较。4 4 当活动当活动i=ni=n时，重复时，重复33，但从，但从当前被选中的活动开始。当前被选中的活动开始。2 2 贪心算法贪心算法3从第从第2个活个活动动开始，用开始开始，用开始时间时间与第与第1个活个活动动的的结结束束时间时间比比 第第5 5课课 贪心与动态规划贪心与动态规划 活动安排问题的贪心算法活动安排问题的贪心算法intActive_Selec(intn,ints,intf,boola)/返回活动安排问题的相容活动数目返回活动安排问题的相容活动数目对对n个活动按结束时间的先后进行非递减个活动按结束时间的先后进行非递减排序排序;a1=true;/从选择活动从选择活动1开始开始intj=1;intcount=1;/计数器计数器for(inti=2;i=fj)/if(si=fj)/选择选择 ai=true;ai=true;j=i;count+;/ifelseai=false;/丢弃丢弃/forreturncount;/Active_Selec2 2 贪心算法贪心算法if(si=fj)/第第5 5课课 贪心与动态规划贪心与动态规划 例如，下面的一个实例。设待安排例如，下面的一个实例。设待安排的的1111个活动的开始时间和结束时间按个活动的开始时间和结束时间按结束时间的非减序排列如下：结束时间的非减序排列如下：i1234567891011Si130535688212fi45678910111213142 2 贪心算法贪心算法例如，下面的一个例如，下面的一个实实例。例。设设待安排的待安排的11个活个活动动的开始的开始时间时间和和结结 第第5 5课课 贪心与动态规划贪心与动态规划2 2 贪心算法贪心算法2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 对于上面的对于上面的1111个活动，应用贪心个活动，应用贪心算法的计算，被选中的活动集和为算法的计算，被选中的活动集和为 A=A=11，4 4，8 8，1111。算法算法Active_Selec Active_Selec 的效率很高。的效率很高。当输入的活动已按结束时间的非减序当输入的活动已按结束时间的非减序排列，算法只需排列，算法只需O O(n)(n)的时间安排的时间安排n n个个活动如果所给出的活动未按非减序排活动如果所给出的活动未按非减序排列，可以用列，可以用O O(nlogn)(nlogn)的时间重排。的时间重排。2 2 贪心算法贪心算法对对于上面的于上面的11个活个活动动，应应用用贪贪心算法的心算法的计计算，被算，被选选中的中的 第第5 5课课 贪心与动态规划贪心与动态规划【例例2 2】DijkstraDijkstra单源最短路径问题。单源最短路径问题。问题描述问题描述 有向赋权图有向赋权图G=(V,E)G=(V,E)，求源顶点，求源顶点 u u 到到其它所有顶点的距离。其它所有顶点的距离。设设u,vu,v是是E E 中的边，中的边，Cu,v Cu,v 是边的长度。是边的长度。V V划分为两个集合划分为两个集合S S 和和T T：S S中所包含中所包含的顶点，它们到的顶点，它们到u u的距离已经确定；的距离已经确定；T T中所中所包含的顶点，它们到包含的顶点，它们到u u的距离尚未确定。的距离尚未确定。P(x)P(x)是从顶点是从顶点u u到顶点到顶点x x的最短路径中的最短路径中x x的前的前驱驱顶点顶点2 2 贪心算法贪心算法【例【例2】Dijkstra单单源最短路径源最短路径问题问题。2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 算法描述算法描述1.1.置置 S=u S=u，T=V-u T=V-u；2.2.，若，若(u,x)E(u,x)E，则，则 d du,xu,x=c=cu,xu,x，p(x)=u p(x)=u；否则，；否则，d du,xu,x=，p(x)=-1 p(x)=-1；3.3.寻找寻找 t T t T，使得，使得d du,tu,t=mi nd=mi ndu,xu,x|x|x T T ，则；，则；就就d du,tu,t是是u u 到到x x的距离；的距离；4.S=St4.S=St，T=T-t T=T-t；5.5.若若 T=T=，算法结束；否则，转，算法结束；否则，转6 6；2 2 贪心算法贪心算法算法描述算法描述2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划6.6.对与对与t t 相邻接的所有顶点相邻接的所有顶点x x，如果，如果 d du,xu,xddu,tu,t+c+ct,x t,x，直接转，直接转3 3；否则，令；否则，令 ，d du,xu,x=d=du,tu,t+c+ct,xt,x ，p(x)=t p(x)=t，转转3 3。例如，例如，在在如如图的有向赋权图中，求顶点图的有向赋权图中，求顶点a a 到其它所有顶点的距离。到其它所有顶点的距离。2 2 贪心算法贪心算法6.对对与与t相相邻邻接的所有接的所有顶顶点点x，如果，如果du,xdu,t 第第5 5课课 贪心与动态规划贪心与动态规划 如果用邻接表来存放顶点之间的距离，如果用邻接表来存放顶点之间的距离，则邻接表如图所示。则邻接表如图所示。2 2 贪心算法贪心算法如果用如果用邻邻接表来存放接表来存放顶顶点之点之间间的距离，的距离，则邻则邻接表如接表如图图所示。所示。2 第第5 5课课 贪心与动态规划贪心与动态规划 迪杰斯特拉迪杰斯特拉算法的执行过程算法的执行过程da,bda,cda,dda,eda,fda,gda,hda,tt1a1441b2a,b34103c3a,b,c49674d4a,b,c,d9676f5a,b,c,d,f87117g6 a,b,c,d,f,g8108e7 a,b,c,d,f,g,e99h8 a,b,c,d,f,g,e,h2 2 贪心算法贪心算法迪杰斯特拉算法的迪杰斯特拉算法的执执行行过过程程da,bda,cda,dda,e 第第5 5课课 贪心与动态规划贪心与动态规划 各个顶点到顶点各个顶点到顶点a a的路径的路径2 2 贪心算法贪心算法各个各个顶顶点到点到顶顶点点a的路径的路径2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 数据结构定义数据结构定义struct adj_list struct adj_list /结点的数据结构结点的数据结构 int v_num;int v_num;/邻接顶点的编号邻接顶点的编号 float len;float len;/邻接顶点与该顶点邻接顶点与该顶点的距离的距离 struct adj_list*next;struct adj_list*next;/下一个邻接顶下一个邻接顶点点 ;2 2 贪心算法贪心算法数据数据结结构定构定义义2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 数据结构定义数据结构定义typedef struct adj_list NODE;typedef struct adj_list NODE;NODENODE noden;noden;/邻接表头结点邻接表头结点floatfloatdn;dn;/顶点顶点 到源顶点的到源顶点的距离距离 intint pn;pn;/最短路径上最短路径上前驱前驱顶点的顶点的编号编号BOOL sn;/SiBOOL sn;/Si为真，为真，顶点顶点i i标志在标志在S S中中2 2 贪心算法贪心算法数据数据结结构定构定义义2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 Dijkstra Dijkstra算法算法#define MAX_FLOT_NUM#define MAX_FLOT_NUM /最大的浮点数最大的浮点数 void dijkstra(NODE node,int n,int void dijkstra(NODE node,int n,int u,u,float d,int p)float d,int p)float temp;float temp;int i,j,t;int i,j,t;BOOL*s=new BOOLn;BOOL*s=new BOOLn;NODE*pnode;NODE*pnode;2 2 贪心算法贪心算法Dijkstra算法算法2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 for(i=0;in;i+)for(i=0;in;i+)/初始化初始化 di=MAX_FLOAT_NUM;di=MAX_FLOAT_NUM;si=FALSE;pi=si=FALSE;pi=1;1;if(!(pnode=nodeu.next)if(!(pnode=nodeu.next)/源顶点与其它顶点不相邻接源顶点与其它顶点不相邻接 return;return;while(pnode)while(pnode)/预置与源顶点相邻接的顶点预置与源顶点相邻接的顶点距离距离2 2 贪心算法贪心算法for(i=0;iv_num=pnode-dpnode-v_num=pnode-len;len;ppnode-v_num=u;ppnode-v_num=u;pnode=pnode-next;pnode=pnode-next;du=0;su=TRUE;du=0;su=TRUE;/开始时开始时,集合集合S S仅包含顶点仅包含顶点u u for(i=1;in;i+)for(i=1;in;i+)temp=MAX_FLOAT_NUM;t=temp=MAX_FLOAT_NUM;t=u;u;for(j=0;jn;j+)/for(j=0;jv_num=pno 第第5 5课课 贪心与动态规划贪心与动态规划 if(!sj&djtemp)if(!sj&djv_num&dpnode-if(!spnode-v_num&dpnode-v_numv_num dt+pnode-len)dt+pnode-len)2 2 贪心算法贪心算法if(!sj&djv_num=dt+dpnode-v_num=dt+pnode-len;pnode-len;ppnode-v_num=t;ppnode-v_num=t;pnode=pnode-next;pnode=pnode-next;delete s;delete s;2 2 贪心算法贪心算法dpnode-v_num=dt 第第5 5课课 贪心与动态规划贪心与动态规划 算法分析算法分析 时间复杂性为时间复杂性为 O(n O(n2 2)。算法需要算法需要 工作空间工作空间O(n)O(n)。2 2 贪心算法贪心算法算法分析算法分析2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 最小最小代价代价生成树问生成树问题题 若连通图若连通图 G=(V,E)G=(V,E)，T T是是G G 的生成树。的生成树。则生成树则生成树 T T有如下性质：有如下性质：性质性质1:T1:T是不含简单回路的连通图；是不含简单回路的连通图；性质性质2:T2:T中的每一对顶点中的每一对顶点u u 和和v v，恰好有，恰好有一条从一条从u u 到到v v 的基本通路；的基本通路；性质性质3:3:若若|V|=n|V|=n，|E|=m|E|=m，则，则m=n-1 m=n-1。性质性质4:4:在在T T中的任何两个不相邻接的顶点中的任何两个不相邻接的顶点之间增加一条边，则得到之间增加一条边，则得到T T中唯一的一条中唯一的一条基本回路。基本回路。2 2 贪心算法贪心算法最小代价生成最小代价生成树问题树问题2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 若图若图G G 是赋权图，是赋权图，T T 是是G G的生成树。的生成树。T T的的每个树枝上的权之和称为每个树枝上的权之和称为T T的权。的权。G G中权最中权最小的生成树，称为小的生成树，称为 G G最小最小代价代价生成树、或生成树、或最小生成树。最小生成树。假定图都是连通的。如果图不连通，假定图都是连通的。如果图不连通，可以把算法应用于图的每一个连通分支。可以把算法应用于图的每一个连通分支。2 2 贪心算法贪心算法若若图图G是是赋权图赋权图，T是是G的生成的生成树树。T的每个的每个树树枝上的枝上的权权 第第5 5课课 贪心与动态规划贪心与动态规划 最小代价生成树原理最小代价生成树原理V是顶点集合，是顶点集合，U是已选中顶点集合是已选中顶点集合U权值最小权值最小V-U2 2 贪心算法贪心算法最小代价生成最小代价生成树树原理原理2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划【例例3 3】KruskalKruskal最小生成树问题。最小生成树问题。克鲁斯卡尔算法的思想克鲁斯卡尔算法的思想1.1.所有顶点都作为孤立顶点，每个顶点构所有顶点都作为孤立顶点，每个顶点构成一棵只有根结点的树，这些树构成森林成一棵只有根结点的树，这些树构成森林T T；2.2.所有边按权的非降顺序排序，构成边集所有边按权的非降顺序排序，构成边集的一个非降序列；的一个非降序列；3.3.从边集中取出权最小的边，如果把这条从边集中取出权最小的边，如果把这条边加入森林边加入森林T T 中，不会使中，不会使 构成回路，就构成回路，就把它加入森林把它加入森林T T中；否则，就放弃它中；否则，就放弃它。2 2 贪心算法贪心算法【例【例3】Kruskal最小生成最小生成树问题树问题。2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划4.4.重复这个过程，直到把重复这个过程，直到把n-1 n-1 条边都放到条边都放到森林森林T T以后，结束这个过程，这时，森林以后，结束这个过程，这时，森林T T中所有的树就被连结成一棵树中所有的树就被连结成一棵树 ，它就是所，它就是所要求取的图的最小要求取的图的最小代价代价生成树。生成树。2 2 贪心算法贪心算法4.重复重复这这个个过过程，直到把程，直到把n-1条条边边都放到森林都放到森林T以后，以后，结结束束这这 第第5 5课课 贪心与动态规划贪心与动态规划 Kruskal Kruskal算法描述算法描述1.1.按权的非降顺序排序按权的非降顺序排序E E中的边；中的边；2.2.令最小令最小代价代价生成树的边集为生成树的边集为T T，T T初始初始化为：化为：T=T=；3.3.把每个顶点都初始化为树的根结点；把每个顶点都初始化为树的根结点；4.4.令令e=(u,v)e=(u,v)是是E E中权最小的边，中权最小的边，E=E-e E=E-e；5.5.如果如果find(u)find(v)find(u)find(v)，则执行，则执行union(u,v)union(u,v)操作，操作，T=Te T=Te；6.6.如果如果|T|n-1|T|n-1，转，转4 4；否则，算法结束。；否则，算法结束。2 2 贪心算法贪心算法Kruskal算法描述算法描述2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 克鲁斯卡尔算法的执行过程克鲁斯卡尔算法的执行过程abcdegf5141827168213ae12dcbgf7148531621712182 2 贪心算法贪心算法克克鲁鲁斯卡斯卡尔尔算法的算法的执执行行过过程程abcdegf5141827168 第第5 5课课 贪心与动态规划贪心与动态规划 数据结构数据结构 假定无向赋权图假定无向赋权图G=(U,E,W)G=(U,E,W)有有n n个顶点，个顶点，m m条边。条边。typedef struct typedef struct/边的数据结构边的数据结构 float key;float key;/边的权边的权 int intu;u;/与边关联的顶点编号与边关联的顶点编号 int intv;v;/与边关联的顶点编号与边关联的顶点编号 EDGE;EDGE;2 2 贪心算法贪心算法数据数据结结构构2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 数据结构数据结构struct node struct node /顶点的数据结构顶点的数据结构 struct node *p;struct node *p;/指向父亲结点指向父亲结点 int intrank;rank;/结点的秩结点的秩 int intu;u;/顶点编号顶点编号;typedef struct node NODE;typedef struct node NODE;EDGE EmEDGE Em1,Tn;1,Tn;NODE Vn;NODE Vn;2 2 贪心算法贪心算法数据数据结结构构2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 克鲁斯卡尔算法克鲁斯卡尔算法 void kruskal(NODE V,EDGE E,EDGE void kruskal(NODE V,EDGE E,EDGE T,int n,int m)T,int n,int m)int i,j,k;int i,j,k;EDGE e;EDGE e;NODE*u,*v;NODE*u,*v;make_heap(E,m);make_heap(E,m);/用边集构成最用边集构成最小堆小堆 for(i=0;in;i+)for(i=0;in;i+)/每个顶点都作为树的根结点每个顶点都作为树的根结点,构成构成森林森林 2 2 贪心算法贪心算法克克鲁鲁斯卡斯卡尔尔算法算法2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 Vi.rank=0;Vi.p=Vi.rank=0;Vi.p=NULL;NULL;i=j=0;i=j=0;while(i0)while(i0)e=delete_min(E,&m);e=delete_min(E,&m);/从最小堆中取下权最小的边从最小堆中取下权最小的边 u=find(&Ve.u);u=find(&Ve.u);/检索与边相邻接的顶点所在树的根结检索与边相邻接的顶点所在树的根结点点 2 2 贪心算法贪心算法Vi.rank=0;Vi 第第5 5课课 贪心与动态规划贪心与动态规划 v=find(&Ve.v);v=find(&Ve.v);if(u!=v)if(u!=v)/两个根结点不在同一棵树上两个根结点不在同一棵树上 union(u,v);union(u,v);/连接它连接它们们 Tj+=e;Tj+=e;/把边加把边加入生成树入生成树 i+;i+;2 2 贪心算法贪心算法v=find(&Ve.v);第第5 5课课 贪心与动态规划贪心与动态规划 算法分析算法分析 算法的运行时间为算法的运行时间为 O(mlog m)O(mlog m)。对完全图，对完全图，m=n(n-1)/2m=n(n-1)/2 ，花费的，花费的时间为时间为 O(n O(n2 2log n)log n)；对平面图，对平面图，m=O(n)m=O(n)，所花费的时，所花费的时间为间为 O(nlog n)O(nlog n)。最小生成树边集所需空间为最小生成树边集所需空间为O(n)O(n)。其余工作单元为其余工作单元为 O(1)O(1)。2 2 贪心算法贪心算法算法分析算法分析2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 克鲁斯卡尔算法克鲁斯卡尔算法正确性证明正确性证明 G G是无向连通图，是无向连通图，T T*是最小是最小代价代价生成树生成树边集；边集；T T是由克鲁斯卡尔算法所产生的生是由克鲁斯卡尔算法所产生的生成树边集。则成树边集。则 G G中的顶点，既是中的顶点，既是 T T*中的中的顶点，也是顶点，也是T T中的顶点。中的顶点。若若G G 的顶点数为的顶点数为n n，则，则|T|T*|=|T|=n-1|=|T|=n-1。下面用用归纳法证明下面用用归纳法证明 T T*=T=T。1.1.设设e e1 1 是是G G中权最小的边，根据克鲁斯卡中权最小的边，根据克鲁斯卡尔算法，有尔算法，有e e1 1 T T。2 2 贪心算法贪心算法克克鲁鲁斯卡斯卡尔尔算法正确性算法正确性证证明明2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 若若 e e1 1TT*，因为，因为 T T*是是G G 的最小生成树，的最小生成树，和和 e e1 1关联的顶点必是关联的顶点必是T T*中的两个不相中的两个不相邻接的顶点，把邻接的顶点，把 e e1 1加入加入 T T*，将使，将使 T T*构成构成唯一的一条回路。唯一的一条回路。假定回路是假定回路是e e1 1，e e a1 a1，e e a2 a2 e e ak ak，且，且 e e1 1是是这条回路中权最小的边。这条回路中权最小的边。令令T T*=Te=Te1 1-e-eaiai ，e eaiai 是是回路回路 中除中除 外的任意一条边。外的任意一条边。边集边集T T*仍然是仍然是G G的生成树，且的生成树，且T T*的权小的权小于或等于于或等于T T*的权。的权。2 2 贪心算法贪心算法若若e1 T*，因，因为为T*是是G的最小生成的最小生成树树，2贪贪心算心算 第第5 5课课 贪心与动态规划贪心与动态规划 若若T T*的权小于的权小于T T*的权，与的权，与 T T*是是G G的最小生的最小生成树的边集矛盾，所以，成树的边集矛盾，所以，e e1 1TT*；若若T T*的权等于的权等于T T*的权，则的权，则 T T*也是也是G G 的最的最小生成树的边集，且小生成树的边集，且 e e1 1TT*。可用新的可用新的 T T*来标记来标记 T T*。在这两种情况。在这两种情况下，都有下，都有 。2.2.若若e e2 2 是是G G中权第二小的边，同理可证中权第二小的边，同理可证 ，e e2 2TT ，且，且e e2 2TT*。2 2 贪心算法贪心算法若若T*的的权权小于小于T*的的权权，与，与T*是是G的最小生成的最小生成树树的的边边集集 第第5 5课课 贪心与动态规划贪心与动态规划3.3.设设e e1 1，e e 2,2,e e k k是是 T T中前面中前面k k 条权最小的条权最小的边，且它们也属于边，且它们也属于T T*，令，令 e e k+1 k+1是是 G G中第中第k+1 k+1 条权最小的边，条权最小的边，e ek+1k+1TT ，但，但 e ek+1k+1T T*。与与 e ek+1k+1关联的顶点也是关联的顶点也是 T T*中的两个不中的两个不相邻接的顶点。把相邻接的顶点。把 e ek+1k+1加入加入 T T*，将使，将使 T T*构成唯一的一条回路。构成唯一的一条回路。假定回路是假定回路是 e ek+1k+1，e e a1 a1，e e a2 a2 e e am am，在，在 其其中，必有一条边中，必有一条边e e ai ai ，但，但 e e ai ai T T*，但但 e e ai ai T T*。否则，。否则，根根据性质据性质4 4 将存在回将存在回路。路。2 2 贪心算法贪心算法3.设设e1，e2,ek是是T中前面中前面k条条权权最小的最小的边边 第第5 5课课 贪心与动态规划贪心与动态规划 e e1 1，e e 2,2,e e k+1 k+1是是 T T中前面中前面k+1k+1条权最小的条权最小的边，边，并且并且 e e1 1，e e 2,2,e e k k都属于都属于T T，所以，所以，e e ai ai 的权大于或等于的权大于或等于e e k+1 k+1 的权。的权。令令T T*=Te=Tek+1 k+1-e-eaiai ，则，则T T*仍仍然然G G是是 的生成树，且的生成树，且T T*的权小于或等于的权小于或等于T T*的权。必有的权。必有 e ek+1k+1T T*。4.4.设设 e e1 1，e e 2,2,e e k k是是G G中前面中前面 k k条权最小的条权最小的边，且它们都属于边，且它们都属于 T T ，也属于，也属于T T*，令，令 e ek+1k+1是是G G中第中第 k+1 k+1条权最小的边，且条权最小的边，且 e ek+1k+1T T，但，但 e ek+1k+1T T*。2 2 贪心算法贪心算法e1，e2,ek+1是是T中前面中前面k+1条条权权最小的最小的 第第5 5课课 贪心与动态规划贪心与动态规划 因为因为 e e1 1，e e 2,2,e e k+1 k+1都属于都属于 T T，而，而 e ek+1k+1T T，根据克鲁斯卡尔算法，必有根据克鲁斯卡尔算法，必有 e e1 1，e e 2,2,e e k+1k+1构成回路。构成回路。因为因为 e e1 1，e e 2,2,e e k+k+也属于也属于 T T*，若，若 e ek+1k+1T T*，将使，将使 T T*存在回路。因此只有存在回路。因此只有e ek+1k+1T T*。综上所述，有综上所述，有T T*=T=T。所以，克鲁斯卡。所以，克鲁斯卡尔算法正确尔算法正确性得证性得证。2 2 贪心算法贪心算法因因为为e1，e2,ek+1都属于都属于T，而，而ek+第第5 5课课 贪心与动态规划贪心与动态规划 相对贪心问题相对贪心问题 【例例4 4】发工资现金找零问题。发工资现金找零问题。问题描述问题描述某某 单位给每个职工发工资（精确到元）。单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱为了保证不要临时兑换零钱,且取款的张且取款的张数最少，取工资前要统计出所有职工的工数最少，取工资前要统计出所有职工的工资所需各种币值资所需各种币值(100,50,20,10,5,2,1(100,50,20,10,5,2,1元共元共七种七种)的张数。的张数。2 2 贪心算法贪心算法相相对贪对贪心心问题问题2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 算法设计算法设计 1)1)读取每人的工资。读取每人的工资。2)2)对对每每一一个个人人的的工工资资，先先尽尽量量多多地地取取大大面面额额的的币币种种，由由大大面面额额到到小小面面额额币币种种逐逐渐渐统计。统计。3)3)利用数组利用数组,将七种币值按降序存储在数将七种币值按降序存储在数组组B B。这样，七种币值就可表示为。这样，七种币值就可表示为Bi,i=1,2,3,4,5,6,7Bi,i=1,2,3,4,5,6,7。4)4)设置一个有设置一个有7 7个元素的累加器数组个元素的累加器数组S S。2 2 贪心算法贪心算法算法算法设计设计2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 算法分析算法分析 算法的时间复杂性是算法的时间复杂性是O O（n n）。）。以上问题的背景是在我国以上问题的背景是在我国,且这样的币且这样的币种正好适合使用贪心算法。假若种正好适合使用贪心算法。假若,某国的币某国的币种是这样的种是这样的,共共9 9种种（100,70,50,20,10,7,5,2,1100,70,50,20,10,7,5,2,1）在在这这样样的的币币值值种种类类下下,再再用用贪贪心心算算法法就就行行不不通通了了,比比如如某某 人人 工工 资资 是是 140,140,按按 贪贪 心心 算算 法法 140=100*(1140=100*(1张张)+20*)+20*(2(2张张)共共需需要要3 3张张,而而事事实实上上,只只要要取取2 2张张7070面额的是最佳结果面额的是最佳结果,2 2 贪心算法贪心算法算法分析算法分析2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划【例例5 5】取数游戏。取数游戏。问题描述问题描述 有有2 2个人轮流取个人轮流取2n2n个数中的个数中的n n个数，取数个数，取数之和大者为胜。设计算法，让先取数者获之和大者为胜。设计算法，让先取数者获胜，模拟取数过程。胜，模拟取数过程。问题分析问题分析 这个游戏一般假设取数者只能看到这个游戏一般假设取数者只能看到2n2n个个数中两边的数数中两边的数,用贪心算法的情况用贪心算法的情况:2 2 贪心算法贪心算法【例【例5】取数游】取数游戏戏。2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 例如例如 若一组数据为：若一组数据为：6,16,27,6,12,9,2,11,6,5 6,16,27,6,12,9,2,11,6,5 用用贪贪心心策策略略每每次次两两人人都都取取两两边边的的数数中中较较大的一个数大的一个数,先取者胜先取者胜.以以A先取为例：先取为例：取数结果为：取数结果为：A 6,27,12,5,11=61 A 6,27,12,5,11=61 胜胜 B 16,6,9,6,2=39B 16,6,9,6,2=392 2 贪心算法贪心算法例如例如2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 但若选另一组数据但若选另一组数据 16,27,7,12,9,2,11,6 16,27,7,12,9,2,11,6 仍都用贪心算法，先取者仍都用贪心算法，先取者A A败。败。取数结果为：取数结果为：A 16,7,9,11=43A 16,7,9,11=43 B 27,12,6,2=47 B 27,12,6,2=47 胜胜 其其实实，若若我我们们只只能能看看到到两两边边的的数数据据，则则此此题题无无论论先先取取还还是是后后取取都都无无必必胜胜的的策策略略。这时一般的策略是用近似贪心算法。这时一般的策略是用近似贪心算法。2 2 贪心算法贪心算法但若但若选选另一另一组组数据数据2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 但若取数者能看到全部但若取数者能看到全部2n2n个数，则此问个数，则此问题可有一些简单的方法，有的虽不能保证题可有一些简单的方法，有的虽不能保证所取数的和是最大，但确是一个先取者必所取数的和是最大，但确是一个先取者必胜的策略。胜的策略。2 2 贪心算法贪心算法但若取数者能看到全部但若取数者能看到全部2n个数，个数，则则此此问题问题可有一些可有一些简单简单的方法的方法 第第5 5课课 贪心与动态规划贪心与动态规划 数学模型的建立数学模型的建立N N个个数数排排成成一一行行，我我们们给给这这N个个数数从从左左到到右右编编号号，依依次次为为1，2，N，因因为为N为为偶偶数数，又又因因为为是是我我们们先先取取数数，计计算算机机后后取取数数，所所以以一一开开始始我我们们既既可可以以取取到到一一个个奇奇编编号号的的数数（最最左左边边编编号号为为1的的数数）又又可可以以取取到到一一个个偶偶编编号号的的数数（最最右右边边编编号号为为N的的数数）。2 2 贪心算法贪心算法数学模型的建立数学模型的建立2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 如果我们第一次取奇编号（编号为如果我们第一次取奇编号（编号为1）的）的数，则接着计算机只能取到偶编号（编号数，则接着计算机只能取到偶编号（编号为为2或或N）的数；）的数；如如果果我我们们第第一一次次取取偶偶编编号号（编编号号为为N）的的数数，则则接接着着计计算算机机只只能能取取到到奇奇编编号号（编编号号为为1或或N-1）的数；）的数；即即无无论论我我们们第第一一次次是是取取奇奇编编号号的的数数还还是是取取偶偶编编号号的的数数，接接着着计计算算机机只只能能取取到到另另一一种编号（偶编号或奇编号）的数。种编号（偶编号或奇编号）的数。2 2 贪心算法贪心算法如果我如果我们们第一次取奇第一次取奇编编号（号（编编号号为为1）的数，）的数，则则接着接着计计算机只能算机只能 第第5 5课课 贪心与动态规划贪心与动态规划 算法设计算法设计 有了以上建立的高效数学模型，算法就有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就先了奇数位和偶数位的数据之和，然后就先了取数者就可以确定必胜的取数方式了。取数者就可以确定必胜的取数方式了。以下面一排数为例：以下面一排数为例：1 2 3 10 5 6 7 8 9 4奇编号数之和为奇编号数之和为25（=1+3+5+7+9）偶编号数之和为偶编号数之和为30（=2+10+6+8+4）2 2 贪心算法贪心算法算法算法设计设计2贪贪心算法心算法 第第5 5课课 贪心与动态规划贪心与动态规划 动态规划的划的概念概念 在动态规划算法策略中，体现在它的决在动态规划算法策略中，体现在它的决策不是线性的而是全面考虑不同的情况分策不是线性的而是全面考虑不同的情况分别进行决策别进行决策,并通过多阶段决策来最终解并通过多阶段决策来最终解决问题。在各个阶段采取决策后决问题。在各个阶段采取决策后,会不断会不断决策出新的数据决策出新的数据,直到找到最优解直到找到最优解.每次决每次决策依赖于当前状态策依赖于当前状态,又随即引起状态的转又随即引起状态的转移。一个决策序列就是在变化的状态中产移。一个决策序列就是在变化的状态中产生出来的。所以，这种多阶段决策最优化生出来的。所以，这种多阶段决策最优化的解决问题的过程称为动态规划。的解决问题的过程称为动态规划。3 3 动态规划动态规划动态规动态规划的概念划的概念3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 动态规划的最优决策原理动态规划的最优决策原理 活动过程划分为若干个阶段，每一阶段活动过程划分为若干个阶段，每一阶段的决策，依赖于前一阶段的状态，由决策的决策，依赖于前一阶段的状态，由决策所采取的动作，使状态发生转移，成为下所采取的动作，使状态发生转移，成为下一阶段的决策依据。一阶段的决策依据。动态规划的决策过程动态规划的决策过程 最优性原理：无论过程的初始状态和最优性原理：无论过程的初始状态和初始决策是什么，其余决策都必须相对于初始决策是什么，其余决策都必须相对于初始决策所产生的状态，构成一个最优决初始决策所产生的状态，构成一个最优决策序列。策序列。3 3 动态规划动态规划动态规动态规划的最划的最优优决策原理决策原理3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 最优决策是在最后阶段形成的，然后向最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；前倒推，直到初始阶段；而决策的具体结果及所产生的状态转移，而决策的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向却是由初始阶段开始进行计算的，然后向后递归或迭代，直到最终结果。后递归或迭代，直到最终结果。3 3 动态规划动态规划最最优优决策是在最后决策是在最后阶阶段形成的，然后向前倒推，直到初始段形成的，然后向前倒推，直到初始阶阶段；段；第第5 5课课 贪心与动态规划贪心与动态规划 动态规划决策划决策过程程 3 3 动态规划动态规划动态规动态规划决策划决策过过程程3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 令最优状态为令最优状态为 s(2,22)s(2,22)，由此倒推：，由此倒推：s(2,22)p(2,22)s(1,2)s(2,22)p(2,22)s(1,2)p(1,2)s0,p(1,2)s0,最优决策序列最优决策序列:p(1,2)p(2,22):p(1,2)p(2,22)状态转移序列：状态转移序列：s0 s(1,2)s0 s(1,2)s(2,22)s(2,22)动态规划函数赖动态规划函数赖是是决策的决策的依据依据。动态规。动态规划函数可以递归地定义，也可以用递推公划函数可以递归地定义，也可以用递推公式来表达。整个决策过程，可以递归地进式来表达。整个决策过程，可以递归地进行，行，也可以也可以用循环迭代的方法进行。用循环迭代的方法进行。3 3 动态规划动态规划令最令最优优状状态为态为s(2,22)，由此倒推：，由此倒推：3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 动态规划的基本性划的基本性质 动态规划算法的问题及决策应该具有三动态规划算法的问题及决策应该具有三个性质：最优化原理、无后向性、子问个性质：最优化原理、无后向性、子问题重叠性质。题重叠性质。1)1)最优化原理最优化原理(或称为最佳原则、最优或称为最佳原则、最优子结构子结构)。2)2)无后向性无后向性(无后效性无后效性)。3)3)有重叠子问题。有重叠子问题。3 3 动态规划动态规划动态规动态规划的基本性划的基本性质质3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 设计一个标准的动态规划算法的步骤设计一个标准的动态规划算法的步骤 1)1)划分阶段划分阶段 按按照照问问题题的的时时间间和和空空间间特特征征，将将问问题题划分为若干阶段，满足无后向性。划分为若干阶段，满足无后向性。2)2)选择状态选择状态 将各阶段的不同状态表示出来。将各阶段的不同状态表示出来。3)3)确定决策并写出状态转移方程确定决策并写出状态转移方程 根根据据相相邻邻两两个个阶阶段段的的状状态态之之间间的的关关系系确定决策方程和状态转移方程。确定决策方程和状态转移方程。3 3 动态规划动态规划设计设计一个一个标标准的准的动态规动态规划算法的步划算法的步骤骤3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 动态规划的特点划的特点 在贪心算法中，每一步的选择，都凭在贪心算法中，每一步的选择，都凭着当前的状态作出在当前看来是最好的着当前的状态作出在当前看来是最好的选择，即局部最优选择。然后再去解作选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。这出这个选择后产生的相应的子问题。这种选择，可以依赖于以往所作过的选择，种选择，可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依但决不依赖于将来所作的选择，也不依赖于子问题的解。动态规划方法则是对赖于子问题的解。动态规划方法则是对问题进行全面的规划处理，从而弥补了问题进行全面的规划处理，从而弥补了贪心法在这方面的不足。贪心法在这方面的不足。3 3 动态规划动态规划动态规动态规划的特点划的特点3动态规动态规划划 第第5 5课课 贪心与动态规划贪心与动态规划 动态规划算法与分治法类似，其基本思动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是题。但是经分解得到的子问题往往不是互相独立的。在用分治法求解时，有些互相独立的。在用分治法求解时，有些子问题被重复计算了许多次。如果能够子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大时再找出已求得的答案，就可以避免大量重复计算，量重复计算，从而得到多项式时间算法。从而得到多项式时间算法。3 3 动态规划动态规划动态规动态规划算法与分治法划算法与分治法类类似，其基本思想也是将待求解似，其基本思想也是将待求解问题问题分分 第第5 5课课 贪心与动态规划贪心与动态规划【例例6 6】FibonacciFibonacci序列问题。序列问题。算法算法1 1 FibonacciFibon