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

问题、模型与求解算法 云南大学数学系 李建平 二OO九年十一月 内容摘要 l基础知识 l最小支撑树问题 l最短路问题 l匹配问题 l欧拉问题 l中国邮递员问题 l一些可计算性为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 v2v4 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=v0 v1v2v3 vk-1vk；称v0 ，vk分别称为路P的起点和终点，其余称为中间点。 定义1.5（回路）设P为一条连结v0和vk 的 路，如果v0 = vk，称该路P为回路；如果v0 vk，称该路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的最小支撑树T Begin 在图中寻找一个圈。若不存在圈，则已 经得到最小支撑树或说明该图不连通，后者 不存在支撑树（当然没有最小支撑树）； 若存在圈，去掉该圈中权数最大的边； 反复重复、两步，直到找到最小支 撑树或说明该图不连通（故没有最小支撑树 ）。 End v6 v5 v2 v3 v4 （a） v1 6 2 7 5 3 5 4 4 v3 v2 v1 v4 v6 v5 5 1 31 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（李建平等，Theoretical Computer Science 410 (2009), 877-885）上 述 算法能够求得顶点加细限制性的最小支撑树 问题的最优解，其算法复杂性就是求最小支 撑树问题的算法复杂性。 问题2.3（顶点加细限制性的支撑树问题 ） 给定赋权图G =（V，E；w；c），及常数B 和d，寻找图G的一棵支撑树T，满足（1） eTw(e) B；（2）支撑树T的顶点加细图 T*上每条边的权重不超过给定的常数d。其 目标是使得eT insert(e) c(e)到达最小。 定理 2.2（李建平等，Theoretical Computer Science 410 (2009), 877-885） 顶点加细限制性的支撑树问题是NP-完备 的； 上述问题多项式等价于限制性的最小支 撑树问题（SIAM Journal on Computing, 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）, 若S V，集合 称为由S确定的反圈（anticircuit）。 类似地，有向图D=（V，A）,若S V， 集合 称为由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（李建平等，submitted to Algorithmica 2007）上述算法能够求得限制 性的最短路问题的最优解，其算法复杂性就 是求最短路问题的算法复杂性。 问题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（李建平等，submitted to Algorithmica，2007） 顶点加细限制性的最短路问题是NP-完备 的； 上述问题多项式等价于限制性的最短路 问题（Mathematics of Operations Research, vol.17, no.1, 36-42, 1992）； 当B表示图G中从vs到vt的最短路长度时， 我们能够设计多项式时间算法解决该问题 ； 当只计算顶点加细的数目时，我们能够 设计多项式时间算法解决该问题。 四、匹配问题 4.1 背景 在生活中经常会遇到这样的问题，如某单 位需要指派 n 个人去完成 n 项任务，每个人只 做一项工作，同时，每项工作只由一个人完成 。由于各人的专长不同，每个人完成各项任务 的效率也不同。于是产生了应指派哪一个人去 完成哪一项任务，使完成 n 项任务的总效率最 高（如所用的时间为最少）。我们把这类问题 称之为指派问题或分派问题(Assignment Problem)。 求解这样的问题时，需要引入变量 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年瑞士科学家欧拉发表了关于图论 方面的第一篇科学论文，解决了著名的哥尼 斯堡七座桥问题。 AB 图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+1 vk+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 哈密尔顿问题(Hamiltonian Problem) 定义7.1 设给定一个图G=（V，E），C 是一个圈，如果C经过G的每个顶点恰好一 次 ，则称C是图G的哈密尔顿圈，也称图G是 哈 密尔顿图。 问题7.1（哈密尔顿问题）对于给定图G ，问G是否含有哈密尔顿圈？即G是否是哈 密 尔顿图？ 7.2 货郎担问题(Travelling Salesman Problem) 设给定一个赋权的完全图G=（V，E； w），寻找G的一条闭回路C经过所有的顶 点 （该回路C可以经过某些顶点多次），使得 闭回路C上边的权重之和达到最小。 一般地，货郎担问题没有近似值为f(n) 的 近似算法，对于满足三角不等式的完全图G ，存在近似值为2和3/2的近似算法（树算法 与Christofides算法）。 7.3 排序问题（Scheduling Problem) 给定m台功能相同的机器，设有n件需 要 加工的任务，其加工时间分别为p1, p2, pn ，每件任务要不间断地在某台机器上加工完 成，问：如何安排加工任务的顺序（称为方 案），使得把全部任务加工完毕所需时间达 到最小。 存在近似值为2-1/m和4/3-1/3m的近似算 法。 7. 装箱问题（Bin-Packing Problem） 给定n个大小分别为a1, a2, an的物品 ， 把