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

第5课

贪心与动态规划

1贪心算法设计框架2相对贪心问题3绝对贪心问题4动态规划设计框架5多阶段特征动态规划6递推特征动态规划第5课贪心与动态规划1贪心算法设计框架□贪心策略选择•贪心法又叫登山法,它的根本思想是逐步到达山顶,即逐步获得最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。一定要注意，选择的贪心策略要具有无后向性。•所谓无后向性，指某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。2贪心算法□贪心策略选择2贪心算法□贪心算法的设计思想

•从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。2贪心算法□贪心算法的设计思想2贪心算法•贪心策略的框架

从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策；尽可能地求出最好的可行解的一个解元素；

当达到某算法中的某一步不需要再继续前进时，算法停止；

由所有解组合成该问题的一个可行解。2贪心算法•贪心策略的框架2贪心算法□贪心算法的基本性质

•对于一个具体的问题，是否可以用贪心算法求解此问题，以及能否得到问题的最优解，对于这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性质和最优子结构性质。2贪心算法□贪心算法的基本性质2贪心算法

1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心法与动态规划法的主要区别。如活动安排问题、背包问题、单源最短路径问题等。

2贪心算法1.贪心选择性质2贪心算法

2.最优子结构性质该问题解的整体最优性依赖于其局部子问题解的最优性。这种性质是可以采用贪心算法解决问题的关键特征。例如，活动安排问题，在选择了一项活动后，它必须是最优的，否则不能得到全局的最优。

2贪心算法2.最优子结构性质2贪心算法□贪心算法的适用性

•贪心算法对问题只需考虑当前局部信息就要做出决策，也就是说使用贪心算法的前提是“局部最优策略能导致产生全局最优解”。

该算法的适用范围较小,若应用不当,不能保证求得问题的最佳解。更准确的方法是通过数学方法证明问题对贪心策略的选用性。2贪心算法□贪心算法的适用性2贪心算法

□绝对贪心问题【例1】会议室活动安排问题。

•活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单而又实用的方法使得公共资源尽可能多地得到利用。2贪心算法□绝对贪心问题2贪心算法

•

会议室活动安排问题的描述设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如会议室。而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi

。2贪心算法•会议室活动安排问题的描述2贪心算法•

如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，且sj≥fi时，则称活动i与活动j是相容的。•

活动安排问题就是要在活动所给的集合中，选出最大的的活动相容子集合。2贪心算法•如果选择了活动i，则它在半开时间区间[si,fi)内•两种不同的选择策略用贪心选择可以有两种不同的策略：选si最小的，这样可以增大场地的利用率；选fi最小的，使得下一个活动可以更早开始。由于活动的占用时间长度没有限制，根据问题的定义，选择后者更合理。2贪心算法•两种不同的选择策略2贪心算法

•适当的预处理

为了在每一次选择时取当前可以安排的活动中最早结束的活动，应当首先把n项活动按结束时间的先后进行非递减排序，即，使f1≤f2≤…≤fn，然后在si值不小于当前时刻的活动中取fi值最小者。

2贪心算法•适当的预处理2贪心算法•活动安排问题的算法描述

[1]对活动集E中的n个活动按结束时间的先后进行非递减排序，得到数组S[1..n]，f[l..n]，其中

f[1]≤f[2]≤…≤f[n]。

[2]选择活动1为开始活动，加入可选活动集。2贪心算法•活动安排问题的算法描述2贪心算法[3]从第2个活动开始，用开始时间与第1个活动的结束时间比较，若不小于，则选中；否则，依次选取后面的活动比较。[4]当活动i<=n时，重复[3]，但从当前被选中的活动开始。

2贪心算法[3]从第2个活动开始，用开始时间与第1个活动的结束时间比•

活动安排问题的贪心算法intActive_Selec(intn,int[]s,int[]f,boola[]){//返回活动安排问题的相容活动数目对n个活动按结束时间的先后进行非递减排序;a[1]=true;//从选择活动1开始

intj=1;intcount=1;//计数器

for(inti=2;i<=n;i++){2贪心算法•活动安排问题的贪心算法2贪心算法

if(s[i]>=f[j]){//选择

a[i]=true;

j=i;

count++;

}//if

else

a[i]=false;

//丢弃

}//for

returncount;

}//Active_Selec

2贪心算法if(s[i]>=f[j]){//

例如，下面的一个实例。设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

i1234567891011S[i]130535688212f[i]45678910111213142贪心算法例如，下面的一个实例。设待安排的11个活动的开始时间和结

2贪心算法2贪心算法•对于上面的11个活动，应用贪心算法的计算，被选中的活动集和为A={1，4，8，11}。

•算法Active_Selec的效率很高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。2贪心算法•对于上面的11个活动，应用贪心算法的计算，被选中的【例2】Dijkstra单源最短路径问题。

•问题描述

有向赋权图G=(V,E)，求源顶点u到其它所有顶点的距离。设u,v是E中的边，Cu,v是边的长度。V划分为两个集合S和T：S中所包含的顶点，它们到u的距离已经确定；T中所包含的顶点，它们到u的距离尚未确定。P(x)是从顶点u到顶点x的最短路径中x的前驱顶点2贪心算法【例2】Dijkstra单源最短路径问题。2贪心算法•算法描述1.置S={u}，T=V-{u}；2.，若(u,x)∈E，则du,x=cu,x，p(x)=u；否则，du,x=∞，p(x)=-1；3.寻找t∈T，使得du,t=min{du,x|x∈T}，则；

就du,t是u到x的距离；4.S=S∪{t}，T=T-{t}；5.若T=Φ，算法结束；否则，转6；2贪心算法•算法描述2贪心算法6.对与t相邻接的所有顶点x，如果du,x≤du,t+ct,x，直接转3；否则，令

，du,x=du,t+ct,x

，p(x)=t，转3。例如，在如图的有向赋权图中，求顶点a到其它所有顶点的距离。2贪心算法6.对与t相邻接的所有顶点x，如果du,x≤du,t•如果用邻接表来存放顶点之间的距离，则邻接表如图所示。2贪心算法•如果用邻接表来存放顶点之间的距离，则邻接表如图所示。2•迪杰斯特拉算法的执行过程da,bda,cda,dda,eda,fda,gda,hda,tt1a144∞∞∞∞1b2a,b3410∞∞∞3c3a,b,c4967∞4d4a,b,c,d967∞6f5a,b,c,d,f87117g6a,b,c,d,f,g8108e7a,b,c,d,f,g,e99h8a,b,c,d,f,g,e,h2贪心算法•迪杰斯特拉算法的执行过程da,bda,cda,dda,e•各个顶点到顶点a的路径2贪心算法•各个顶点到顶点a的路径2贪心算法•数据结构定义

structadj_list{ //结点的数据结构

intv_num; //邻接顶点的编号

floatlen; //邻接顶点与该顶点的距离

structadj_list*next; //下一个邻接顶点

};2贪心算法•数据结构定义

2贪心算法•数据结构定义

typedefstructadj_listNODE;NODE node[n]; //邻接表头结点float d[n]; //顶点

到源顶点的距离

int p[n]; //最短路径上前驱顶点的编号BOOLs[n];//S[i]为真，顶点i标志在S中2贪心算法•数据结构定义

2贪心算法•Dijkstra算法#defineMAX_FLOT_NUM∞ //最大的浮点数voiddijkstra(NODEnode[],intn,intu,floatd[],intp[]){floattemp;inti,j,t;BOOL*s=newBOOL[n];NODE*pnode;2贪心算法•Dijkstra算法2贪心算法for(i=0;i<n;i++){ //初始化d[i]=MAX_FLOAT_NUM;s[i]=FALSE;p[i]=－1;}if(!(pnode=node[u].next))//源顶点与其它顶点不相邻接

return;while(pnode){ //预置与源顶点相邻接的顶点距离2贪心算法for(i=0;i<n;i++){ //初始d[pnode->v_num]=pnode->len;p[pnode->v_num]=u;pnode=pnode->next;}d[u]=0;s[u]=TRUE; //开始时,集合S仅包含顶点ufor(i=1;i<n;i++){temp=MAX_FLOAT_NUM;t=u;for(j=0;j<n;j++)//寻找距离u最近的顶点t2贪心算法d[pnode->v_num]=pnoif(!s[j]&&d[j]<temp){t=j;temp=d[j];}if(t==u)berak; //找不到,跳出循环

s[t]=TRUE; //否则,把t并入集合spnode=node[t].next; //更新与t相邻接的顶点到u的距离while(pnode){if(!s[pnode->v_num]&&d[pnode->v_num]>d[t]+pnode->len){2贪心算法if(!s[j]&&d[j]<td[pnode->v_num]=d[t]+pnode->len;p[pnode->v_num]=t;}pnode=pnode->next;}}deletes;}2贪心算法d[pnode->v_num]=d[t•算法分析

时间复杂性为O(n2)。

算法需要

工作空间O(n)。2贪心算法•算法分析2贪心算法□最小代价生成树问题•若连通图G=(V,E)，T是G的生成树。则生成树T有如下性质：性质1:T是不含简单回路的连通图；性质2:T中的每一对顶点u和v，恰好有一条从u到v的基本通路；性质3:若|V|=n，|E|=m，则m=n-1。性质4:在T中的任何两个不相邻接的顶点之间增加一条边，则得到T中唯一的一条基本回路。2贪心算法□最小代价生成树问题2贪心算法•

若图G是赋权图，T是G的生成树。T的每个树枝上的权之和称为T的权。G中权最小的生成树，称为G最小代价生成树、或最小生成树。•

假定图都是连通的。如果图不连通，可以把算法应用于图的每一个连通分支。2贪心算法•若图G是赋权图，T是G的生成树。T的每个树枝上的权•最小代价生成树原理

V是顶点集合，U是已选中顶点集合

U

权值最小V-U

2贪心算法•最小代价生成树原理2贪心算法【例3】Kruskal最小生成树问题。

•克鲁斯卡尔算法的思想1.所有顶点都作为孤立顶点，每个顶点构成一棵只有根结点的树，这些树构成森林T；2.所有边按权的非降顺序排序，构成边集的一个非降序列；3.从边集中取出权最小的边，如果把这条边加入森林T中，不会使

构成回路，就把它加入森林T中；否则，就放弃它。2贪心算法【例3】Kruskal最小生成树问题。2贪心算法4.重复这个过程，直到把n-1条边都放到森林T以后，结束这个过程，这时，森林T中所有的树就被连结成一棵树

，它就是所要求取的图的最小代价生成树。2贪心算法4.重复这个过程，直到把n-1条边都放到森林T以后，结束这•Kruskal算法描述1.按权的非降顺序排序E中的边；2.令最小代价生成树的边集为T，T初始化为：T=Φ

；3.把每个顶点都初始化为树的根结点；4.令e=(u,v)是E中权最小的边，E=E-{e}；5.如果find(u)≠find(v)，则执行union(u,v)操作，T=T∪{e}；6.如果|T|<n-1，转4；否则，算法结束。2贪心算法•Kruskal算法描述2贪心算法•克鲁斯卡尔算法的执行过程abcdegf5141827168213ae12dcbgf7148531621712182贪心算法•克鲁斯卡尔算法的执行过程abcdegf5141827168•数据结构

假定无向赋权图G=(U,E,W)有n个顶点，m条边。typedefstruct{ //边的数据结构floatkey; //边的权int u; //与边关联的顶点编号

int v; //与边关联的顶点编号

}EDGE;2贪心算法•数据结构2贪心算法•数据结构structnode{ //顶点的数据结构

structnode*p; //指向父亲结点

int rank; //结点的秩

int u; //顶点编号};typedefstructnodeNODE;EDGEE[m＋1],T[n];NODEV[n];2贪心算法•数据结构2贪心算法•克鲁斯卡尔算法voidkruskal(NODEV[],EDGEE[],EDGET[],intn,intm){inti,j,k;EDGEe;NODE*u,*v;make_heap(E,m); //用边集构成最小堆for(i=0;i<n;i++){ //每个顶点都作为树的根结点,构成森林

2贪心算法•克鲁斯卡尔算法2贪心算法V[i].rank=0;V[i].p=NULL;} i=j=0;while((i<n-1)&&(m>0){ e=delete_min(E,&m); //从最小堆中取下权最小的边u=find(&V[e.u]);//检索与边相邻接的顶点所在树的根结点

2贪心算法V[i].rank=0;V[i]v=find(&V[e.v]); if(u!=v){ //两个根结点不在同一棵树上

union(u,v); //连接它们

T[j++]=e; //把边加入生成树i++;}}}2贪心算法v=find(&V[e.v]); •算法分析

算法的运行时间为O(mlogm)。

对完全图，m=n(n-1)/2，花费的时间为O(n2logn)；

对平面图，m=O(n)，所花费的时间为O(nlogn)。

最小生成树边集所需空间为O(n)。其余工作单元为O(1)。2贪心算法•算法分析2贪心算法□克鲁斯卡尔算法正确性证明

•G是无向连通图，T*是最小代价生成树边集；T是由克鲁斯卡尔算法所产生的生成树边集。则G中的顶点，既是T*中的顶点，也是T中的顶点。•

若G的顶点数为n，则|T*|=|T|=n-1。

下面用用归纳法证明T*=T。1.设e1

是G中权最小的边，根据克鲁斯卡尔算法，有e1∈T。2贪心算法□克鲁斯卡尔算法正确性证明2贪心算法•若e1∈T*，因为T*是G的最小生成树，

和e1关联的顶点必是T*

中的两个不相邻接的顶点，把e1加入T*，将使T*构成唯一的一条回路。•

假定回路是e1，ea1，ea2…eak，且e1是这条回路中权最小的边。

令T**=T∪{e1}-{eai}，eai

是回路

中除

外的任意一条边。•边集T**仍然是G的生成树，且T**

的权小于或等于T*的权。2贪心算法•若e1∈T*，因为T*是G的最小生成树，2贪心算•

若T**的权小于T*的权，与T*是G的最小生成树的边集矛盾，所以，e1∈T*

；•若T**的权等于T*的权，则T**也是G的最小生成树的边集，且e1∈T**。

•

可用新的T*来标记T**。在这两种情况下，都有

。2.若e2

是G中权第二小的边，同理可证

，e2∈T，且e2∈T*

。2贪心算法•若T**的权小于T*的权，与T*是G的最小生成树的边集3.设e1，e2,…ek是T中前面k条权最小的边，且它们也属于T*，令ek+1是G中第k+1条权最小的边，ek+1∈T，但ek+1∈T*。

•

与ek+1关联的顶点也是T*中的两个不相邻接的顶点。把ek+1加入T*，将使T*构成唯一的一条回路。•假定回路是ek+1，ea1，ea2…eam，在

其中，必有一条边eai

，但eai∈T*，但eai∈T*。否则，根据性质4将存在回路。2贪心算法3.设e1，e2,…ek是T中前面k条权最小的边•e1，e2,…ek+1是T中前面k+1条权最小的边，

并且e1，e2,…ek都属于T，所以，eai

的权大于或等于ek+1

的权。

•

令T**=T∪{ek+1}-{eai}，则T**

仍然G是

的生成树，且T**的权小于或等于T*

的权。必有ek+1∈T*。4.设e1，e2,…ek是G中前面k条权最小的边，且它们都属于T

，也属于T*

，令ek+1是G中第k+1条权最小的边，且ek+1∈T，但ek+1∈T*。2贪心算法•e1，e2,…ek+1是T中前面k+1条权最小的•因为e1，e2,…ek+1都属于T，而ek+1∈T，

根据克鲁斯卡尔算法，必有e1，e2,…ek+1构成回路。•

因为e1，e2,…ek+也属于T*，若ek+1∈T*，将使T*存在回路。因此只有ek+1∈T*

。

•

综上所述，有T*=T。所以，克鲁斯卡尔算法正确性得证。2贪心算法•因为e1，e2,…ek+1都属于T，而ek+□相对贪心问题

【例4】发工资现金找零问题。•问题描述某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱,且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。2贪心算法□相对贪心问题2贪心算法•算法设计1)读取每人的工资。

2)对每一个人的工资，先尽量多地取大面额的币种，由大面额到小面额币种逐渐统计。

3)利用数组,将七种币值按降序存储在数组B。这样，七种币值就可表示为B[i],i=1,2,3,4,5,6,7。4)设置一个有7个元素的累加器数组S。2贪心算法•算法设计2贪心算法•算法分析算法的时间复杂性是O（n）。以上问题的背景是在我国,且这样的币种正好适合使用贪心算法。假若,某国的币种是这样的,共9种（100,70,50,20,10,7,5,2,1）在这样的币值种类下,再用贪心算法就行不通了,比如某人工资是140,按贪心算法140=100*(1张)+20*(2张)共需要3张,而事实上,只要取2张70面额的是最佳结果,2贪心算法•算法分析2贪心算法【例5】取数游戏。

•问题描述有2个人轮流取2n个数中的n个数，取数之和大者为胜。设计算法，让先取数者获胜，模拟取数过程。•问题分析

这个游戏一般假设取数者只能看到2n个数中两边的数,用贪心算法的情况:2贪心算法【例5】取数游戏。2贪心算法•例如若一组数据为：6,16,27,6,12,9,2,11,6,5用贪心策略每次两人都取两边的数中较大的一个数,先取者胜.以A先取为例：

取数结果为：

A6,27,12,5,11=61胜

B16,6,9,6,2=392贪心算法•例如2贪心算法•

但若选另一组数据16,27,7,12,9,2,11,6

仍都用贪心算法，先取者A败。取数结果为：

A16,7,9,11=43B27,12,6,2=47胜其实，若我们只能看到两边的数据，则此题无论先取还是后取都无必胜的策略。这时一般的策略是用近似贪心算法。2贪心算法•但若选另一组数据2贪心算法•但若取数者能看到全部2n个数，则此问题可有一些简单的方法，有的虽不能保证所取数的和是最大，但确是一个先取者必胜的策略。2贪心算法•但若取数者能看到全部2n个数，则此问题可有一些简单的方法•数学模型的建立NN个数排成一行，我们给这N个数从左到右编号，依次为1，2，…，N，因为N为偶数，又因为是我们先取数，计算机后取数，所以一开始我们既可以取到一个奇编号的数（最左边编号为1的数）又可以取到一个偶编号的数（最右边编号为N的数）。

2贪心算法•数学模型的建立2贪心算法•如果我们第一次取奇编号（编号为1）的数，则接着计算机只能取到偶编号（编号为2或N）的数；•如果我们第一次取偶编号（编号为N）的数，则接着计算机只能取到奇编号（编号为1或N-1）的数；•即无论我们第一次是取奇编号的数还是取偶编号的数，接着计算机只能取到另一种编号（偶编号或奇编号）的数。2贪心算法•如果我们第一次取奇编号（编号为1）的数，则接着计算机只能•算法设计

有了以上建立的高效数学模型，算法就很简单了，算法只需要分别计算一组数的奇数位和偶数位的数据之和，然后就先了取数者就可以确定必胜的取数方式了。以下面一排数为例：12310567894奇编号数之和为25（=1+3+5+7+9）偶编号数之和为30（=2+10+6+8+4）2贪心算法•算法设计2贪心算法□动态规划的概念

•在动态规划算法策略中，体现在它的决策不是线性的而是全面考虑不同的情况分别进行决策,并通过多阶段决策来最终解决问题。在各个阶段采取决策后,会不断决策出新的数据,直到找到最优解.每次决策依赖于当前状态,又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的。所以，这种多阶段决策最优化的解决问题的过程称为动态规划。

3动态规划□动态规划的概念3动态规划□动态规划的最优决策原理

•活动过程划分为若干个阶段，每一阶段的决策，依赖于前一阶段的状态，由决策所采取的动作，使状态发生转移，成为下一阶段的决策依据。•

动态规划的决策过程

最优性原理：无论过程的初始状态和初始决策是什么，其余决策都必须相对于初始决策所产生的状态，构成一个最优决策序列。

3动态规划□动态规划的最优决策原理3动态规划•最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；

而决策的具体结果及所产生的状态转移，却是由初始阶段开始进行计算的，然后向后递归或迭代，直到最终结果。

3动态规划•最优决策是在最后阶段形成的，然后向前倒推，直到初始阶段；•动态规划决策过程

3动态规划•动态规划决策过程3动态规划•令最优状态为s(2,22)，由此倒推：s(2,22)→p(2,22)→s(1,2)→p(1,2)→s0,

最优决策序列:p(1,2)→p(2,22)

状态转移序列：s0→s(1,2)→s(2,22)

•动态规划函数赖是决策的依据。动态规划函数可以递归地定义，也可以用递推公式来表达。整个决策过程，可以递归地进行，也可以用循环迭代的方法进行。3动态规划•令最优状态为s(2,22)，由此倒推：3动态规划□动态规划的基本性质

•动态规划算法的问题及决策应该具有三个性质：最优化原理、无后向性、子问题重叠性质。1)最优化原理(或称为最佳原则、最优子结构)。2)无后向性(无后效性)。

3)有重叠子问题。

3动态规划□动态规划的基本性质3动态规划•设计一个标准的动态规划算法的步骤

1)划分阶段按照问题的时间和空间特征，将问题划分为若干阶段，满足无后向性。

2)选择状态

将各阶段的不同状态表示出来。

3)确定决策并写出状态转移方程

根据相邻两个阶段的状态之间的关系确定决策方程和状态转移方程。

3动态规划•设计一个标准的动态规划算法的步骤3动态规划□动态规划的特点

•

在贪心算法中，每一步的选择，都凭着当前的状态作出在当前看来是最好的选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。这种选择，可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。动态规划方法则是对问题进行全面的规划处理，从而弥补了贪心法在这方面的不足。

3动态规划□动态规划的特点3动态规划•动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

3动态规划•动态规划算法与分治法类似，其基本思想也是将待求解问题分【例6】Fibonacci序列问题。

•算法1

Fibonacci序列问题的递归算法

intfibonacci(intn){//Fibonacci序列的递归算法

if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}//fibonacci

3动态规划【例6】Fibonacci序列问题。3动态规划

3动态规划3动态规划

•算法分析

由此可知，函数fibonacci()的计算量随n的增加而急剧增加，n=6时需要25次调用，n=10时需要177次调用，n=25时需要1974次调用。事实上，解决这样的问题并不需要付出如此高的代价，从图中可以看出，大量的调用过程是重复的，显然，此算法可以改进。3动态规划•算法分析3动态规划

•

算法2Fibonacci序列问题的非递归算法intfibo(intn){//Fibonacci序列的非递归算法

f0=0,fl=1;for(i=2；i<=n；i++){f=fl;fl=f+f0;f0=f;}//forreturnfl;}//fibo

3动态规划•算法23动态规划•

Fibonacci序列问题的递归算法的时间代价是n的指数函数，而非递归算法的时间代价为O(n)阶，问题的关键在于避免了重复计算。简单的递归算法都是一种自顶向下进行递归分解的过程，其中包含了大量的重复调用，在这种情况下采用动态规划方法特别有效。动态规划算法的一个特征是自底向上，它可以大幅度地减少计算代价。3动态规划•Fibonacci序列问题的递归算法的时间代价是•避免重复计算--备忘录方法由程序设置“备忘录”，每当计算出一个新的子结构的解时，都保存起来。当遇到一次递归时，判断是否已经计算，如果已经计算，只需取出先前保存的结果即可。这种方式与动态规划算法相比，要增加保存与检索中间结果的代价。下面是采用备忘录策略计算Fibonacci序列的自顶向下的递归程序。

3动态规划•避免重复计算--备忘录方法3动态规划•算法3Fibonacci序列问题的备忘录算法

intfibo_Memo(intn){//Fibonacci序列的备忘录算法

intdict[n]={0,0,…,0};//初始化数组

if(n<2)returnn;if(diet[n-1]=O)fl=fibo_Memo(n-1);elsefl=diet[n-1];

3动态规划•算法33动态规划

if(didt[n-2]=0)f2=fibo_Memo(n-2);elsef2=diet[n-2];dict[n]=f1+f2;return(fl+f2);}//fibo_Memo•

这个递归程序在n=6时仅调用7次，其他重复的部分由对数组dict[]进行的判定与查询操作取代。3动态规划if(didt[n-2]=0)3动态规划□多段特征的动态规划【例6】多段图的最短路径问题。•问题描述

是求从源点s到达终点t的最小代价的通路。

3动态规划□多段特征的动态规划3动态规划

•动态规划函数：

3动态规划•动态规划函数：3动态规划•决策过程

数组元素cost[i]：存放顶点i到达终点t的最小花费;

数组元素path[i]：存放顶点i到达终点t的最小花费通路上的前方顶点编号

数组route[n]：存放从源点i出发，到达终点t的最短通路上的顶点编号

第一阶段，确定第k-1段的所有顶点到达终点的花费最小的通路。3动态规划•决策过程3动态规划•第二阶段，用第一阶段的信息，确定第k-2段的所有顶点到达终点的花费最小的通路。

如此依次进行，直到最后确定源点s到达终点t的花费最小的通路。

最后，从源点s的path信息中，确定它的前方顶点编号p1

，从p1的path信息中，确定p1

的前方顶点编号p2，如此递推，直到终点。

3动态规划•第二阶段，用第一阶段的信息，确定第k-2段的所有顶点到•算法描述1.对所有的i，0≤i<n。把cost[i]初始化为最大值，path[i]初始化为-1；cost[n-1]初始化为0；2.令i=n-2；3.计算cost[i]和path[i]；4.i=i-1，若i≥0，转3；否则，转5；5.令i=0，route[i]=0；6.如果route[i]=n-1，算法结束；否则，转7；7.i=i+1，route[i]=path[route[i-1]]；转6。

3动态规划•算法描述3动态规划

•例如，如图，计算过程：i=8

,cost[8]=c89+cost[9]=3+0=3path[8]=9;

3动态规划•例如，如图，计算过程：3动态规划

i=7

,cost[7]=c79+cost[9]=7+0=7path[7]=9;i=6

,cost[6]=min{c67+cost[7],c68+cost[8]}=min{6+7,5+3}=3path[6]=8;

i=5

,cost[5]=min{c57+cost[7],c58+cost[8]}=min{8+7,6+3}=9path[5]=8;

3动态规划i=7,cost[7]=c79+cost[9]i=4

,cost[4]=min{c47+cost[7],c48+cost[8]}=min{5+7,6+3}=9path[4]=8;

i=3

,cost[3]=min{c35+cost[5],c36+cost[6]}=min{4+9,7+8}=13path[3]=5;i=2

,cost[2]=min{c23+cost[3],c24+cost[4]+c25+cost[5],c26+cost[6]}=min{1+13,6+9,7+9,8+8}=14path[2]=3;

3动态规划i=4,cost[4]=min{c47+costi=1

,cost[1]=min{c14+cost[4],c15+cost[5]}=min{9+9,6+9}=15path[1]=5;

i=0

,cost[0]=min{c01+cost[1],c02+cost[2]+c03+cost[3]}=min{4+15,1+14,3+13}=15path[0]=2;

3动态规划i=1,cost[1]=min{c14+costroute[0]=0

route[1]=path[route[0]]=path[0]=2

route[2]=path[route[1]]=path[2]=3

route[3]=path[route[2]]=path[3]=5

route[4]=path[route[3]]=path[5]=8

route[5]=path[route[4]]=path[8]=9•最短的路径为0，2，3，5，8，9

费用是15。

3动态规划route[0]=03动态规划

•思考一下，如何求此题的关键路径（最长路径）。拓扑序列：0-1-2-3-4-5-6-7-8-93动态规划•思考一下，如何求此题的关键路径（最长路径）。3动态规【例7】旅行售货商问题。

•问题描述

在有向赋权图G=(V,E)中，寻找路径最短的哈密尔顿回路问题。•问题分析

令

：从顶点i出发，经

中各顶点一次，最终回到顶点i的最短路径的长度，开始时，=V-{i}。3动态规划【例7】旅行售货商问题。3动态规划动态规划函数：

4个城市的费用矩阵是：

3动态规划动态规划函数：3动态规划

•根据规划函数公式，由城市1出发，经城市2,3,4然后返回1的最短路径长度为：

它必须依据

的计算结果：

3动态规划•根据规划函数公式，由城市1出发，经城市2,3,4然后返回

•这一阶段的决策，又必须依据下面的计算结果：再向前倒推，有：

3动态规划•这一阶段的决策，又必须依据下面的计算结果：3动态规划

•有了这些结果，再向后计算，有：

路径顺序是：2,3,4,1

路径顺序是：3,2,4,1

路径顺序是：4,3,2,1最后：路径顺序是：1,2,3,4,1

3动态规划•有了这些结果，再向后计算，有：3动态规划

•求解过程示意图

3动态规划•求解过程示意图3动态规划

•算法分析

令Ni

是计算从顶点i出发，返回顶点i所需计算的形式为

的个数。

开始计算

时，集合V-{i}中有n-1个城市。

以后，在计算

时，集合

的城市数目，在不同的决策阶段，分别为n-2,…,0。

3动态规划•算法分析3动态规划

在整个计算中，需要计算大小j为

的不同城市集合的个数为

，j=0,1,2,…,n-1。因此，总个数为：

当

集合中的城市个数为j时，为计算

，需j次加法，j-1次比较。从i城市出发，经其它城市再回到i，总的运算时间

为Ti：

3动态规划在整个计算中，需要计算大小j为的不同城市集合的•由二项式定理：令x=y=1；可得：

则用动态规划方法求解旅行售货商问题，总的花费T为：

3动态规划3动态规划□递推特征的动态规划【例8】最长公共子序列问题。

•问题描述若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

3动态规划□递推特征的动态规划3动态规划•

给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。

3动态规划•给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的

•问题分析-最长公共子序列的结构设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk}，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。

3动态规划•问题分析-最长公共子序列的结构3动态规划•由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。•由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。•由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。

3动态规划•由此可见，2个序列的最长公共子序列包含了这2个序列的前缀•动态规划函数

由最优子结构性质可建立递归关系如下：

3动态规划•动态规划函数3动态规划

•算法1-最长公共子系列的递归算法intNum=100

char

a[Num],b[Num],str[Num];main()

{intm,n,k;print

(“Enter

two

string”);

input(a,b);m=strlen(a);n=strlen(b),

k=lcs_len(n,m);//k为公共子序列的长度

3动态规划•算法1-最长公共子系列的递归算法3动态规划

buile_lcs(k,n,m);print(str);

}

•lcs_len(int

i，j)//计算最优值

{

if(i=0orj=0)

c[i][j]=0;elseif(a[i-1]=b[j-1])c[i][j]=

lcs_len(i-1，j-1)+1

;elsec[i][j]=max（lcs_len(i，j-1)，lcs_len(i-1，j);}

3动态规划

buile_lcs(k,n,m);3动

•buile_lcs(k,i,j);//构造最长公共子序列

{if（i=0orj=0）return;

if（c[i][j]=c[i-1][j]）buile_lcs(k,i-1,j);elseif（c[i][j]=c[i][j-1]）buile_lcs(k,i,j-1);else{str[k]=a[i-1];

buile_lcs(k-1,i-1,j-1);}}

3动态规划•buile_lcs(k,i,j);//构

j0123456c[i][j]=c[i-1][j]iyiBDCABA0xi00000001A00001112B0111122B3C0112222C4B0112233B5D01222336A0122334A7B0122344

c[7][6]=c[6][6]3动态规划j0123

•算法分析设计角度是从递推思想进行的,设计中只要找出大规模问题与小规模问题(子问题)之间的递推关系,最后一个子问题所得最优解就是原问题的最优解。

算法的时间复杂度是O(m×n)。

3动态规划•算法分析3动态规划

•算法2-最长公共子系列的非递归算法n=100

char

a[n],b[n],str[n];lcs_len(char

a[],

char

b[],

int

c[

][

n])//计算最优值

{int

m,n,i,j;print

(“Enter

two

string”);

input(a,b);

m=strlen(a);n=strlen(b);

3动态规划•算法2-最长公共子系列的非递归算法3动态规划for

(i=0;i<=m;i++)

c[i][0]=0;

for

(i=0;i<=n;i++)

c[0][i]=0;

for

(i=1;i<=m;i++)

for

(j=1;j<=m;j++)

if

(a[i-1]=b[j-1])

c[i][j]=c[i-1][j-1]+1;

else

if

(c[i-1][j]>=c[i][j-1])

c[i][j]=c[i-1][j];

else

c[i][j]=c[i][j-1];}

3动态规划for

(i=0;i<=m;i++)

buile_lcs()//构造最长公共子序列

{

int

k,i=strlen(a),j=strlen(b);

k=lcs_len();

str[k]=’’;

while

(k>0)

if

(c[i][j]=c[i-1][j])

i=i-1;

else

if

(c[i][j]=c[i][j-1])

j=j-1;

3动态规划buile_lcs()//构造最长公共子序列

{

intelse

{k=k-1;str[k]=a[i-1];

j=j-1;}

}

3动态规划else

3动态规划本课结束下课啦，休息一会儿！本课结束下课啦，第5课

贪心与动态规划

1贪心算法设计框架2相对贪心问题3绝对贪心问题4动态规划设计框架5多阶段特征动态规划6递推特征动态规划第5课贪心与动态规划1贪心算法设计框架□贪心策略选择•贪心法又叫登山法,它的根本思想是逐步到达山顶,即逐步获得最优解。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。一定要注意，选择的贪心策略要具有无后向性。•所谓无后向性，指某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为无后效性。2贪心算法□贪心策略选择2贪心算法□贪心算法的设计思想

•从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策,尽可能地求得最好的解。当达到某算法中的某一步不需要再继续前进时，算法停止。2贪心算法□贪心算法的设计思想2贪心算法•贪心策略的框架

从问题的某一个初始解出发逐步逼近给定的目标，每一步都作一个不可回溯的决策；尽可能地求出最好的可行解的一个解元素；

当达到某算法中的某一步不需要再继续前进时，算法停止；

由所有解组合成该问题的一个可行解。2贪心算法•贪心策略的框架2贪心算法□贪心算法的基本性质

•对于一个具体的问题，是否可以用贪心算法求解此问题，以及能否得到问题的最优解，对于这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有两个重要的性质：贪心选择性质和最优子结构性质。2贪心算法□贪心算法的基本性质2贪心算法

1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心法与动态规划法的主要区别。如活动安排问题、背包问题、单源最短路径问题等。

2贪心算法1.贪心选择性质2贪心算法

2.最优子结构性质该问题解的整体最优性依赖于其局部子问题解的最优性。这种性质是可以采用贪心算法解决问题的关键特征。例如，活动安排问题，在选择了一项活动后，它必须是最优的，否则不能得到全局的最优。

2贪心算法2.最优子结构性质2贪心算法□贪心算法的适用性

•贪心算法对问题只需考虑当前局部信息就要做出决策，也就是说使用贪心算法的前提是“局部最优策略能导致产生全局最优解”。

该算法的适用范围较小,若应用不当,不能保证求得问题的最佳解。更准确的方法是通过数学方法证明问题对贪心策略的选用性。2贪心算法□贪心算法的适用性2贪心算法

□绝对贪心问题【例1】会议室活动安排问题。

•活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单而又实用的方法使得公共资源尽可能多地得到利用。2贪心算法□绝对贪心问题2贪心算法

•

会议室活动安排问题的描述设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如会议室。而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi

。2贪心算法•会议室活动安排问题的描述2贪心算法•

如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，且sj≥fi时，则称活动i与活动j是相容的。•

活动安排问题就是要在活动所给的集合中，选出最大的的活动相容子集合。2贪心算法•如果选择了活动i，则它在半开时间区间[si,fi)内•两种不同的选择策略用贪心选择可以有两种不同的策略：选si最小的，这样可以增大场地的利用率；选fi最小的，使得下一个活动可以更早开始。由于活动的占用时间长度没有限制，根据问题的定义，选择后者更合理。2贪心算法•两种不同的选择策略2贪心算法

•适当的预处理

为了在每一次选择时取当前可以安排的活动中最早结束的活动，应当首先把n项活动按结束时间的先后进行非递减排序，即，使f1≤f2≤…≤fn，然后在si值不小于当前时刻的活动中取fi值最小者。

2贪心算法•适当的预处理2贪心算法•活动安排问题的算法描述

[1]对活动集E中的n个活动按结束时间的先后进行非递减排序，得到数组S[1..n]，f[l..n]，其中

f[1]≤f[2]≤…≤f[n]。

[2]选择活动1为开始活动，加入可选活动集。2贪心算法•活动安排问题的算法描述2贪心算法[3]从第2个活动开始，用开始时间与第1个活动的结束时间比较，若不小于，则选中；否则，依次选取后面的活动比较。[4]当活动i<=n时，重复[3]，但从当前被选中的活动开始。

2贪心算法[3]从第2个活动开始，用开始时间与第1个活动的结束时间比•

活动安排问题的贪心算法intActive_Selec(intn,int[]s,int[]f,boola[]){//返回活动安排问题的相容活动数目对n个活动按结束时间的先后进行非递减排序;a[1]=true;//从选择活动1开始

intj=1;intcount=1;//计数器

for(inti=2;i<=n;i++){2贪心算法•活动安排问题的贪心算法2贪心算法

if(s[i]>=f[j]){//选择

a[i]=true;

j=i;

count++;

}//if

else

a[i]=false;

//丢弃

}//for

returncount;

}//Active_Selec

2贪心算法if(s[i]>=f[j]){//

例如，下面的一个实例。设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

i1234567891011S[i]130535688212f[i]45678910111213142贪心算法例如，下面的一个实例。设待安排的11个活动的开始时间和结

2贪心算法2贪心算法•对于上面的11个活动，应用贪心算法的计算，被选中的活动集和为A={1，4，8，11}。

•算法Active_Selec的效率很高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。2贪心算法•对于上面的11个活动，应用贪心算法的计算，被选中的【例2】Dijkstra单源最短路径问题。

•问题描述

有向赋权图G=(V,E)，求源顶点u到其它所有顶点的距离。设u,v是E中的边，Cu,v是边的长度。V划分为两个集合S和T：S中所包含的顶点，它们到u的距离已经确定；T中所包含的顶点，它们到u的距离尚未确定。P(x)是从顶点u到顶点x的最短路径中x的前驱顶点2贪心算法【例2】Dijkstra单源最短路径问题。2贪心算法•算法描述1.置S={u}，T=V-{u}；2.，若(u,x)∈E，则du,x=cu,x，p(x)=u；否则，du,x=∞，p(x)=-1；3.寻找t∈T，使得du,t=min{du,x|x∈T}，则；

就du,t是u到x的距离；4.S=S∪{t}