算法设计(第8章迭代改进法).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,8,章 迭代改进法,线性规划与单纯形法,二部图匹配,最大流,8.1,线性规划与单纯形法,营养搭配问题,食物,碳水化合物,蛋白质,脂肪,A,100,90,150,￥,24,B,125,150,60,￥,20,75,60,60,8.1,线性规划与单纯形法,营养搭配问题,x,1,x,2,x,1,=6/19,x,2,=4/19,8.1,线性规划与单纯形法,线性规划问题（标准型）,标准化,:,(1),极大值,极小值,:,目标函数系数取反,(2),不等式约束,等式约束,:,增加约束变量,(3),正数范围限制,:,变量平移,8.1,线性规划与单纯形法,线性规划问题,x,1,=200/3,x,2,=100/3,8.1,线性规划与单纯形法,线性规划问题,问题的可行域,:,n,维空间中的一个凸多边形（凸集）,问题的最优解总,:,在凸多边形的顶点上获得,8.1,线性规划与单纯形法,单纯形法,求出一个基本可行解,不存在改进可能则结束,否则进行变换，转到下一个更优的顶点，而后继续上一步,8.2,二部图匹配,二部图,G,=,匹配,a,1,a,2,a,3,a,4,a,5,b,1,b,2,b,3,b,4,8.2,二部图匹配,二部图,G,=,匹配,a,1,a,2,a,3,a,4,a,5,b,1,b,2,b,3,b,4,8.2,二部图匹配,迭代改进法,找到任意一个匹配（如空匹配）,不存在改进可能则结束,寻找一个更大的匹配并继续上一步,a,1,a,2,a,3,a,4,a,5,b,1,b,2,b,3,b,4,寻找增广路径,8.2,二部图匹配,迭代改进法,交错路径,:,路径中,任意两条相邻的边都是一条属于,M,而另一条不属于,M,增广路径,:,起点和终点都不在,M,中,的,交错路径,a,1,a,2,a,3,a,4,a,5,b,1,b,2,b,3,b,4,8.2,二部图匹配,Algorithm,BipartiteMatching(A,B:set;E:set),begin,let M=E0;/,初始匹配,let Q=A E0.a;,while(|Q|0)do,let u=Q0;,let P=Augment(u,A,B,E,M);,if(P=null)then,then Q,Q u;,else,M,M,P;,Q,A e.a|e,M;,return M;,end,迭代改进法,8.3,最大流,流网络,定义,:,流网络,G,=,是一个有向图，其中每条边,(,u,v,),E,上的权值,c,(,u,v,)0,表示允许通过的最大容量。网络中存在两个特殊的顶点：源点,s,和汇点,t,网络中的流,:,实值函数,f,:,V,V,R,，其满足,f,(,u,v,),c,(,u,v,),，,f,(,u,v,)=,f,(,v,u,),；,除,s,和,t,外,，,其它任意顶点,u,满足,流守恒,特性,v,V,f,(,u,v,)=0,8.3,最大流,最大流问题,输入：一个流网络,G,=,，其源点和汇点分别为,s,和,t,输出：,G,中从,s,到,t,的最大值流,f,8.3,最大流,迭代改进法,初始时令,f,为一个空流,如不能再增加流量则结束,对流进行扩充并继续上一步,寻找增广路径,8.3,最大流,迭代改进法,残留网络,:,由,f,导出的,G,的残留网络为,G,f,=,，其中,E,f,=(,u,v,),E,|,c,f,(,u,v,)0,c,f,(,u,v,)=,c,(,u,v,),f,(,u,v,),引理,8.1:,设,若,G,f,是由,f,导出的,G,的残留网络，且,f,为,G,f,中的一个流,，,那么,f,+,f,是,G,中的一个流，其值,|,f,+,f,|=|,f,|+|,f,|,推论,8.1:,设,P,是,G,f,中的一条增广路径，那么,f,=,f,+,f,P,是,G,中的一个流，且,|,f,|,f,|,8.3,最大流,Algorithm,Ford-Fulkerson(V:set;E:set;c:int,;s,t:int),begin,let n=|V|,m=|E|,f=new intn,n,f=new intn,n;,foreach(u,v),E do,fu,v,0;fv,u,0;/,初始流为,0,let f=c,E=E,P=Path(V,E,s,t);/,增广路径,while(,P,null)do,let c=(Min(u,v):(u,v),P:fu,v);,foreach(u,v),E do/,压入增广路径上的流,fu,v,fu,v+c;fv,u,fu,v;,foreach(u,v),E do,if(fu,v0)then fv,u,cv,u+fu,v;E,E,(v,u);,P,Path(V,E,s,t);/,继续查找增广路径,return M;,end,迭代改进法,8.3,最大流,最小割问题,输入：一个流网络,G,=,，其源点和汇点分别为,s,和,t,输出：,G,中具有最小容量值的割,(,S,T,),8.3,最大流,最大流,/,最小割定理：,设,G,=,是源点为,s,、汇点为,t,的一个流网络，,f,是,G,中的一个流，则下列条件是等价的：,f,是,G,的一个最大流,残留网络,G,f,中不包含增广路径,对,G,的某个割,(,S,T,),，有,|,f,|=,c,(,S,T,),