《网络优化(数学建模资料)ppt课件.ppt》由会员分享，可在线阅读，更多相关《网络优化(数学建模资料)ppt课件.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1网网 络络 优优 化化 第第 1 1 章章 概概 论论 （第（第1 1讲）讲）Network Optimization清华大学数学科学系 谢金星办公室：理科楼1308# （电话：62787812）Email: http:/ 络络 优优 化化 简简 介介网络：网络社会 - 计算机信息网络？电话通信网络 运输服务网络 能源和物质分派网络 人际关系网络 等等网络优化就是研究如何有效地计划、管理和控制网络优化就是研究如何有效地计划、管理和控制网络系统，使之发挥最大的社会和经济效益网络系统，使之发挥最大的社会和经济效益 3网网 络络 优优 化化 简简 介介 网络：数学模型、数学结构网络：数学模型、数学
2、结构 - 图图从若干可能的安排或方案中寻求某种意义下的最优安排或方从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为（最）优化案，数学上把这种问题称为（最）优化 (Optimization) 问题问题 运筹学（运筹学（Operations Research - OR）的一个分支）的一个分支网络优化就是研究网络优化就是研究与（赋权）图有关的最优化问题与（赋权）图有关的最优化问题 研究生专业 数学本科专业数学数学 与应用数学信息 与计算科学基础数学应用数学计算数学概率论与数理统计运筹学运筹学与控制论4Operations Research and Management S
3、cience (OR/MS) The professional disciplines that deal with the application of information technology for informed decision-making Provide rational bases for decision making by seeking to understand and structure complex situations and to use this understanding to predict system behavior and improve
4、system performance. Much of this work is done using analytical and numerical techniques to develop and manipulate mathematical and computer models of organizational systems composed of people, machines, and procedures. The field is closely related to several other fields in the decision sciences - a
5、pplied mathematics, computer science, economics, industrial engineering, and systems engineering. From http:/www.informs.org/Join/Orms.html5建 立 OR/MS 理 论 模 型 的 一 般 步 骤模型准备模型假设模型构成模型求解模型分析模型检验模型应用 Applied Mathematics Mathematical Modeling:Motivation,Formulation,Solution,Validation“源”远“流”长6运筹学（运筹学（Ope
6、rations Research - OR）n广义：管理科学广义：管理科学/决策科学决策科学(MS/DS)、系统科学、系统科学/工程工程(SS/SE)、工业工程、工业工程(IE)、运、运作管理作管理(OM)n狭义：运筹数学狭义：运筹数学 - 最优化、最优化、对策论、排队论等对策论、排队论等 连续优化：数学规划（线性规划、非连续优化：数学规划（线性规划、非线性规划）、非光滑优化、全局优化等线性规划）、非光滑优化、全局优化等 离散优化：组合优化、离散优化：组合优化、网络优化、整网络优化、整数规划等数规划等 不确定规划：随机规划、模糊规划等不确定规划：随机规划、模糊规划等OMOR/MS/DSSS/S
7、EIE/EMn网络优化也是计算机科学的入门课程之一网络优化也是计算机科学的入门课程之一7Optimization Tree http:/www-fp.mcs.anl.gov/otc/Guide/OptWeb/8网网 络络 优优 化化 简简 介介教材：教材：谢金星谢金星 、邢文训邢文训，网络优化网络优化 ，清华大学出版社，清华大学出版社，2000年年8月；月；2003年年9月。月。参考书：参考书：Ahuja, R. K., Magnanti T. L., Orlin J. B. Network Flows: Theory, Algorithms, and Applications. Prenti
8、ce Hall, 1993: Englewood Cliffs, New Jersey. 教学资源： 网络学堂; http:/ - 50%左右左右 考试考试 - 50%左右左右如何学习？认真看书、完成习题如何学习？认真看书、完成习题( (有些习题难度较大有些习题难度较大) )助教助教: : 王振波王振波 内容：网络优化模型、算法及其复杂性内容：网络优化模型、算法及其复杂性对象：数学、计算机科学、管理科学、工程科学等9例例1.1 公路连接问题公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，城市连接起来， 使得从其中任何
9、一个城市都可以经高速公使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市路直接或间接到达另一个城市. 假定已经知道了任意两个城假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？间修建高速公路，使得总成本最小？ 1.1网络优化问题的例子网络优化问题的例子 例例1.2 最短路问题（最短路问题（SPP-Shortest Path Problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地往乙地. 从甲地到乙地的公路网纵横
10、交错，因此有多种行车从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路乙地的最短路. 10例例1.3 运输问题运输问题(Transportation Problem)某种原材料有某种原材料有M个产地，现在需要将原材料从产地运往个产地，现在需要将原材料从产地运往N个个使用这些原材料的工厂使用这些原材料的工厂. 假定假定M个产地的产量和个产地的产量和N家工厂的家工厂的需要量已知，单位产品从任一产
11、地到任一工厂的的运费已需要量已知，单位产品从任一产地到任一工厂的的运费已知，那么如何安排运输方案可以使总运输成本最低？知，那么如何安排运输方案可以使总运输成本最低？ 1.1网络优化问题的例子网络优化问题的例子 例例1.4 指派问题指派问题(Assignment Problem)一家公司经理准备安排一家公司经理准备安排N名员工去完成名员工去完成N项任务，每人一项项任务，每人一项. 由于各员工的特点不同，不同的员工去完成同一项任务时由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的所获得的回报是不同的. 如何分配工作方案可以使总回如何分配工作方案可以使总回 报最报最大？大？ 1
12、1例例1.5 中国邮递员问题中国邮递员问题(CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件. . 如何为他如何为他( (她她) )设计设计一条最短的投递路线一条最短的投递路线( (从邮局出发，经过投递区内每条街道从邮局出发，经过投递区内每条街道至少一次，最后返回邮局至少一次，最后返回邮局) )？由于这一问题是我国？由于这一问题是我国复旦大学复旦大学 管梅谷管梅谷教授教授19601960年首先提出的，所以国际上称之为中国邮年首先提出的，所以国际上称之为中国邮递员问题递员问题. . 1.1网络优化问题的例子网络优化问题的例子
13、 例例1.6 旅行商问题旅行商问题/货郎（担）问题货郎（担）问题(TSP-Traveling Salesman Problem)一名推销员准备前往若干城市推销产品一名推销员准备前往若干城市推销产品. . 如何为他如何为他( (她她) )设设计一条最短的旅行路线计一条最短的旅行路线( (从驻地出发，经过每个城市恰好一从驻地出发，经过每个城市恰好一次，最后返回驻地次，最后返回驻地) )？这一问题的研究历史十分悠久，通常？这一问题的研究历史十分悠久，通常称之为旅行商问题称之为旅行商问题. . 121.1网络优化问题的例子网络优化问题的例子 例例 稳定婚配问题稳定婚配问题( (Stable Marri
14、age Problem) )假设有假设有n个男人和个男人和n个女人个女人, 每人都希望从每人都希望从n个异性中选择一位个异性中选择一位自己的配偶自己的配偶. 假设每人都对假设每人都对n个异性根据自己的偏好进行了排个异性根据自己的偏好进行了排序序, 以此作为选择配偶的基础以此作为选择配偶的基础. 当给定一种婚配方案当给定一种婚配方案(即给每人即给每人指定一个配偶指定一个配偶)后后, 如果存在一个男人和一个女人不是互为配如果存在一个男人和一个女人不是互为配偶偶, 但该男人喜欢该女人胜过其配偶但该男人喜欢该女人胜过其配偶, 且该女人喜欢该男人也且该女人喜欢该男人也胜过其配偶胜过其配偶, 则该婚配方案
15、称为不稳定的则该婚配方案称为不稳定的. 安排稳定的婚配方安排稳定的婚配方案的问题称为案的问题称为稳定婚配问题稳定婚配问题。131.1网络优化问题的例子网络优化问题的例子 网络优化网络优化或或网络流网络流（Network Flows)或或网络规划网络规划（Network Programming)特点特点： （1）与图形有关，或易于用与图形有关，或易于用图形方式表示图形方式表示（2）优化问题：从若干可能优化问题：从若干可能的安排或方案中寻求某种意义的安排或方案中寻求某种意义下的最优安排或方案下的最优安排或方案141.2 1.2 图与网络图与网络 定义定义 定义定义1.1 一个有向图一个有向图(Di
16、rected Graph 或或 Digraph) G是由一个是由一个非空有限集合非空有限集合V(G)和和V(G)中某些元素的中某些元素的有序对有序对集合集合A(G)构成构成的二元组，记为有向图的二元组，记为有向图G=(V(G)，A(G). 其中其中V(G) 称为图称为图G的顶点集的顶点集(Vertex Set)或节点集或节点集(Node Set)，V(G)中的每一个元中的每一个元素称为该图的一个顶点素称为该图的一个顶点(Vertex)或节点或节点(Node)； A(G)称为图称为图G的弧集的弧集(Arc Set)，A(G)中的每一个元素中的每一个元素(即即V(G)中某两个元素中某两个元素的有序
17、对的有序对) 称为该图的一条从到的弧称为该图的一条从到的弧 (Arc). 在不引起混淆的在不引起混淆的情况下，记号情况下，记号V(G)和和A(G)中也可以省略中也可以省略G，即分别记顶点集、，即分别记顶点集、弧集为弧集为V和和A，而记有向图，而记有向图G=（V，A）.如果对有向图如果对有向图G中的每条弧赋予一个或多个实数，得中的每条弧赋予一个或多个实数，得到的有向图称为赋权有向图或有向网络到的有向图称为赋权有向图或有向网络, 简称为网络简称为网络(Network). 151.2 1.2 图与网络图与网络 例例5a1a1v2v3a3v4a4v5v2a6a图G=(V，A)，其中顶点集V= 弧集A=
18、 弧,54321vvvvv,654321aaaaaa),(211vva ),(212vva ),(323vva ),(434vva ),(145vva ),(336vva 16弧的端点(Endpoint)，尾(Tail)，头(Head)；顶点相邻(Adjacent)，邻居(Neighbor)；弧与顶点关联 (Incident)，出弧(Outgoing Arc)，入弧(Incoming Arc)；弧相邻 (Adjacent)；环 (Loop)，孤立点(Isolated Vertex)；图的阶(Order) 顶点的度（Degree），出度，入度，奇点，偶点没有环、且没有多重弧的图称为简单图(Sim
19、ple Graph)1.2 1.2 图与网络图与网络 基本概念基本概念171.2 1.2 图与网络图与网络 子子图图 称为G的子图(Subgraph)，AAVV,),(AVG ，),(AVG 图的支撑子图 (Spanning Subgraph，又称生成子图)是包含G 的所有顶点的子图（顶点、弧）导出子图(Induced Subgraph) 图的导出子图是唯一的；图的支撑子图一般是不唯一的 有向图中的途径(Walk)是该图的一些顶点 和弧 所组成的子图，这些顶点与弧可以交错排列成点弧序列 其中 或 riii,21121,raaarriaaiai,12211),(1kkkiia) 1, 2 , 1
20、)(,(1kkiiakkk 如果该序列中的所有弧都指向同一方向，即 ，则该途径称为有向途径(Directed Walk). ) 1, 2 , 1)(,(1kkiiakkk181.2 1.2 图与网络图与网络 路、圈路、圈 有向图中的路 (Path)是该图的不包含重复顶点的途径. 方向与路的起点到终点的方向一致的弧称为路的前向弧(Forward Arc)；否则称为后向弧或反向弧(Backward Arc). P,P+,P- 有向图中的有向路(Directed Path)是该图的不包含重复顶点的有向途径，即不包含反向弧的路. 有向图的圈(Cycle) 是起点和终点重合，且不含其他重复顶点的途径.
21、C,C+,C- 有向图中的有向圈(Directed Cycle)是该图的不包含反向弧的圈. 不包含有向圈的图称为无圈图(Acyclic Graph). 191.2 1.2 图与网络图与网络 路、圈路、圈 对于有向图中的两个顶点，如果在图中至少存在一条路把它们连接起来，则称这两个顶点是连通的(Connected). 如果图中任意两个顶点都是连通的，则称该图为连通的(Connected)；否则称为不连通的(Disconnected). 不连通图可以分解成一些连通分支的并，而连通图只有一个连通分支. 所谓连通分支(Component) ，就是图中的极大连通子 图。如果有向图中从任意一个顶点出发，都存
22、在至少一条有向路到达任意另一个顶点，则称该图为强连通的(Strongly Connected). 同样可以类似地定义强连通分支. 若 ，则称两个端点分别位于S，T的弧为一个割（cut），记为 S，T= TSVTSTSVTS;,;,|),(TjSiAji,|),(TjSiAij201.2 1.2 图与网络图与网络 无向图无向图 定义定义1.2 一个无向图一个无向图(Undirected Graph) G是由一个非空有是由一个非空有限集合限集合V和和V中某些中某些 元素元素 的的无序对无序对集合集合E 构成的，即构成的，即G=(V，E). 其中其中 V=V(G) 仍称为仍称为 图图G的顶点集的顶点
23、集(Vertex Set)或或 节点集节点集(Node Set)，V中的每一个中的每一个 元素元素 称为该图的称为该图的 一个顶点一个顶点(Vertex) 或或 节点节点(Node)；E=E(G)=通常称为图通常称为图G的边集合的边集合(Edge Set)，E中的每一个元素中的每一个元素(即即V 中某两个元素的无序对中某两个元素的无序对) 称为该图的一称为该图的一条边条边(Edge). 边上赋权的无向图称为赋权无向图或无向网络边上赋权的无向图称为赋权无向图或无向网络(Undirected Network). 本课程中，在不引起混淆的情况下，有时将有向图和无向图都简称为图(Graph)；也不再对
24、弧和边的概念作严格区分。并且，对图和网络的概念也不再作严格区分。211.2 1.2 图与网络图与网络 两种特殊的两种特殊的图图 若若图图G=(V，E)的顶点集的顶点集V可以表示成两个互不相交的非空可以表示成两个互不相交的非空子集子集S，T的并集，且使得的并集，且使得G中每一条边的一个端点在中每一条边的一个端点在S中，另中，另一端点在一端点在T 中，则称中，则称G为二部图为二部图/ /二分图二分图(Bibartite Graph). 当当|S|=p，|T|=q，且，且S与与T中任意两对顶点都相邻时，称中任意两对顶点都相邻时，称G为完全为完全二部图，记为二部图，记为Kp,q. 类似地，也可以定义有
25、向的完全图和有向的完全二部图. Kn的弧的数量为的弧的数量为 n(n-1)/21)/2 若无向图若无向图G的任意两个顶点间有且只有一条边相连，则称其的任意两个顶点间有且只有一条边相连，则称其为完全图为完全图 (Complete Graph). n阶完全图记为阶完全图记为Kn. Kp,q的弧的数量为的弧的数量为 pq 221.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.1 1.3.1 邻接矩阵邻接矩阵(Adjacency Matrix)(Adjacency Matrix)表示法表示法 图图G=(V，A)的邻接矩阵的邻接矩阵C是如下定义的：是如下定义的：C是一是一个个 的的0-1矩阵
26、，即矩阵，即每行元素之和正好是对应顶点的出度， 每列元素之和正好是对应顶点的入度. nnG=(V，A)是一个简单有向图|V|=n，|A|=m ,1 , 0)(nnnnijcC.),(, 1,),(, 0AjiAjicij在邻接矩阵的所有元素中，只有m个为非零元. 231.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.1 1.3.1 邻接矩阵表示法邻接矩阵表示法 0110010100000100100000110对于网络中的权，也可以用类似邻接矩阵的矩阵表示. 只是此时一条弧所对应的元素不再是1，而是相应的权而已. 如果网络中每条弧赋有多种权，则可以用多个矩阵表示这些权. 12345
27、241.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.1.3.2 2 关联矩阵关联矩阵(Incidence Matrix)(Incidence Matrix)表示法表示法 图图G=(V，A)的邻接矩阵的邻接矩阵C是如下定义的：是如下定义的：C是一是一个个 的矩阵，即的矩阵，即每行元素1的个数正好是对应顶点的出度， 每行元素-1的个数正好是对应顶点的入度. mnG=(V，A)是一个简单有向图|V|=n，|A|=m 在关联关联矩阵的所有元素中，只有2m个为非零元. ,1 , 0 , 1)(mnmnikbB其他。，, 0),(, 1,),(, 1AijkVjAjikVjbik251.3
28、1.3 图与网络的数据结构图与网络的数据结构 1.3.2 1.3.2 关联矩阵表示法关联矩阵表示法 如果网络中每条弧赋有一个权，我们可以把关联矩阵增加一行, 把每一条弧所对应的权存贮在增加的行中. 如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存贮在增加的行中. 11100000101101000101101000001101000000111234512378654261.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.3 1.3.3 弧表（弧表（Arc List)Arc List)表示法表示法 所谓图的弧表所谓图的弧表, , 也就是图的弧集合中
29、的所有有序也就是图的弧集合中的所有有序对对. . 弧表表示法直接列出所有弧的起点和终点，弧表表示法直接列出所有弧的起点和终点，共需共需2 2m个存贮单元，因此当网络比较稀疏时比个存贮单元，因此当网络比较稀疏时比较方便较方便. . G=(V，A)是一个简单有向图|V|=n，|A|=m 271.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.3 1.3.3 弧表表示法弧表表示法 起点11234455终点23423534权 (例)8964036712345281.3 1.3 图与网络的数据结构图与网络的数据结构 G=(V，A)是一个简单有向图|V|=n，|A|=m 1.3.4 1.3.4
30、邻接表邻接表 (Adjacency Lists)(Adjacency Lists)表示法表示法 图的邻接表是图的所有节点的邻接表的集合图的邻接表是图的所有节点的邻接表的集合; ; 而而对每个节点，它的邻接表就是它的所有出弧对每个节点，它的邻接表就是它的所有出弧. . 对于有向图G=（V，A），一般用A（i）表示节点i的邻接表，即节点i的所有出弧构成的集合或链表（实际上只需要列出弧的另一个端点，即弧的头）. 这种记法我们在本书后面将会经常用到. 291.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.4 1.3.4 邻接表表示法邻接表表示法 1223452839046024030530
31、36470单向链表(指针数组) A(1)=2,3A(2)=4A(3)=2A(4)=3,5A(5)=3,412345301.3 1.3 图与网络的数据结构图与网络的数据结构 1.3.5 1.3.5 星形（星形（StarStar）表示法）表示法 前向星形前向星形( (Forward StarForward Star) )表示法表示法 节点对应的出弧的起始地址编号数组（记为point）为 记录弧信息的数组为弧编号12345678起点11234455终点23423534权89640367节点号i123456起始地址point(i)1345791234512378654311.3 1.3 图与网络的数据
32、结构图与网络的数据结构 1.3.5 1.3.5 星形（星形（StarStar）表示法）表示法 反向星形反向星形(Reverse Star)(Reverse Star)表示法表示法 节点对应的入弧的起始地址编号数组（记为rpoint）为 记录弧信息的数组为1234523756841节点号i123456起始地址rpoint(i)113689弧编号12345678终点起点2233344531145524权48906763321.3 1.3 图与网络的数据结构图与网络的数据结构 几点说明几点说明（1）星形表示法和邻接表方法常用）星形表示法和邻接表方法常用. 星形表示法的星形表示法的优点是占用的存贮空间
33、较少优点是占用的存贮空间较少;邻接表方法增加或删除邻接表方法增加或删除一条弧所需的计算工作量很少一条弧所需的计算工作量很少（2）当网络不是简单图，而是具有平行弧）当网络不是简单图，而是具有平行弧(即多重弧即多重弧)时，邻接矩阵法是不能采用的时，邻接矩阵法是不能采用的. 其他方法则可以推广其他方法则可以推广到可以处理平行弧的情形到可以处理平行弧的情形. （3 3）无向图处理类似）无向图处理类似. . 如无向图的关联矩阵只含如无向图的关联矩阵只含有元素有元素0 0和和+1. +1. 在邻接表和星形表示中，每条弧会被在邻接表和星形表示中，每条弧会被存贮两次存贮两次; ;反向星形表示显然是没有必要的，
34、等等反向星形表示显然是没有必要的，等等. . 331.4 1.4 计算复杂性的概念计算复杂性的概念 定义定义1.3 1.3 所谓组合所谓组合( (最最) )优化优化(Combinatorial Optimization)(Combinatorial Optimization)又称离散优化又称离散优化（Discrete OptimizationDiscrete Optimization），它是通过数学方法去寻找），它是通过数学方法去寻找离散离散事件的最事件的最优编排、分组、次序或筛选等优编排、分组、次序或筛选等. . 这类问题可用数学模型描述为：这类问题可用数学模型描述为： 优化问题三要素优化问
35、题三要素: (Min,f,F)或或(Max,f,F)min s.t. f xg xxD( )( ),0其中其中D表示表示有限个点有限个点组成的集合组成的集合( (定义域定义域) ) , , f为目标函数为目标函数,F=x|x D, g(x) 0为可行域为可行域 1.4.1 1.4.1 组合优化组合优化 定义定义341.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.1 1.4.1 组合优化组合优化 例例例例1.7 0-11.7 0-1背包问题背包问题( (knapsack problem) )设有一个容积为设有一个容积为b的背包，的背包，n个体积分别为个体积分别为ai，价值分别为，价值分
36、别为ci的物品，如何以的物品，如何以最大的价值装包？这个问题称为最大的价值装包？这个问题称为0-10-1背包问题背包问题. . 用数学规划模型表示为：用数学规划模型表示为： D= 0,1nmaxc xiiin1s ta xbiiin. . 1.,.,1 ,1 , 0nixi例例1.10 1.10 装箱问题装箱问题(Bin Packing)(Bin Packing)如何以个数最少的尺寸为如何以个数最少的尺寸为1 1的箱子装进的箱子装进n n个尺寸不超过个尺寸不超过1 1的物品，该的物品，该问题为装箱问题问题为装箱问题. . 351.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.1 1.4
37、.1 组合优化组合优化 例例例例1.9 1.9 整数线性规划整数线性规划(Integer Linear Programming)(Integer Linear Programming) (IP) . minc xTs tAxb. . xxZn0, 我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数( (或有理数或有理数) ). .许多组合优化问题可以用整数规划模型表示许多组合优化问题可以用整数规划模型表示, ,但有时不如直接用自然但有时不如直接用自然语言描述简洁语言描述简洁 361.4 1.4 计算复杂性的概念计算复杂性的概念
38、1.4.2 1.4.2 多项式时间算法多项式时间算法 对于组合优化问题，我们关心的一般不是最优对于组合优化问题，我们关心的一般不是最优解的解的存在性存在性和和唯一性唯一性，而是如何找到有效的，而是如何找到有效的算算法法求得一个最优解求得一个最优解. . 那么如何衡量算法的优劣、那么如何衡量算法的优劣、有效与无效呢？有效与无效呢？ 完全枚举法可以求得最优解,但枚举时间有时不可能接受 ATSP: (ATSP: (n-1)!-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30! / 10e+10 2.65e+22 (秒)即 2.65e+22 / (365*24*60*60) 8
39、.4e+13 (年) 371.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 构造构造算法算法的目的是能够解决问题（或至少是问题某个的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例子类）的所有实例而不单单是某一个实例 问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数. 问题通过下面的描述给定：（1）描述所有参数参数的特性，（2）描述答案答案所满足的条件. 问题中的参数赋予了具体值的例子称为实例(instance). 衡量一个算法的好坏通常是用算法中的加、减、乘、衡量一个算法的好坏通常是用
40、算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）除和比较等基本运算的总次数（计算时间）C（I）同）同实例实例I在计算机计算时的二进制输入数据在计算机计算时的二进制输入数据(输入规模输入规模/长长度度d（I）)的大小关系来度量的大小关系来度量. C(I) = f(d(I) : 该函数关系称为算法的计算复杂性（度）计算复杂性（度）381.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 对于一个正整数对于一个正整数x，二进制表示是以，二进制表示是以如ATSP:二进制输入长度总量不超过 (不考虑正负号、分隔符等)的系数来表示，其中，的系数来
41、表示，其中， xaaaassss2221110，0sa., 1 , 0,1 , 0siaix的二进制数的位数不超过 log21x Ln nP()log | |12Pd dijij |0假设每一个数据(距离)的绝对值都有上界K 输入长度是输入长度是n的多项式函数的多项式函数所以网络优化中常用n,m等表示输入规模 Ln nPn nK()log | |()(log)11 122391.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 例例 构造构造算法算法将将n个自然数从小到大排列起来个自然数从小到大排列起来 算法 输入自然数自然数a(1),a(2)
42、,a(n). for (i=1;in;i+)for (j=i+1;ja(j) k=a(i);a(i)=a(j);a(j)=k;即该算法的计算复杂性（度）为即该算法的计算复杂性（度）为O( (n2 2) )基本运算的总次数基本运算的总次数( (最坏情形）：最坏情形）：2n(n-1)= =O( (n2 2) )比较：比较： （n-1)+(n-2)+n-1)+(n-2)+1=n(n-1)/2+1=n(n-1)/2赋值：赋值： 3(n-1)+(n-2)+3(n-1)+(n-2)+1=3n(n-1)/2+1=3n(n-1)/2401.4 1.4 计算复杂性的概念计算复杂性的概念 定义定义1.4 假设问题
43、和解决该问题的一个算法已经给定，若存在假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式为多项式函数且对该问题函数且对该问题任意的一个实例任意的一个实例I，使得计算时间，使得计算时间成立，则称该算法为解决该问题的多项式成立，则称该算法为解决该问题的多项式( (时间时间) )算法算法(Polynomial time algorithm). 当当不存在不存在多项式函数多项式函数g(x)使得使得上式上式成立时，称相应的算法是成立时，称相应的算法是非非多项式时多项式时间算法间算法, 或指数或指数( (时间时间) )算法算法(Exponential time algorithm)输入规模增大
44、时，多项式时间算法的基本计算总次数的增加速度相对较慢. 为常数）（其中)()(ILgIC1.4.2 1.4.2 多项式时间算法多项式时间算法注：上面定义中，要求对该问题的任意一个实例均成立注：上面定义中，要求对该问题的任意一个实例均成立 ，这种分析方法称为这种分析方法称为最坏性能分析（最坏性能分析（Worst-Case AnalysisWorst-Case Analysis）)()(ILgIC411.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 近似值计算机提速10倍n10100100010121013nlogn3366499660.9e1
45、10.87e12n21001041061063.16e6n310001061091042.15e4108n410121016102010182n10241.27e30 1.05e301 404310n1010101001010001213nlogn20791.93e13 7.89e297995n!3628800101584e25671415421.4 1.4 计算复杂性的概念计算复杂性的概念 1.4.2 1.4.2 多项式时间算法多项式时间算法 算法复杂性研究中算法复杂性研究中: :常将算法的计算时间表示为： 问题中的简单而典型的参数(如网络优化中网络优化中n,m), 以及 问题中出现的数值(
46、如弧上的权)的最大值(按绝对值)K等自变量的函数关系如果算法运行时间的上界是如果算法运行时间的上界是m,n和和K的多项式函数，则称相应的算法为伪的多项式函数，则称相应的算法为伪多项式（多项式（PseudopolynomialPseudopolynomial）（时间）算法，或拟多项式（时间）算法）（时间）算法，或拟多项式（时间）算法. . 实际问题的输入规模/长度一定是m,n和logK的一个多项式函数. 所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数. 特别地, 如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）, 则称相应的算法为强多项式(Strong
47、ly Polynomial)时间算法. )()()log,()(2211ILgICKnmgIL)log,()(33KnmgIC一般来说，伪多项式算法并不是多项式算法一般来说，伪多项式算法并不是多项式算法. . 431.4 1.4 计算复杂性的概念计算复杂性的概念 TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存在定义定义1.5 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial). 同样道理, 可以定义强多项式问题,伪多项式问题等.TSP是否存在是否存在多项式时间算法
48、? - 这是21世纪数学和计算机科学的挑战性问题之一1.4.3 多项式问题多项式问题44布 置 作 业目的掌握图与网络的基本概念掌握算法复杂性的基本概念内容网络优化网络优化第第49-51页页 5; 9; 14; 16更正：第更正：第14题题“ ”改为改为 )(lognOkn)1(lognnOn45网网 络络 优优 化化 第第 1 1 章章 概概 论论 ( (第第2 2讲讲) ) Network Optimization清华大学数学科学系 谢金星办公室：理科楼1308# （电话：62787812）Email: http:/ 1.5 NP,NPCNP,NPC和和NP-hardNP-hard概念概念
49、( (计算复杂性理论）计算复杂性理论）46运筹学的运筹学的ABC - ABC - A2B2 2C2 2 （至少是组合优化、理论计算机科学的（至少是组合优化、理论计算机科学的ABCABC）q Approximation Algorithm ( Approximation Algorithm (近似算法近似算法) )；HeuristicHeuristicq Branch and Bound Branch and Bound （分枝定界）（分枝定界）q Computational Complexity Computational Complexity （计算复杂性）（计算复杂性）口莫开，开口常说错。
50、口莫开，开口常说错。理论在监督，理论在监督，众目睽睽难逃脱。众目睽睽难逃脱。计算复杂性理论的计算复杂性理论的“Bible”Bible”GareyGarey M R.and Johnson.D S, Computers and intractability : a guide to the theory M R.and Johnson.D S, Computers and intractability : a guide to the theory of NP-completeness. San Francisco :.W.H. Freeman and Co., 1979 of NP-compl