组合优化问题简介ppt课件.ppt

《组合优化问题简介ppt课件.ppt》由会员分享，可在线阅读，更多相关《组合优化问题简介ppt课件.ppt（108页珍藏版）》请在三一办公上搜索。

1、,关秀翠,东南大学数学系,组合优化问题(Combinatorial Optimization Problems),运 筹 学 (Operations Research),Introduction,引入数学方法解决实际问题 -定性与定量方法结合系统与整体性 -从全局考察问题应用性 -源于实践、为了实践、服务于实践交叉学科 -涉及经济、管理、数学、工程和系统等 多学科开放性 -不断产生新的问题和学科分支多分支 -问题的复杂性和多样性,运筹学的性质与特点,线性规划,数学规划,非线性规划,整数规划,动态规划,学科内容,多目标规划,双层规划,组合优化,最优计数问题,网络优化,排序问题,统筹图,随机优化,

2、对策论,排队论,库存论,决策分析,可靠性分析,运筹学的主要内容,运筹数学,系统工程,管理与运筹学,问题与方法,方法与应用,核心算法与工具,基础理论,应用理论,应用技术,运筹学,运筹学的学科地位,模型要素 变量可控因素 目标优化的动力和依据 约束内部条件和外部约束研究方法,建模,最优性条件,算法,灵敏度分析,最优化模型,组合优化问题简介,线性规划问题,几种组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,最小费用流问题,算法复杂性简介,什么是计算？,分析问题：抓住本质（抽象法）一些符号记在某种器具上，计算的行为随着作为各步结果的各种特定符号而变化。,因此计算可抽象成在线性带上

3、的0、1串执行以下指令：1. 写符号0；2. 写符号1；3. 向左移一格；4. 向右移一格；5. 观察当前符号以确定下一步；6. 停止。,一个线性的纸带或磁带，带中可加格子,8,Church-Turing Thesis,Every effective computation or algorithm can be carried out by a Turing Machine.,Turing, Alan (1912-1954),Effective Computation,Algorithm,Any computer program,Truing Machine,9,What Can be Do

4、ne by a Computer?,Problem Solvability,What computers can?,What computers cant?,10,11,An algorithm is a finite sequence of unambiguous instructions for solving a well-specified computational problem.Important Features:Finiteness.Definiteness.Effectiveness.,What is an Algorithm?,Brute forceDivide and

5、conquerDecrease and conquerTransform and conquerSpace and time tradeoffs,Greedy approachDynamic programmingBacktracking Branch and bound,Two main issues related to algorithms,How to design algorithms?,How to analyze an algorithm?,1. Is it correct?2. How are the time and space efficiencies of the alg

6、orithm? 3. And can we do better?,T(n) cop C(n),Running time expression should be machine-independent.Most use Random Access Machine (RAM) model .,Running time of an algorithm for a given input is the number of steps executed by the algorithm on that input.,Running Time,13,Worst Case Efficiency: The

7、algorithm runs the longest among all possible inputs of size n. Consider the leading term, ignore the constant coefficient. denoted by O(g(n): class of functions f(n) that grow no faster than g(n).,14,Orders of Growth,Exponential-growth functions,polynomial functions,旅行商问题,（Traveling Salesman Proble

8、m）,一位旅行售货员要到城市 进行商品销售，已知 的距离为 他从某个城市出发，去每个城市一次且仅一次回到出发的城市。问应如何计划旅行路线，使路线总长度最短？,路线有（n-1)!种,旅行商问题,（Traveling Salesman Problem）,一位旅行售货员要到城市 进行商品销售，已知 的距离为 他从某个城市出发，去每个城市一次且仅一次回到出发的城市。问应如何计划旅行路线，使路线总长度最短？,TSP：以计算机1秒可完成24个城市所有路径枚举 (23!种),1s,24s,10min,4. 3h,4.9d,136.5d,10.8y,325y,17,Orders of Growth,Expon

9、ential-growth functions,polynomial functions,TSP：以计算机1秒可完成24个城市所有路径枚举 (23!种),1s,24s,10min,4. 3h,4.9d,136.5d,10.8y,325y,Time Complexity,18,Polynomial Time Solvable Problems,Non-deterministic Polynomial-time (NP) Solvable Problems,NP类问题：可以在多项式时间内验证其解是否正确的问题。,P类问题：可以在多项式时间内求解的问题。,P and NP,19,Solvable,S

10、olvable,P and NP,Polynomial-TimeSolvable,Nondeterministic Polynomial-TimeSolvable,20,Solvable,P = NP ?,No answer, now.,21,Polynomial-TimeSolvable,Nondeterministic Polynomial-TimeSolvable,$1,000,000 Question,P = NP ?,No answer, now.,22,假设P NP,Complexity of a Problem,23,24,25,Coping with NP-Complete P

11、roblems,Exact Algorithmit might take an absurdly long time (e.g., 300 centuries) to find the optimal solution for the problem.Pseudo-polynomial Algorithm Eg. Knapsack Problem, (Dynamic Program) O(nW)Approximation Algorithm If the optimal solution is unattainable then it is reasonable to sacrifice op

12、timality and settle for a “good” (close to optimal) feasible solution that can be computed. Heuristic AlgorithmGenetic Algorithm, Simulated Annealing AlgorithmArtificial Neural Network, Tabu SearchEvolutionary Algorithm, Ant Algorithms,26,组合优化问题简介,线性规划问题,几种组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,最小费用流问题,

13、算法复杂性简介,The Diet Problem,The goal of the diet problem is to find the cheapest combination of foods that will satisfy all the daily nutritional requirements of a person.,The Diet Problem,The Diet Problem,aij : No. of units of nutrient i in one unit food j.,6 kinds of foods,11 kinds of nutrients,aij,x

14、j : No. of units of food j in the diet.,cj,bi: Lower bound of nutrient i in the diet.,11 kinds of nutrients,The Diet Problem,aij : No. of units of nutrient i in one unit food j.,6 kinds of foods,aij,xj : No. of units of food j in the diet.,cj,bi: Lower bound of nutrient i in the diet.,The Linear Pro

15、gram Model of Diet Problem,aij : No. of units of nutrient i in one unit food j.,xj : No. of units of food j in the diet.,cj: cost of one unit food j.,bi: Lower bound of nutrient i in the diet.,The goal: find the cheapest combination of foods that will satisfy all the daily nutritional requirements.,

16、Minimize,Subject to,The Linear Program Model of Diet Problem,aij : No. of units of nutrient i in one unit food j.,xj : No. of units of food j in the diet.,线性规划问题 (Linear Program),规范形式：,一般形式,标准形式：,求解线性规划的单纯形方法,基本思想：保持原问题的可行性，从凸多面体的一个顶点迭代到另一个更优的顶点。,研究线性规划的三次高潮,单纯形法: (1947 Dantzig),椭球算法: (1979 苏联青年数学家)

17、,Karmarkar内点算法: (1984 Karmarkar),实际运算效果非常好,平均运算次数是多项式的,不是多项式时间算法,1972年Klee,Minty给出反例,第一个多项式时间算法 O(n3(m+n) L) (L为输入规模),运用求解非线性规划的方法,实际运算效果不太好,从可行域的内部找到一个迭代点列达到边界,O(n3.5L) 实际运算效果较好,目前较好O(n3L),组合优化问题,几种组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,最小费用流问题,线性规划问题,算法复杂性简介,38,哥尼斯堡七桥问题(1736年欧拉),欧拉图：存在经过每条边一次且仅一次的回路,一

18、笔画：存在欧拉通(回)路,图连通且没有奇度顶点,图连通,奇度顶点有2, 0 个,d(A)=3,d(B)=3,d(C)=5,d(D)=3,4,2,39,哈密顿环球旅行问题(1857年) 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,40,中国邮路问题(1962管梅谷)：一邮递员从邮局出发要走遍他负责的每一条街道去送信，最后回到邮局要走的最短路径。,还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，这些都引出了许多有实用意义的新问题，开辟了新学科.,四色问题(1852年英国，1976美计算机证明)对任何一张地图进

19、行着色，两个共同边界的国家染不同的颜色，则只需要四种颜色就够了.,问题就转化为：在一个有奇度结点的赋权连通图中，增加一些平行边，使得新图不含奇度结点，并且增加的边的总权值最小。,41,图论的基本概念,定义1 一个有序二元组(V, E ) 称为一个图, 记为G = (V, E ), 其中, V称为G的顶点集, V, 其元素称为顶点; E称为G的边集, 其元素称为边, 它联结V 中的两个点, 如果这两个点是无序的, 则称该边为无向边, 否则, 称为有向边.,有边联结的两个点称为相邻的点, 有一个公共端点的边称为相邻边. 顶点v的度数d(v)：G中与顶点v关联的边的数目.,欧拉图,图连通且没有奇度顶

20、点,42,我们今后只讨论有限简单图：,(1) 顶点个数是有限的; (2) 任意一条边有且只有两个不同的点与它相互关联; (3) 若是无向图, 则任意两个顶点最多只有一条边与之相联结; (4) 若是有向图, 则任意两个顶点最多只有两条边与之相联结. 当两个顶点有两条边与之相联结时，这两条边的方向相反. 如果某个有限图不满足(2)(3)(4),可在某条边上增设顶点使之满足.,43,定义2 若图G的每条边e都对应一个实数w(e), 则称w(e)为该边的权, 称图G =(V,E,w)为赋权图(网络).,定义3 设G = (V, E)是一个图, v0, v1, , vkV, 且1ik, vi-1viE,

21、 则称v0 v1 vk是G的一条通路.如果通路中没有相同的边, 则称此通路为道路. 始点和终点相同的道路称为圈或回路(cycle). 如果通路中既没有相同的边, 又没有相同的顶点, 则称此通路为路径, 简称路(path).定义4 任意两点均有通路 的图称为连通图.定义5 连通而无圈的图称为树, 常用T表示树(Tree).,44,赋权图G = (V, E, w)的权矩阵A = (aij ) nn ,有限简单图基本上可用权矩阵来表示.,图的权矩阵,无向图G的权矩阵A是一个对称矩阵.,45,例 一摆渡人欲将一只狼,一头羊,一篮菜从河西渡过河到河东.由于船小,一次只能带一物过河，并且狼与羊,羊与菜不能

22、独处.给出渡河方法.,解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24 =16 种状态.在河东岸的状态类似记作.,由题设,状态(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的,从而对应状态(1,0,0,1), (1,1,0,0), (1,0,0,0)也是不允许的. 以可允许的10个状态向量作为顶点,将可能互相转移的状态用线段连接起来构成一个图. 根据此图便可找到渡河方法.,46,(1,1,1,1) (1,1,1,0) (1,1,0,1) (1,0,1,1) (1,0,1,0)(0,0,0,0) (0,0,0,1) (0,0,

23、1,0) (0,1,0,0) (0,1,0,1),(0,1,0,1) (0,1,0,0) (0,0,1,0) (0,0,0,1) (0,0,0,0)(1,0,1,0) (1,0,1,1) (1,1,0,1) (1,1,1,0) (1,1,1,1)河西=(人,狼,羊,菜) 河东=(人,狼,羊,菜),将10个顶点分别记为A1, A2, , A10 ,则渡河问题化为在该图中求一条从A1到A10的路. 从图中易得到两条路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,组合优化问题,几种

24、组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,最小费用流问题,线性规划问题,算法复杂性简介,48,最小支撑树问题的例子,公路连接问题某地区有n个主要城市，现准备修建高速公路把这些城市连接起来， 使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市. 假定已经知道了任意两个城市i和j之间修建高速公路的成本(费用)wij (0), 那么应任何决定在哪些城市间修建高速公路，使得总成本最小？,高速公路网正好构成这个完全图G的一个连通的支撑子图T.,为了使得总建设成本最小, 该子图必须是无圈的,无圈连通图称为树，上类问题称为最小支撑树问题.,49,村庄1,电话通讯问题：

25、阿富汗战后建设， 30个村庄要通话， 已知两两距离，如何用最少的电话线连通30个村庄？,村庄4,村庄3,村庄6,村庄2,村庄5,6,3,11,5,9,8,10,7,7,12,最小支撑树问题的例子,50,树的基本概念,定义：无圈连通图称为树(tree). 无圈图(即若干棵树的并)称为森林(forest).,引理图G=(V, E) ，|V|=n，则下列命题等价:G是一棵树；G连通，且|E|=n-1；G无圈，且|E|=n-1；G的任何两个顶点之间存在唯一的一条路；G连通，且将G的任何一条弧删去之后，该图成为非连通图；,6) G无圈，且在G的任何两个不相邻顶点之间加入一条弧之后，该图正好含有一个圈.,

26、51,最小支撑树(Minimum Spanning Tree),T*是G的一棵支撑树，且对G的任何一棵支撑树T都有 w(T*)w(T)，则T*为G的最小支撑树.,如果一个子图包含图的所有顶点并且是一棵树，则称这棵树为该图的支撑树.,G=(V,E,w)为一个无向网络，w为边权函数. 如果H=(V1,E1)为G的一个子图，,定理: 支撑树T*是最小树eG|T*, 在T*+e形成的圈中，e为最大弧, 即w(e)w(e), eT*.,e,e,52,求最小支撑树的方法,破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,6,5,5,1,7,2,3

27、,4,4,v1,v2,v3,v4,v5,v6,避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。,v3,v2,1,v4,2,v5,3,v6,4,v1,5,Kruskal(1956)O(mn),7,53,组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,几个典型的图论问题,图论的基本概念,最小费用流问题,54,最短路问题 (Shortest Path),若P0 (u, v) 是G 中连接u, v的路径, 且对任意在G 中连接u, v的路径P (u, v)都w(P0)w(P), 则称P0 (u, v) 是G 中连接u, v的

28、最短路.,重要性质：最短路的任一段也是最短路.,求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.,55,求赋权图中任意两点的最短路的Floyd算法(1962),设A = (aij )nn为赋权图G = (V, E, w)的权矩阵, dij表示从vi到vj点的距离, rij表示从vi到vj点的最短路中一个点的编号. 赋初值. 对所有i, j, dij = aij, rij = j. k = 1. 更新dij , rij . 对所有i, j, 若dik + dkjdij , 则令dij

29、 = dik + dkj , rij = k, 转向;(求得从vi到vj经过点v1, vk的最短路的距离) 终止判断. 若k = n终止; 否则令k= k+1, 转向. 最短路线可由rij得到. (每次迭代增加一个中间点，逐步更新距离矩阵D),56, 计算,其中,例如：,例 求下图中任意两点间的最短路., 赋初值,57,中不带角标的元素表示从 到 的距离（直接有边），带角标的元素表示借 为中间点时的最短路长。,58,中不带角标的元素表示从 到 的距离（直接有边），带角标的元素表示借 为中间点时的最短路长。,在放开 的基础上，再放开,59,表示任意两点间的最短路长及其路径。,比如， 表示任意点1

30、到点5之间的最短路长为6，其路径为13 2 5。,60,设备更新问题,某企业每年年初,都要作出决定,如果继续使用旧设备,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新计划,使总支出最少. 已知设备在每年年初的购买费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18. 解 设bi 表示设备在第i 年年初的购买费,ci 表示设备使用i 年后的维修费, V=v1, v2, , v6,点vi表示第i 年年初购进一台新设备,虚设一个点v6表示第5年年底. E =vivj | 1ij6.,61,这样上述设备更新问题就变为：在有向赋权图G = (V

31、, E, w )(图解如下)中求v1到v6的最短路问题.,已知设备在每年年初的购买费分别为11,11, 12,12,13. 使用不同时间设备所需的维修费分别为5,6,8,11,18.,62,由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5 ,v1到v6 ,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五条连线后得到,从上图中容易得到v1到v6只有两条路：,v1v3v6和v1v4v6.,而这两条路都是v1到v6的最短路，费用为53.,63,选址问题 (Location Problem),现准备在 n 个

32、居民点v1, v2, , vn中设置一银行.问设在哪个点,可使最大服务距离最小? 若设置两个银行,问设在哪两个点? 模型假设 假设各个居民点都有条件设置银行,并有路相连,且路长已知. 模型建立与求解 用Floyd算法求出任意两个居民点vi , vj 之间的最短距离,并用dij 表示., 设置一个银行,银行设在 vi 点的最大服务距离为,64,求k,使,即若设置一个银行,则银行设在 vk 点,可使最大服务距离最小. 设置两个银行,假设银行设在vs , vt 点使最大服务距离最小.,记,则s,t 满足：,进一步,若设置多个银行呢？,65,用三维数组表示(8升,5升,3升)酒壶的酒量,则平分酒的问题

33、化为在该图中求一条从起点到终点的最短路.从图中易得到上下两条路：显然上面一条较短，路长为7;下面一条路长为8.,思考题：某二人有一只8升的酒壶装满了酒,还有两只空壶,分别为5升和3升.问如何尽快将酒平分?,66,组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,几个典型的图论问题,图论的基本概念,最小费用流问题,设备更新问题,选址问题,67,二部图的匹配及其应用,定义 设X,Y 都是非空有限集,且XY = , E xy|xX,yY, 称G =(X, Y, E)为二部图.如果X中的每个点都与Y中的每个点邻接,则称G =(X, Y, E)为完备二部图.若w：ER +,则称G =

34、(X, Y, E, w )为二部赋权图.,68,设G =(X, Y, E)为二部图,且M E.若M中任意两条边在G中均不邻接,则称M是G的一个匹配.,设M是二部图G的一个匹配,如果G的每一个点都是M中边的顶点,则称M是二部图G的完美匹配；如果G中没有另外的匹配M0 ,使|M0|M|,则称M是二部图G的最大匹配.在二部赋权图G =(X, Y, E, w )中,权值最大的最大匹配M称为二部赋权图G的最佳匹配.,69,工作安排问题之一,给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. n个工作人员中每个人能胜任一项或几项工作, 但并不是所有工作人员都能从事任何一项工作.

35、问题：对所有的工作人员能不能都分配一件他所能胜任的工作？,构造一个二部图G = ( X, Y, E ), X=x1,x2, , xn, Y = y1, y2, , yn, (xi,yj)E人员xi胜任工作yj. 问题转化为求二部图的一个完美匹配. 因为 |X|=|Y|, 所以完美匹配即为最大匹配.,70,工作安排问题之二(指派问题),给n个工作人员x1, x2, , xn安排n项工作y1, y2, , yn. 如果每个工作人员工作效率不同, 要求工作分配的同时考虑总效率最高.,构造一个二部赋权图G = ( X, Y, E , c ), 这里X = x1, x2, , xn,Y = y1, y2

36、, , yn, cij 为工作人员xi胜任工作yj时的工作效率. 则问题转化为：求二部赋权图G的最佳匹配.求G 的最佳匹配, 总可假设G为完备二部赋权图.若xi与yj不相邻, 可令cij =0. 若人员数与工作数不等，可虚设点x或y使|X|=|Y|.,71,指派问题的数学模型及其特点 (Assignment Pr.),特点：若从效率矩阵(cij)nxn的一行(列)各元素中分别减去该行(列)的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解.,对同一项工作，同时提高或降低每人相同的效率，不影响其最优指派。,人员i能否完成工作j,人员i只能完成一项工作,工作j只能由一个人完成,总

37、的工作时间最少,72,指派问题的解法匈牙利法(D.Konig),匈牙利法的基本思想：可以让每行或每列减去一个数后，出现尽可能多的0元素，然后，再给费用为0元素的相应变量指派为1，以使变换后的目标函数为0，从而达到最优。,从效率矩阵的一行(列)各元素中分别减去该行(列)的最小元素，不改变原指派问题的最优解.,最小覆盖 与 最大独立集,设G = (V,E), 称点子集SV是一个覆盖, 若E中的每条边都至少有一个顶点在S中. 所有覆盖中顶点数最少的称为最小覆盖. 最小覆盖的顶点数称为最小覆盖数.,73,定理: 二部图的最小覆盖数= 最大匹配数.,设G = (V,E), 称点子集TV 是一个独立集,

38、若T中的任意两点不相邻. 所有独立集中顶点数最多的称为最大独立集. 最大独立集的顶点数称为最大独立集.,定理: 设S是G的一个覆盖，则T=VS是G的一个独立集.,对一般图都是NP-C问题，对二分图与最大匹配问题等价.,例题1 Place the Robots（ZOJ1654）,问题描述 有一个N*M(N,M=50)的棋盘，棋盘的每一格是三种类型之一：空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。问给定的棋盘，最多可以放置多少个机器人，使它们不能互相攻击。,74,模型一,75,问题转化为求图的最大独立集问题。,在问题的原型中，草地，墙这

39、些信息不是我们所关心的，我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：,机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。,机器人要放在不相邻的顶点上。,例题1 Place the Robots（ZOJ）,模型一,76,我们关心的只是空地和空地之间的联系。因此，我们很自然想到了下面这种简单的模型：以空地为顶点，有冲突的空地间连边，我们可以得到右边的这个图：,这是NP-C问题！,问题转化为求图的最大独立集问题。,机器人要放在不相邻的顶点上。,模型二,77,我们将每一

40、行，每一列被墙隔开，且包含空地的连续区域称作“块”。显然，在一个块之中，最多只能放一个机器人。我们把这些块编上号。,同样，把竖直方向的块也编上号。,1,2,3,4,5,机器人只能放在空地上。在同一行或同一列的两个机器人，若它们之间没有墙，则它们可以互相攻击。,例题1 Place the Robots（ZOJ）,模型二,78,1,2,3,4,5,把每个横向块看作X部的点，竖向块看作Y部的点，若两个块有公共的空地，则在它们之间连边。,于是，问题转化成这样的一个二部图：,例题1 Place the Robots（ZOJ）,模型二,79,由于每条边表示一个空地，有冲突的空地之间必有公共顶点，所以机器人

41、要放在不相邻的边上。,1,2,3,5,4,问题转化为二部图的最大匹配问题。,这是P类问题！,例题1 Place the Robots（ZOJ）,小结,80,模型一过于简单，没有给问题的求解带来任何便利；模型二则抓住了问题的内在联系，巧妙地建立了二部图。,为什么会产生这种截然不同的结果呢？其一是由于对问题分析的角度不同：模型一以空地为点，模型二以空地为边；其二是由于对原型中要素的选取有差异：模型一对要素的选取不充分，模型二则保留了原型中“棋盘”这个重要的性质。由此可见，对要素的选取，是图论建模中至关重要的一步。,例题2 打猎,猎人要在n*n的格子里打鸟,他可以在某一行中打一枪,这样此行中的所有鸟

42、都被打掉，也可以在某一列中打,这样此列中的所有鸟都打掉.问至少打几枪,才能打光所有的鸟？建图：二分图的X部为每一行，Y部为每一列，如果(i,j)有一只鸟，那么连接X部的i与Y部的j。该二分图最大匹配数既是最少要打的枪数。,81,例题3 救护伤员（TOJ1148）,无情的海啸夺取了无数人的生命.很多的医疗队被派往灾区拯救伤员.就在此时,医疗队突然发现自己带的药品已经不够用了,只剩下了N种。(1 n = 20)，随着病人病情的发展，每种药在每天能获得的效果是不一样的。同时，每天病人只能服用一种药。也就是说，这些药还够支持N天。现在，给出你每种药在每天使用的效果，请你判断当每种药都用完后所有药达到的

43、效果之和最大可以是多少。,例题4 最小路径覆盖,一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括0。请你求任意一个不含圈的有向图G的最小路径覆盖数。理清一个关系：最小路径覆盖数G的定点数最小路径覆盖中的边数,例题4 最小路径覆盖,试想我们应该使得最小路径覆盖中的边数尽量多，但是又不能让两条边在同一个顶点相交。拆点：将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息，从X部往Y部引边。所有边的方向都是由X部到Y部。,例题4 最小路径覆盖,因此，所转化出的二分图的最大匹配

44、数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数原图G的顶点数二分图的最大匹配数便可以得解。,86,组合优化问题,最短路问题,最小支撑树问题,指派问题,最大流最小割问题,几个典型的图论问题,图论的基本概念,最小费用流问题,设备更新问题,选址问题,二部图的最佳匹配问题,七桥问题,邮路问题,破圈法,避圈法,87,给一个有向图D(V,A)，指定两个点，一个称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。 对于D中的每一个弧(vi,vj)，相应地给一个数cij（cij0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为D(V,A,C)。,最大流问题 (

45、Maximum Flow),3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统有信息流,88,网络上的流：定义在弧集A上的函数f=f(vi,vj),并称f(vi,vj)为弧上的流量，简记为fij。,可行流的流量:,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,容量限制： 对每一边上都有,平衡条件：中间点：流入量等于流出量; 发收点：发出流量等于汇入流量.,可行流,使流量达到最大的可行流称为最大流.,89,对于可行流ffij，我们

46、把网络中使fijcij的弧称为饱和弧，使fij0的弧称为非零弧.,增广链 P是从vs到vt的一条链，满足前向弧 fij 0。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,若P是联结发点vs和收点vt的一条链，规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。,一个可行流是最大流 不存在增广链。,90,求最大流的标号法,思想：从可行流出发，经过标号并检查的过程,得到从vs到vt的增广链;再调整增广链的流量,得到新的可行流.重复直到无增广链时得到最大流.,(3,3),(5,1),(1,1),(1,1),(4,3),(2

47、,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,(-,+),(vs,4),(-v1,1),(-v2,1),(v2,1),(v3,1),(3,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),vs,v2,v1,v3,v4,(vs,3),(-,+),检查vi：对未标号vj；非饱和(vi,vj)，vj标(vi,minl(vi),cij-fij), 非零弧(vj,vi)，vj标号(-vi,minl(vi),fji),调整：在增广链上,前向弧流量增l(vt)，后向弧流量减l(vt).,91,该算法是否一定在有限步内终止呢

48、？如果弧上的容量可以是无理数，可以举出例子说明标号算法不一定在有限步内终止；并且，这一增广路算法的极限过程得到的流的流值即使收敛，也不一定收敛到最大流,Ford-Fulkerson标号算法,标号算法终止时，网络中一定不再含有增广路.,如果所有弧上的容量都是正整数，根据整流定理，最大流v也是整数. 实际上，由于割s，Vs中前向弧的条数最多为n条，因此最大流v的上界为nU（U表示网络中弧上的最大容量）. 由于每次增广至少使得流值增加1个单位，因此增广的次数不会超过v次，算法一定在有限步内终止. 此外，由于每次增广最多需要对所有弧检查一遍，因此算法的复杂度为O（mv），或表示为O（mnU）. 伪多项

49、式时间算法，而不是多项式时间算法.,92,Ford-Fulkerson标号算法每次随便找一条增广路进行增广,最大容量增广路算法:每次都找一条增广容量最大的增广路进行增广,最短增广路算法: 每次都找一条包含弧数最少的增广路,对于这时特殊的最短路问题,可以采用从节点s或t开始的广度优先搜索方法, 则在O(m)内找到一条最短增广路，因此最短增广路算法的复杂度为O(m2n).,从目前已有的理论分析和计算经验来看，最短增广路算法是所有增广路算法中效果最好的算法，可以设计出在O(logn)的平均时间内找到一条最短增广路，即算法复杂度为O(mnlogn),最短增广路算法,最短增广路算法最多经过O(mn)次增

50、广后终止.,93,若去掉某一割集的弧，则从vs到vt便不存在路.所以，割集是从vs到vt的必经之路。,割集的容量：,给定容量网络D=(V,E,C)，如果点集V被剖分成 ,使得 弧集 满足： 不连通； 为 的真子集，而 仍连通，则称 为G的割集。,(3,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),vs,v2,v1,v3,v4,(vs,3),(-,+),最大流最小割定理：最大流的流量=最小割集的容量,vt,最小割集,94,二部图中最大匹配问题可转化为最大流问题。在二部图中增加两个新点 vs ,vt分别作为发点，收点。并用有向边把它们与原二部