云南大学报告问题、模型与算法.ppt

问题、模型与求解算法,云南大学数学系李建平二OO九年十一月,内容摘要,基础知识最小支撑树问题最短路问题匹配问题欧拉问题中国邮递员问题一些可计算性为NP-完备的组合最优化问题及数学模型,一、基础知识,1.1图与支撑子图定义1.1所谓一个（无向）图是指给了一个集合V，以及V中的不同元素的无序对构成的集合E，并记图为G=(V，E)。称V中的元素为图G的顶点，称E中的元素为图G的边。连接两顶点u和v的边记作uv（或者vu），也称边uv（或者vu）与顶点u,v相关联，同时称两顶点u和v是相邻的。,太原,重庆,武汉,南京,徐州,连云港,上海,郑州,石家庄,塘沽,青岛,济南,天津,北京,图1.1,定义1.2所谓一个有向图是指给了一个集合V，以及V中的不同元素的有序对构成的集合A，并记有向图为D=(V，A)。称V中的元素为有向图D的顶点，称A中的元素为有向图D的弧。以顶点u为起点和以顶点v为终点的弧记作（u，v），也称与弧（u，v）与顶点u,v相关联。,v3,v1,v2,v4,v6,v5,图1.2,定义1.3给定两个图G=(V,E)和H=(V*,E*)，称H是G的一个支撑（生成）子图，如果V*=V和E*E。1.2图的连通性定义1.4（路）给定图G=(V,E)，一个点、边交错的序列P=（v0,e1,v1,e2,v2，e3,v3,vk-1,ek,vk)，如果满足ei=vi-1vi,i=1,2,k,则称P为一条连结v0和vk的路，简记为P=v0v1v2v3vk-1vk；称v0，vk分别称为路P的起点和终点，其余称为中间点。,定义1.5（回路）设P为一条连结v0和vk的路，如果v0=vk，称该路P为回路；如果v0vk，称该路P为(严格的)路。定义1.6（圈）如果路P除起点和终点相同，中间所含的点均不相同，称这样的回路P为圈。定义1.7（连通图）如果图G中任意两点之间均至少有一条路相连，称G为连通图；否则称图为不连通图。问题1.1：给定图G，问G是连通的吗？,二、最小支撑树问题,2.1树定义2.1一个无圈的连通图称为树。树具有如下一些性质：性质2.1设图G=（V，E）是一棵树，n2，则图G中至少有两个悬挂点。性质2.2图G=（V，E）是一棵树的充要条件是G不含圈，并且有且仅有n-1条边。性质2.3图G=（V，E）是一棵树的充要条件是G是连通图，并且有且仅有n-1条边。性质2.4图G是一棵树的充分必要条件是任意两个顶点之间有且仅有一条路。,2.2支撑树定义2.2设图T=(V,E)是图G=(V,E)的一个支撑子图，如果图T=(V,E)是一棵树，那么称T是G的一棵支撑树。,v6,v5,v2,v3,v4,v1,图2.1,（a）,（b）,v6,v5,v3,v1,v2,v4,2.3最小支撑树问题定义2.3设有图G=（V，E；w），如果对于G中的每一条边vivj，相应地有一个数wij，那么称这样的图G为赋权图，wij称为边vivj的权。这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。,定义2.4如果图T=（V，E）是赋权图G的一棵支撑树，那么E中所有边的权重之和称为支撑树T的权重，记作w(T)。如果图G中支撑树T*的权重w(T*)是在G的所有支撑树T中的权重达到最小者，即w(T*)=minw(T)|T为G的支撑树，那么称T*是G的一棵最小支撑树。类似可定义最大支撑树问题。问题2.1：给定图G，如何求G的一棵最小支撑树？,常用的有破圈算法和避圈算法：Algorithm破圈算法Input:赋权图G=（V，E；w）Output:G的最小支撑树TBegin在图中寻找一个圈。若不存在圈，则已经得到最小支撑树或说明该图不连通，后者不存在支撑树（当然没有最小支撑树）；若存在圈，去掉该圈中权数最大的边；反复重复、两步，直到找到最小支撑树或说明该图不连通（故没有最小支撑树）。End,v6,v5,v2,v3,v4,（a）,v1,6,2,7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,（b）,图2.2,避圈算法：从图中依次寻找权重较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权重边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最小支撑树或者说明该图不连通，后者不存在支撑树（当然没有最小支撑树）。,2.4顶点加细限制性的最小支撑树问题定义2.5给定图G=（V，E），在G的某些边内部增加一些顶点，所得到的新图称为原图G的顶点加细图（subdivision）。问题2.2（顶点加细限制性的最小支撑树问题）给定赋权图G=（V，E；w）及常数d，寻找图G的一棵最小支撑树T，在T上增加尽可能少的顶点，使得到新的（最小）顶点加细支撑树T*上每条边的权重不超过给定的常数d。,顶点加细限制性的最小支撑树问题的算法(1).利用已有的算法，对赋权图G求最小支撑树T，记T上权重大于d的边为ei1,ei2,eik;(2).对边eij按照下面方式插入insert(eij)顶点，其中当w(eij)是d的倍数，取insert(eij)=w(eij)/d-1，当w(eij)不是d的倍数，取insert(eij)=w(eij)/d；(3).输出支撑树T及插入的顶点。,定理2.1（李建平等，TheoreticalComputerScience410(2009),877-885）上述算法能够求得顶点加细限制性的最小支撑树问题的最优解，其算法复杂性就是求最小支撑树问题的算法复杂性。,问题2.3（顶点加细限制性的支撑树问题）给定赋权图G=（V，E；w；c），及常数B和d，寻找图G的一棵支撑树T，满足（1）eTw(e)B；（2）支撑树T的顶点加细图T*上每条边的权重不超过给定的常数d。其目标是使得eTinsert(e)c(e)到达最小。,定理2.2（李建平等，TheoreticalComputerScience410(2009),877-885）顶点加细限制性的支撑树问题是NP-完备的；上述问题多项式等价于限制性的最小支撑树问题（SIAMJournalonComputing,Vol.33,no.2,261-268,2004）；我们能够设计多项式时间算法解决顶点加细限制性的支撑树问题的三种特殊情形，其算法复杂性就是求最小支撑树问题的算法复杂性。,三、最短路问题,3.1最短路问题定义3.1设有赋权图G=（V，E;w），vs,vt是G中的两个顶点，P是G中从vs到vt的任意一条路，路P的权重是指P中所有边的权重之和，记作w(P)。问题3.1（最短路问题）在所有从vs到vt的路中，寻找一条权重最小的路P0，即w(P0)=minw(P)。P0称为从vs到vs的最短路。P0的权重w(P0)称为从vs到vt的距离，记作d（vs，vt）。类似可定义赋权有向图D中的最短路问题。,3.2反圈定义3.2给定（无向）图G=（V,E;w）,若SV，集合称为由S确定的反圈（anticircuit）。类似地，有向图D=（V，A）,若SV，集合称为由S确定的正向反圈，集合称为由S确定的反向（或逆向）反圈。,3.3一般形式的反圈算法给定图G=（V，E），设X(k),E(k)分别是V,E的子集合（初始k=0时，取X(0)是V的某个非空子集合,E(0)为空集合）。若由X(k)确定的反圈不为空集合，根据某些确定的限制条件，从该反圈中选取一条或多条边，使得这些所选边在V-X(k)中的端点互不相同。记被选边的集合为F(k)，它们在V-X(k)中的端点集合为Y(k)。令对，重复上述过程或者终止。,3.4利用反圈算法求解最短路问题(1)初值X(0)=vs，L(vs)=0;(2)在中选一条边vivj,使得L(vi)+w(vi,vj)=minL(vi)+w(vi,vj)令L(vj)=L(vi)+w(vi,vj)。(3)当出现下面情形之一时，停止。当，得到从vs到vt的最短路；当，但是，说明没有从vs到vt的（最短）路。,3.5顶点加细限制性的最短路问题定义3.3（顶点加细限制性的最短路问题）给定赋权图G=（V，E；w；vs,vt），及常数d，寻找图G中从vs到vt的一条最短路P(vs,vt)，在P(vs,vt)上增加尽可能少的顶点，使得到的最短路P(vs,vt)上每条边的权重不超过给定的常数d。,顶点加细限制性的最短路问题的（标号）算法：(1)取X(0)=vs，E(0)=空集，L(vs)=0；(2)在X(k)确定的反圈中选取满足条件的全部边uv放入F(k)，这里u属于X(k)，v不属于X(k)L(u)+w(u,v)=minL(u)+w(u,v)|u属于X(k)，v不属于X(k)直到vt属于某个X(k),转(3)；或者无边可选（停止）；,(3)当存在vt属于某个X(k)，在E(k)中（递归）去掉那些不能到达vt的顶点及其关联的边；(4)在新图Gk=(X(k),E(k)中构造新的权重，对边e属于E(k)，当w(e)d时，取w(e)=0，当w(e)d时，取w(e)=insert(e)，其中当w(e)是d的倍数，取insert(e)=w(e)/d-1，当w(e)不是d的倍数，取insert(e)=w(e)/d；,(5)相应地，在新图Gk=(X(k),E(k)中，对边e属于E(k)，当w(e)d时,插入insert(e)个新的顶点；(6)在新图Gk=(X(k),E(k)中按照新的权重w，计算从vs到vt的一条最短路P(vs,vt)；(7)输出最短路P(vs,vt)及插入的顶点，这里最短路P(vs,vt)关于w的权重就是所求路的权重，关于w的权重就是所增加定点的数目。,定理3.1（李建平等，submittedtoAlgorithmica2007）上述算法能够求得限制性的最短路问题的最优解，其算法复杂性就是求最短路问题的算法复杂性。,问题3.4（顶点加细限制性的最短路问题）给定赋权图G=（V，E；w，c;vs,vt），及常数B和d，寻找图G中从vs到vt的一条路P(vs,vt)，满足（1）eP(vs,vt)w(e)B；（2）使得路P(vs,vt)的顶点加细图中每条边的权重不超过给定的常数d。其目标是使得（费用）eP(vs,vt)insert(e)c(e)到达最小。,定理2.2（李建平等，submittedtoAlgorithmica，2007）顶点加细限制性的最短路问题是NP-完备的；上述问题多项式等价于限制性的最短路问题（MathematicsofOperationsResearch,vol.17,no.1,36-42,1992）；当B表示图G中从vs到vt的最短路长度时，我们能够设计多项式时间算法解决该问题；当只计算顶点加细的数目时，我们能够设计多项式时间算法解决该问题。,四、匹配问题,4.1背景在生活中经常会遇到这样的问题，如某单位需要指派n个人去完成n项任务，每个人只做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成n项任务的总效率最高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题(AssignmentProblem)。,求解这样的问题时，需要引入变量xij,其取值只能是1或0，并令：当问题是要求极小化时的数学模型是：,4.2匹配问题定义4.1给定图G=（V，E），如果M是E的子集合，当M中任意两条边都不相邻，则称M是图G的一个匹配(matching)。当图G的匹配M的元素个数恰好为顶点数的一半时，称M是图G的完美匹配。,问题4.1（最大基数匹配问题）寻找图G的匹配M，使得M中含的元素个数最多。问题4.2（最优匹配问题）对于赋权图G=（V，E;w），寻找图G的匹配M，使得M中含的元素的权重之和最大。问题4.3（最小或最大完美匹配问题）对于赋权图G=（V，E;w），寻找图G的完美匹配M，使得M中含的边的权重之和达到最小（或最大）。,4.3求解二部图匹配设G=（S，T；E）是二部图，能够用反圈算法来解决二部图最大匹配问题：设M为当前已有的匹配，(1)初始k=0时，令X(0)=|v是关于M的非饱和顶点；(2)在中选边的原则为如果，则选以vi为顶点的非饱和边如果，则选以vi为顶点的饱和边；,(3)在某一步，当出现下面情形之一时停止：情形1：X(k)中有非饱和的T型点，此时有关于M的增广路，则可增广匹配M（重复步骤(2)）；情形2情形1没有出现，但是由X(k)确定的反圈中无边可选，此时没有关于M的增广路，则M是最大匹配。,定理4.1：设G是一个图，M是G的一个匹配，则M是G的最大匹配当且仅当G中不存在关于匹配M的增广路。4.3求解赋权二部图完美匹配：匈牙利算法（或最小费用最大流问题的算法）4.4求解一般图匹配：Edmonds算法4.5求解一般赋权图匹配：Edmonds算法,五、欧拉问题,5.1背景德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图5.1所示。1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。,A,B,图5.1,C,D,图5.2,A,C,D,B,5.2欧拉问题定义5.1给定一个图G=（V，E），如果存在一条回路C经过每条边恰好一次，称这样的图G是欧拉图。回路C被称为欧拉回路。问题5.1（欧拉问题）对于给定的图G=（V，E），判断图G是否是欧拉图？定理5.1（欧拉定理）图G是欧拉图当且仅当G是连通图，并且G的每个顶点的度为偶数。,1921年，Fleury提供了一个有效的算法来寻找图G的欧拉回路。以Pk=v1v2vkvk+1表示第k步得到的路，记Gk=GE-E(Pk)，如下进行第k+1步：在Gk中选一条边ek+1=vk+1vk+2，使得ek+1不是图Gk的割边（除非dGk(vk+1)=1)。令Pk+1=v1v2vkvk+1vk+2，及Gk+1=GE-E(Pk+1)，直到没有边可选。,5.3一笔画问题问题5.2（一笔画问题）对于给定的图G=（V，E），问G是否存在一条路P经过每条边恰好一次？如果G存在这样的一条路，称G是可一笔画的。这时，也称图G是M图。定理5.2图G是可一笔画的当且仅当G是连通图，并且G中至多存在两个顶点的度为奇数。,六、中国邮递员问题,6.1中国邮递员问题1960年，中国的数学家管梅谷教授提出如下问题：一个邮递员，每次送信都要走遍他负责的投递范围内的每条街道，完成投递任务后回到邮局，问他应该按照何路线投递信件，使得所走的总路程之和达到最小？,把这个问题抽象为图的问题，就是对于给定的连通赋权图G=（V，E;w），要寻找G的一个闭回路C，要求C经过每条边至少一次，使得闭回路C中的边权重之和达到最小。管梅谷教授在1960年给出了一个判定闭回路C是否是最优的一个充分必要条件，但是没有设计出有效的算法；Edmonds和Johnson于1973年给出了一个有效的算法来完整地解决了中国邮递员问题。,Edmonds-Johnson算法：(1)在赋权图中找到所有度为奇数的顶点（共有偶数个），如v1,v2,v2r-1v2r，并且计算这2r个奇数顶点之间的最短路及其长度；(2)在以这2r个顶点为新的顶点构造完全图H2r，在完全图H2r中，顶点vi与vj之间的边权重定义为图G中vi与vj之间的最短路长度。,(3)在完全图H2r上寻找权重最小的完美匹配M，每条匹配边对应于图G中的一条最短路，把得到的r条最短路叠加到赋权图G上，就得到新的赋权图G*（这是一个欧拉图）；(4)对新的赋权图G*，利用求欧拉回路的算法(Fleury)能够找到一条欧拉回路C，这条回路C就是图G上的中国邮递员问题的最优解（最优路线）。,七、NP-完备的组合最优化问题,7.1哈密尔顿问题(HamiltonianProblem)定义7.1设给定一个图G=（V，E），C是一个圈，如果C经过G的每个顶点恰好一次，则称C是图G的哈密尔顿圈，也称图G是哈密尔顿图。问题7.1（哈密尔顿问题）对于给定图G，问G是否含有哈密尔顿圈？即G是否是哈密尔顿图？,7.2货郎担问题(TravellingSalesmanProblem)设给定一个赋权的完全图G=（V，E；w），寻找G的一条闭回路C经过所有的顶点（该回路C可以经过某些顶点多次），使得闭回路C上边的权重之和达到最小。一般地，货郎担问题没有近似值为f(n)的近似算法，对于满足三角不等式的完全图G，存在近似值为2和3/2的近似算法（树算法与Christofides算法）。,7.3排序问题（SchedulingProblem)给定m台功能相同的机器，设有n件需要加工的任务，其加工时间分别为p1,p2,pn，每件任务要不间断地在某台机器上加工完成，问：如何安排加工任务的顺序（称为方案），使得把全部任务加工完毕所需时间达到最小。存在近似值为2-1/m和4/3-1/3m的近似算法。,7.装箱问题（Bin-PackingProblem）给定n个大小分别为a1,a2,an的物品，把它们放入容量为1的多个箱子之中，要求每个箱子中所放数之和不超过该箱子的容量1，问：如何安排装箱顺序，使得需要的箱子数目尽可能少。该问题不存在近似值为3/2-k的近似算法，这里k是大于的任意正数。存在多个近似算法来解决该问题，其近似值为2或3/2。,7.背包问题(KnapsackProblem)给定一个背包，其容量为，设有n件物品，每件物品的容量分别为a1,a2,an，当把这些物品放入背包之中，产生的效益分别为p1,p2,pn，问：如何安排装物体的顺序（称为方案），满足装入背包的物品容量之和不超过容量，使得产生的效益之和达到最大。存在全多项式近似方案PTAS(polynomial-timeapprximationscheme)。,7.最小点覆盖问题设给定一个图G=（V，E），寻找的一个子集合，使得中每条边的两个顶点至少有一个要属于，称是图的一个点覆盖。最小点覆盖问题:就是要寻找点覆盖，使得|S|达到最小。存在近似值为2的近似算法来解决该问题（匹配、LP）。利用匹配算法，能够解决二部图的最小点覆盖问题。,7.染色问题给定图（，），所谓的一个k点染色是指把划分为k个子集V1,V2,Vk,使得集合Vi中的点染成颜色i，并且集合Vi是独立集。点染色问题就是求这样的最小正整数k。给定图（，），所谓的一个k边染色是指把划分为k个子集1,E2,Ek,使得集合Ei中的边染成颜色i，并且集合Ei是匹配。边染色问题就是求这样的最小正整数k。,7.平面图的面染色问题给定平面图（，），所谓的一个k面染色是指把的所有面划分为k个子集F1,F2,Fk,使得集合Fi中的面染成颜色i，任何有公共边的两个面具有不同的颜色。面染色问题就是求这样的最小正整数k。四色猜想(定理)：任何平面图可以-面染色。(1979)五色定理：任何平面图可以-面染色。(1890),谢谢！,