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

《组合优化问题简介ppt课件.ppt》由会员分享，可在线阅读，更多相关《组合优化问题简介ppt课件.ppt（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第第1页页关秀翠关秀翠东南大学数学系东南大学数学系组合优化问题组合优化问题(Combinatorial Optimization Problems)第第2页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学(Operations Research)绪绪 论论IntroductionIntroduction第第3页页引入数学方法解决实际问题引入数学方法解决实际问题 -定性与定量方法结合定性与定量方法结合系统与整体性系统与整体性 -从全局考察问题从全局考察问题应用性应用性 -源于实践、为了实践、服务于实践源于实践、为了实践、服务于实践交叉学科交叉学科 -涉及经济

2、、管理、数学、工程和系统等涉及经济、管理、数学、工程和系统等 多学科多学科开放性开放性 -不断产生新的问题和学科分支不断产生新的问题和学科分支多分支多分支 -问题的复杂性和多样性问题的复杂性和多样性运筹学的性质与特点第第4页页线性规划线性规划数数学学规规划划非线性规划非线性规划整数规划整数规划动态规划动态规划学学科科内内容容多目标规划多目标规划双层规划双层规划组组合合优优化化最优计数问题最优计数问题网络优化网络优化排序问题排序问题统筹图统筹图随随机机优优化化对策论对策论排队论排队论库存论库存论决策分析决策分析可靠性分析可靠性分析运筹学的主要内容第第5页页1在数学学科中的地位在数学学科中的地位运

3、筹数学运筹数学1在系统科学中的地位在系统科学中的地位系统工程系统工程1在管理科学中的地位在管理科学中的地位管理与运筹学管理与运筹学1与经济学的关系与经济学的关系问题与方法问题与方法1与工程科学的关系与工程科学的关系方法与应用方法与应用1 与计算机科学的关系与计算机科学的关系核心算法与工具核心算法与工具基础理论基础理论应用理论应用理论应用技术应用技术运筹学运筹学运筹学的学科地位第第6页页模型要素模型要素 变量变量可可控因素控因素 目标目标优化优化的动力和依据的动力和依据 约束约束内内部条件和外部约束部条件和外部约束研究方法研究方法 建建模模最优最优性条性条件件算算法法灵敏灵敏度分度分析析最优化模

4、型第第7页页组合优化问题简介组合优化问题简介线性规划问题线性规划问题几种组合优化问题几种组合优化问题最短路问题最短路问题最小支撑树问题最小支撑树问题指派问题指派问题最大流最小割问题最大流最小割问题最小费用流问题最小费用流问题算法复杂性简介算法复杂性简介什么是计算？什么是计算？分析问题：抓住本质（抽象法）分析问题：抓住本质（抽象法）一些符号记在某种器具上，一些符号记在某种器具上，计算的行为随着作为各步结果的各种特定符号而变化。计算的行为随着作为各步结果的各种特定符号而变化。n因此因此计计算可抽象成在算可抽象成在线线性性带带上的上的0、1串串执执行以下指令：行以下指令：1.写符号写符号0；2.写符

5、号写符号1；3.向左移一格；向左移一格；4.向右移一格；向右移一格；5.观观察当前符号以确定下一步；察当前符号以确定下一步；6.停止。停止。一个一个线线性的性的纸带纸带或磁或磁带带，带带中可加格子中可加格子实质实质是或者在格子里写是或者在格子里写0或或1，或者移到另一格子，或者移到另一格子8Church-Turing ThesislEvery effective computation or algorithm can be carried out by a Turing Machine.Turing,Alan(1912-1954)Effective ComputationAlgorithmA

6、ny computer program Truing Machine9What Can be Done by a Computer?lProblem SolvabilityWhat computers can?What computers cant?1011lAn algorithm is a finite sequence of unambiguous instructions for solving a well-specified computational problem.lImportant Features:Finiteness.Definiteness.Effectiveness

7、.AlgorithmInputOutputWhat is an Algorithm?Brute forceDivide and conquerDecrease and conquerTransform and conquerSpace and time tradeoffsGreedy approachDynamic programmingBacktracking Branch and boundTwo main issues related to algorithmsu How to design algorithms?u How to analyze an algorithm?1.Is it

8、 correct?2.How are the time and space efficiencies of the algorithm?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.lRunning time of an algorithm for a given input is the number of steps executed by the algorithm on th

9、at input.Running Time1313running timeexecution time for the basic operationNo.of times the basic operation is executedinput sizel Worst Case Efficiency:The 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

10、 of functions f(n)that grow no faster than g(n).14Orders of GrowthExponential-growth functionspolynomial functions 旅行商问题旅行商问题（Traveling Salesman Problem）一位旅行售货员要到城市一位旅行售货员要到城市 进行商品销售，进行商品销售，已知已知 的距离为的距离为 他从某个城市出发，去每个城市一次且仅一次回到出发的他从某个城市出发，去每个城市一次且仅一次回到出发的城市。问应如何计划旅行路线，使路线总长度最短？城市。问应如何计划旅行路线，使路线总长度最短？

11、路线有路线有（n-1)!n-1)!种种 旅行商问题旅行商问题（Traveling Salesman Problem）一位旅行售货员要到城市一位旅行售货员要到城市 进行商品销售，进行商品销售，已知已知 的距离为的距离为 他从某个城市出发，去每个城市一次且仅一次回到出发的他从某个城市出发，去每个城市一次且仅一次回到出发的城市。问应如何计划旅行路线，使路线总长度最短？城市。问应如何计划旅行路线，使路线总长度最短？TSP：以：以计计算机算机1秒可完成秒可完成24个城市所有路径枚个城市所有路径枚举举(23!种种)城市数城市数城市数城市数24242525262627272828 2929 3030 313

12、1计算时间计算时间计算时间计算时间1 1s s2424s s1010minmin4.34.3h h4.94.9d d 136.5136.5d d10.810.8y y 325325y y17Orders of GrowthExponential-growth functionspolynomial functionsTSP：以：以计计算机算机1秒可完成秒可完成24个城市所有路径枚个城市所有路径枚举举(23!种种)城市数城市数城市数城市数24242525262627272828 2929 3030 3131计算时间计算时间计算时间计算时间1 1s s2424s s1010minmin4.34.3

13、h h4.94.9d d 136.5136.5d d10.810.8y y 325325y yTime Complexity18l Polynomial Time Solvable Problemsl Non-deterministic Polynomial-time(NP)Solvable ProblemsNP类问题类问题：可以在多：可以在多项项式式时间时间内内验证验证其解是否其解是否正确的正确的问题问题。P类问题类问题：可以在多：可以在多项项式式时间时间内内求解求解的的问题问题。NPP P and NPNPP19SolvableSolvableNPP P and NPNPPPolynomi

14、al-TimeSolvableNondeterministic Polynomial-TimeSolvable20SolvableNPPP=NP?No answer,now.21Polynomial-TimeSolvableNondeterministic Polynomial-TimeSolvable$1,000,000 Question$1,000,000 QuestionNPPP=NP?No answer,now.22NP-Complete假设假设P P NP NP Complexity of a Problem232425Coping with NP-Complete Problems

15、 lExact Algorithmit might take an absurdly long time(e.g.,300 centuries)to find the optimal solution for the problem.lPseudo-polynomial Algorithm Eg.Knapsack Problem,(Dynamic Program)O(nW)lApproximation Algorithm If the optimal solution is unattainable then it is reasonable to sacrifice optimality a

16、nd settle for a“good”(close to optimal)feasible solution that can be computed.lHeuristic AlgorithmGenetic Algorithm,Simulated Annealing AlgorithmArtificial Neural Network,Tabu SearchEvolutionary Algorithm,Ant Algorithms26第第27页页组合优化问题简介组合优化问题简介线性规划问题线性规划问题几种组合优化问题几种组合优化问题最短路问题最短路问题最小支撑树问题最小支撑树问题指派问题指

17、派问题最大流最小割问题最大流最小割问题最小费用流问题最小费用流问题算法复杂性简介算法复杂性简介The Diet ProblemUnitPrice200400300300RequiredUnitsVA 5000IUCa 1000 mgDietary_Fiber 100gFood.Nutrient.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

18、ProblemFoodsPrice$SizeCalories CHO mgFat gNa mgCarbo.gD_Fiber gProt.gVA IUVC IUCa mgFe mgChicken.841 lb 277.4 129.9 10.8 125.6 0 0 42.2 77.4 0 21.9 1.8 Beef.271 F.141.8 27.4 12.8 461.7 0.8 0 5.4 0 10.8 9 0.6 Lett uce.021 Leaf2.6 0 0 1.8 0.4 0.3 0.2 66 0.8 3.8 0.1 Potato.221 Oz139.2 0 9.2 212.6 15 1.

19、2 2.2 61.5 9.6 14.2 0.5 Milk.131 C85.5 4.4 0.4 126.2 11.9 0 8.4 499.8 2.4 302.3 0.1 Tom ato.271 25.8 0 0.4 11.1 5.7 1.4 1 766.3 23.5 6.2 0.6 Lowerbound200010020200100255050005080010The Diet ProblemFoodsPrice$SizeCalories CHO mgFat gNa mgCarbo.gD_Fiber gProt.gVA IUVC IUCa mgFe mgChicken.841 lb 277.4

20、129.9 10.8 125.6 0 0 42.2 77.4 0 21.9 1.8 Beef.271 F.141.8 27.4 12.8 461.7 0.8 0 5.4 0 10.8 9 0.6 Lett uce.021 Leaf2.6 0 0 1.8 0.4 0.3 0.2 66 0.8 3.8 0.1 Potato.221 Oz139.2 0 9.2 212.6 15 1.2 2.2 61.5 9.6 14.2 0.5 Milk.131 C85.5 4.4 0.4 126.2 11.9 0 8.4 499.8 2.4 302.3 0.1 Tom ato.271 25.8 0 0.4 11.

21、1 5.7 1.4 1 766.3 23.5 6.2 0.6 Lowerbound200010020200100255050005080010aij:No.of units of nutrient i in one unit food j.6 kinds of foods11 kinds of nutrients aij xj:No.of units of food j in the diet.cjbi:Lower bound of nutrient i in the diet.11 kinds of nutrients The Diet ProblemFoodsPrice$SizeCalor

22、ies CHO mgFat gNa mgCarbo.gD_Fiber gProt.gVA IUVC IUCa mgFe mgChicken.841 lb 277.4 129.9 10.8 125.6 0 0 42.2 77.4 0 21.9 1.8 Beef.271 F.141.8 27.4 12.8 461.7 0.8 0 5.4 0 10.8 9 0.6 Lett uce.021 Leaf2.6 0 0 1.8 0.4 0.3 0.2 66 0.8 3.8 0.1 Potato.221 Oz139.2 0 9.2 212.6 15 1.2 2.2 61.5 9.6 14.2 0.5 Mil

23、k.131 C85.5 4.4 0.4 126.2 11.9 0 8.4 499.8 2.4 302.3 0.1 Tom ato.271 25.8 0 0.4 11.1 5.7 1.4 1 766.3 23.5 6.2 0.6 Lowerbound200010020200100255050005080010aij:No.of units of nutrient i in one unit food j.6 kinds of foodsaij xj:No.of units of food j in the diet.cjbi:Lower bound of nutrient i in the di

24、et.The Linear Program Model of Diet Problemaij: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 requirement

25、s.UnitPricec1c2c3cn.RequiredUnitsb1b2bm.Food.Nutrient.MinimizeSubject toThe Linear Program Model of Diet Problemaij:No.of units of nutrient i in one unit food j.xj:No.of units of food j in the diet.第第34页页线性规划问题线性规划问题(Linear Program)规范形式：规范形式：一一般般形形式式标准形式：标准形式：第第35页页求解线性规划的单纯形方法求解线性规划的单纯形方法基本思想：保持原问题

26、的可行性，从凸多面基本思想：保持原问题的可行性，从凸多面体的一个顶点迭代到另一个更优的顶点。体的一个顶点迭代到另一个更优的顶点。第第36页页研究线性规划的三次高潮研究线性规划的三次高潮单纯形法单纯形法:(1947 Dantzig)椭球算法椭球算法:(1979 苏联青年数学家苏联青年数学家)Karmarkar内点算法内点算法:(1984 Karmarkar)实际运算效果非常好实际运算效果非常好平均运算次数是多项式的平均运算次数是多项式的不是多项式时间算法不是多项式时间算法1972年年Klee,Minty给出反例给出反例第一个多项式时间算法第一个多项式时间算法 O(n3(m+n)L)(L为输入规模

27、为输入规模)运用求解非线性规划的方法运用求解非线性规划的方法实际运算效果不太好实际运算效果不太好从可行域的内部找到一个迭代点列达到边界从可行域的内部找到一个迭代点列达到边界O(n3.5L)实际运算效果较好实际运算效果较好目前较好目前较好O(n3L)第第37页页组合优化问题组合优化问题几种组合优化问题几种组合优化问题最短路问题最短路问题最小支撑树问题最小支撑树问题指派问题指派问题最大流最小割问题最大流最小割问题最小费用流问题最小费用流问题线性规划问题线性规划问题算法复杂性简介算法复杂性简介38哥尼斯堡七桥问题哥尼斯堡七桥问题(1736年欧拉年欧拉)欧拉图：存在经过每条边一次且仅一次的欧拉图：存在

28、经过每条边一次且仅一次的回路回路一笔画：存在欧拉通一笔画：存在欧拉通(回回)路路图连通且没有奇度顶点图连通且没有奇度顶点图连通图连通,奇度顶点有奇度顶点有2,0 个个d(A)=3d(B)=3d(C)=5d(D)=34 42 239哈密顿环球旅行哈密顿环球旅行问题问题(1857(1857年年)十二面体的十二面体的2020个顶点代表世界上个顶点代表世界上2020个城市，个城市，能否从某个城市出发在十二面体上依次能否从某个城市出发在十二面体上依次经过每个经过每个城市恰好一次最后回到出发点城市恰好一次最后回到出发点？哈密顿圈（环球旅行游戏）哈密顿圈（环球旅行游戏）40中国邮路问题中国邮路问题(1962

29、(1962管梅谷管梅谷)：一一邮邮递递员员从从邮邮局局出出发发要要走走遍遍他他负负责责的的每每一一条条街街道去送信，最后回到邮局要走的最短路径。道去送信，最后回到邮局要走的最短路径。还有许多诸如迷宫问题、博弈问题以及棋盘上马还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，这些都引出了许多的行走路线之类的游戏难题，这些都引出了许多有实用意义的新问题，开辟了新学科有实用意义的新问题，开辟了新学科.四色问题四色问题(1852年英国，年英国，19761976美计算机证明美计算机证明)对任何一张地图进行着色，两个共同边界的国对任何一张地图进行着色，两个共同边界的国家染不同的颜色，则只

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

31、无序的,则称该边为则称该边为无向无向边边,否则否则,称为称为有向边有向边.有边联结的两个点称为有边联结的两个点称为相邻的点相邻的点,有一个公共端点的边称为有一个公共端点的边称为相邻边相邻边.顶点顶点v的的度数度数d(v)：G中与顶点中与顶点v关联的边的数目关联的边的数目.欧拉图欧拉图图连通且没有奇度顶点图连通且没有奇度顶点42我们今后只讨论我们今后只讨论有限简单图有限简单图：(1)(1)顶点个数是有限的顶点个数是有限的;(2)(2)任意一条边有且只有两个不同的点与它任意一条边有且只有两个不同的点与它相互关联相互关联;(3)(3)若是无向图若是无向图,则任意两个顶点最多只有则任意两个顶点最多只有

32、一条边与之相联结一条边与之相联结;(4)(4)若是有向图若是有向图,则任意两个顶点最多只有则任意两个顶点最多只有两条边与之相联结两条边与之相联结.当两个顶点有两条边与之相当两个顶点有两条边与之相联结时，这两条边的方向相反联结时，这两条边的方向相反.如果某个有限图不满足如果某个有限图不满足(2)(3)(4),(2)(3)(4),可在某条可在某条边上增设顶点使之满足边上增设顶点使之满足.43定义定义2 若图若图G的每条边的每条边e都对应一个实数都对应一个实数w(e),则称则称w(e)为该边的为该边的权权,称图称图G=(V,E,w)为为赋权图赋权图(网络网络).定义定义3 设设G=(V,E)是一个图

33、是一个图,v0,v1,vkV,且且 1ik,vi-1viE,则称则称v0 v1 vk是是G的一条的一条通路通路.如果通路中没有相同的边如果通路中没有相同的边,则称此通路为则称此通路为道路道路.始点和终点相同的道路称为始点和终点相同的道路称为圈圈或或回路回路(cycle).如果通路中既没有相同的边如果通路中既没有相同的边,又没有相同的顶点又没有相同的顶点,则称此通路为则称此通路为路径路径,简称简称路路(path).定义定义4 任意两点均有通路任意两点均有通路 的图称为的图称为连通图连通图.定义定义5 连通而无圈的图称为连通而无圈的图称为树树,常用常用T表示树表示树(Tree).44赋权图赋权图G

34、=(V,E,w)的权矩阵的权矩阵A=(aij)nn,有限简单图基有限简单图基本上可用权矩本上可用权矩阵来表示阵来表示.图的图的权权矩阵矩阵 无向图无向图G的权矩阵的权矩阵A是一个对称矩阵是一个对称矩阵.45 例例 一摆渡人欲将一只狼一摆渡人欲将一只狼,一头羊一头羊,一篮菜从河一篮菜从河西渡过河到河东西渡过河到河东.由于船小由于船小,一次只能带一物过河，一次只能带一物过河，并且狼与羊并且狼与羊,羊与菜不能独处羊与菜不能独处.给出渡河方法给出渡河方法.解解：用四维：用四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河在河西岸的状态西岸的状态(在河西岸则分量取在河西岸则分量取1,1,否则

35、取否则取0),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

36、,0)(0,0,0,0)(0,0,0,1)(0,0,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

37、 A9 A4 A8 A5 A10.A1A2A3A4A5A6A7A8A9A10第第47页页组合优化问题组合优化问题几种组合优化问题几种组合优化问题最短路问题最短路问题最小支撑树问题最小支撑树问题指派问题指派问题最大流最小割问题最大流最小割问题最小费用流问题最小费用流问题线性规划问题线性规划问题算法复杂性简介算法复杂性简介48最小支撑树问题最小支撑树问题的例子的例子公路连接问题公路连接问题某地区有某地区有n个主要城市，现准备修建高速公路把这些个主要城市，现准备修建高速公路把这些城市连接起来，城市连接起来，使得从其中任何一个城市都可以经使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市高

38、速公路直接或间接到达另一个城市.假定已经知道假定已经知道了任意两个城市了任意两个城市i和和j之间修建高速公路的成本之间修建高速公路的成本(费用费用)wij(0),那么应任何决定在哪些城市间修建高速公那么应任何决定在哪些城市间修建高速公路，使得总成本最小？路，使得总成本最小？高速公路网正好构成这个完全图高速公路网正好构成这个完全图G的一个连通的的一个连通的支撑子图支撑子图T.为了使得总建设成本最小为了使得总建设成本最小,该子图必须是无圈的该子图必须是无圈的 无圈连通图称为树，上类问题称为最小支撑树问题无圈连通图称为树，上类问题称为最小支撑树问题.49村庄村庄1电话通讯问题：阿富汗战后建设，电话通

39、讯问题：阿富汗战后建设，30个个村庄要通话，村庄要通话，已知两两距离，如何用最已知两两距离，如何用最少的电话线连通少的电话线连通30个村庄？个村庄？村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄56311598107712最小支撑树问题最小支撑树问题的例子的例子50树的基本概念树的基本概念定义：无圈连通图称为树定义：无圈连通图称为树(tree).无圈图无圈图(即若即若干棵树的并干棵树的并)称为森林称为森林(forest).).引理引理 图图G=(V,E)，|V|=n，则，则下列命题等价下列命题等价:1)G是一棵树；是一棵树；2)G连通，且连通，且|E|=n-1；3)G无圈，且无圈，且|E|=

40、n-1；4)G的任何两个顶点之间存在的任何两个顶点之间存在唯一唯一的一条路；的一条路；5)G连连通通，且且将将G的的任任何何一一条条弧弧删删去去之之后后，该该图成为非连通图；图成为非连通图；6)G无无圈圈，且且在在G的的任任何何两两个个不不相相邻邻顶顶点点之之间间加入一条弧之后，该图正好含有一个圈加入一条弧之后，该图正好含有一个圈.51最小支撑树最小支撑树(Minimum Spanning Tree)T*是是G的一棵支撑树，且对的一棵支撑树，且对G的任何一棵支撑树的任何一棵支撑树T都有都有 w(T*)w(T)，则，则T*为为G的最小支撑树的最小支撑树.如果一个子图包含图的所有顶点并且是一棵树，

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

42、含圈不含圈的图为止。的图为止。655172344v1v2v3v4v5v6 避圈法避圈法：开始选一条开始选一条权最小权最小的边，以后每的边，以后每一步中，总从未被选一步中，总从未被选取的边中选一条权尽取的边中选一条权尽可能小，且与已选边可能小，且与已选边不构成圈的边。不构成圈的边。v3v21v42v53v64v15 Kruskal(1956)(1956)O(mn)753组合优化问题组合优化问题最短路问题最短路问题最小支撑树问题最小支撑树问题指派问题指派问题最大流最小割问题最大流最小割问题几个典型的图论问题几个典型的图论问题图论的基本概念图论的基本概念最小费用流问题最小费用流问题54最短路问题最短

43、路问题(Shortest Path)若若P0(u,v)是是G 中连接中连接u,v的路径的路径,且对任意在且对任意在G 中连接中连接u,v的路径的路径P(u,v)都都w(P0)w(P),则称则称P0(u,v)是是G 中连接中连接u,v的的最短路最短路.重要性质：重要性质：最短路的任一段也是最短路最短路的任一段也是最短路.求非负赋权图求非负赋权图G中某一点到其它各点最短路，一中某一点到其它各点最短路，一般用般用Dijkstra标号算法；标号算法；求非负赋权图上任意两点间的最短路，一般用求非负赋权图上任意两点间的最短路，一般用Floyd算法算法.这两种算法均适用于有向非负赋权图这两种算法均适用于有向

44、非负赋权图.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=dik+dkj,rij=k,转向转向;(求得求得从从vi到到vj经过点经过点v1,vk的最短路的距离的最短路的距离)终止判断终止判断.若若k

45、=n终止终止;否则令否则令k=k+1,转向转向.最短路线可由最短路线可由rij得到得到.(每次迭代增加一个中间点，逐步更新距离矩阵每次迭代增加一个中间点，逐步更新距离矩阵D)56 计算计算其中其中例如：例如：例例 求下图中任意两点间的最短路求下图中任意两点间的最短路.赋初值赋初值57 中不带角标的元素表示从中不带角标的元素表示从 到到 的距的距离（直接有边），离（直接有边），带角标的元素表示借带角标的元素表示借 为中间点时的最短路为中间点时的最短路长。长。58 中不带角标的元素表示从中不带角标的元素表示从 到到 的距离（直接有边）的距离（直接有边），带角标的元素表示借带角标的元素表示借 为中间

46、点时的最短路长。为中间点时的最短路长。在放开在放开 的基础上，再放开的基础上，再放开在放开在放开 点的基础上，再放开点的基础上，再放开 考察最考察最短路。短路。然后然后,59表示任意两点间的最短路长及其路径。表示任意两点间的最短路长及其路径。比如，比如，表示任意点表示任意点1到点到点5之间的之间的最短路长为最短路长为6，其路径为，其路径为13 2 5。60设备更新问题设备更新问题 某企业每年年初某企业每年年初,都要作出决定都要作出决定,如果继续使如果继续使用旧设备用旧设备,要付维修费；若购买一台新设备要付维修费；若购买一台新设备,要付要付购买费购买费.试制定一个试制定一个5 5年更新计划年更新

47、计划,使总支出最少使总支出最少.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,11,11,12,12,13.12,12,13.使用不同时间设备所需的维修费分别使用不同时间设备所需的维修费分别为为5,6,8,11,18.5,6,8,11,18.解解 设设bi 表示设备在第表示设备在第i 年年初的购买费年年初的购买费,ci 表表示设备使用示设备使用i 年后的维修费年后的维修费,V=v1,v2,v6,点点vi表示第表示第i 年年初购进一台新设备年年初购进一台新设备,虚设一个点虚设一个点v6表表示第示第5 5年年底年年底.E=vivj|1ij6.61 这样上述设备更新问题

48、就变为：在有向赋权图这样上述设备更新问题就变为：在有向赋权图G=(V,E,w)(图解如下图解如下)中求中求v1到到v6的最短路问题的最短路问题.已知设备在每年年初的购买费分别为已知设备在每年年初的购买费分别为11,11,11,11,12,12,13.12,12,13.使用不同时间设备所需的维修费分别使用不同时间设备所需的维修费分别为为5,6,8,11,18.5,6,8,11,18.62 由实际问题可知由实际问题可知,设备使用三年后应当更新设备使用三年后应当更新,因此删除该图中因此删除该图中v1到到v5,v1到到v6,v2到到v6的连线；又的连线；又设备使用一年后就更新则不划算设备使用一年后就更

49、新则不划算,因此再删除该因此再删除该图中图中v1v2,v2v3,v3v4,v4v5,v5v6 五条连线后得到五条连线后得到从上图中容易得到从上图中容易得到v1到到v6只有两条路：只有两条路：v1v3v6和和v1v4v6.而这两条路都是而这两条路都是v1到到v6的最短路，费用为的最短路，费用为53.53.63选址问题选址问题 (Location Problem)现准备现准备在在 n 个个居民点居民点v1,v2,vn中设置一银中设置一银行行.问设在哪个点问设在哪个点,可使最大服务距离最小可使最大服务距离最小?若设若设置两个银行置两个银行,问设在哪两个点问设在哪两个点?模型假设模型假设 假设各假设各

50、个个居民点都有条件设置银居民点都有条件设置银行行,并有路相连并有路相连,且路长已知且路长已知.模型建立与求解模型建立与求解 用用Floyd算法求出任意两算法求出任意两个个居民点居民点vi,vj 之间的最短距离之间的最短距离,并用并用dij 表示表示.设置一个银行设置一个银行,银行设银行设在在 vi 点点的最大服务的最大服务距离为距离为64求求k,使使 即若设置一个银行即若设置一个银行,则银行设在则银行设在 vk 点点,可使最可使最大服务距离最小大服务距离最小.设置两个银行设置两个银行,假设银行设假设银行设在在vs,vt 点点使最使最大服务距离最小大服务距离最小.记记则则s,t 满足：满足：进一