计算复杂性的概念.

1、1 1网网 络络 优优 化化 第第 1 1 章章 概概 论论 Network Optimization1.4 1.4 计算复杂性的概计算复杂性的概念念 2定义定义1.3 1.3 所谓所谓组合组合( (最最) )优化优化(Combinatorial Optimization)(Combinatorial Optimization)又称离散优化又称离散优化（Discrete OptimizationDiscrete Optimization），它是通过数学方法去寻找），它是通过数学方法去寻找离散离散事件的最事件的最优编排、分组、次序或筛选等优编排、分组、次序或筛选等. . 这类问题可用数学模型描述

2、为：这类问题可用数学模型描述为： 优化问题三要素优化问题三要素: (Min, f, F)或或 (Max, f, F)min ( )s.t. ( )0, ,f xg xxD 其中其中D表示表示有限个点有限个点组成的集合组成的集合( (定义域定义域) ) , , f为目标函数为目标函数,F=x|x D, g(x) 0为可行域为可行域 1.4.1 1.4.1 组合优化问题组合优化问题1 1、定义、定义3给定给定n个容积分别为个容积分别为ai，价值分别为，价值分别为ci的物品的物品. .设有一个容积为设有一个容积为b的背包，如的背包，如何以最大的价值装包？用数学规划模型表示为：何以最大的价值装包？用数

3、学规划模型表示为： D= 0,1n1maxniiic x 1. . niiis ta xb 0,1, 1,., .ixin2 2、例子、例子例例1.7 0-1背包问题背包问题(knapsack problem)4一个商人到一个商人到n城市推销商品，两个城市之间的距离为城市推销商品，两个城市之间的距离为dij，如何，如何选择一条道路使得商人每个城市走一遍之后回到起点，且所走选择一条道路使得商人每个城市走一遍之后回到起点，且所走的路径最短？其数学模型描述为：的路径最短？其数学模型描述为： minijijijd x 1. . 1, 1, 2,nijjs txin 0,1, ,1,2, ,.ijxi

4、jn ij例例1.8 旅行商问题旅行商问题(TSP)1 1, 1, 2,nijixjn , |1, 2|2, 1, 2,niji jSxSSnSn D= 0,1n(n- -1)5例例1.9 1.9 整数线性规划整数线性规划(Integer Linear Programming)(Integer Linear Programming) (ILP)(ILP) . minc xTs tAxb. . xxZn0, 我们假设线性整数规划的参数（约束矩阵和右端项系数）我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数都是整数( (或有理数或有理数) ). .ILPILP中系数是有理数时，都可以处理

5、成整数的情况。中系数是有理数时，都可以处理成整数的情况。6以尺寸为以尺寸为1的箱子装进给定的的箱子装进给定的n个尺寸不超过个尺寸不超过1的物品，物的物品，物品的尺寸为品的尺寸为wj ，如何使所用的箱子个数最少，如何使所用的箱子个数最少? 说明说明：许多组合优化问题可以用整数规划模型表示：许多组合优化问题可以用整数规划模型表示, ,但有时但有时不如直接用自然语言描述简洁不如直接用自然语言描述简洁，故，大量的组合优化问题，故，大量的组合优化问题是通过文字语言叙述的。是通过文字语言叙述的。例例1.10 装箱问题装箱问题(Bin Packing)71.4.2 1.4.2 多项式时间算法多项式时间算法

6、对于组合优化问题，我们关心的一般不是最优对于组合优化问题，我们关心的一般不是最优解的解的存在性存在性和和唯一性唯一性，而是如何找到有效的，而是如何找到有效的算算法法求得一个最优解求得一个最优解. . 那么如何衡量算法的优劣、那么如何衡量算法的优劣、有效与无效呢？有效与无效呢？ 完全枚举法可以求得最优解完全枚举法可以求得最优解,但但枚举时间有时不可能接受枚举时间有时不可能接受 ATSP: (ATSP: (n-1)!-1)!枚举枚举(TOUR,(TOUR,周游或环游周游或环游) )设计算机每秒进行设计算机每秒进行100100亿次枚举亿次枚举, ,需需30! / 10e+10 2.65e+22 (3

7、0! / 10e+10 2.65e+22 (秒秒) )即即 2.65e+22 / (3652.65e+22 / (365* *2424* *6060* *60)60) 8.4e+13 ( 8.4e+13 (年年) ) 8问题（问题（Problem）：）：是需要回答的一般性提问，通常含有若干是需要回答的一般性提问，通常含有若干个满足一定条件的参数个满足一定条件的参数. 实例实例(instance)：问题中的参数赋予了具体值的例子。问题中的参数赋予了具体值的例子。一、问题与实例的定义：一、问题与实例的定义： 问题通过下面的描述给定：（问题通过下面的描述给定：（1）描述所有参数的特性）描述所有参数的

8、特性 （2）描述答案所满足的条件）描述答案所满足的条件. 问题问题实例实例TSP 问题中各参数问题中各参数:100个城市，城市间距离个城市，城市间距离 已知已知. 背包问题背包问题问题中各参数问题中各参数: 4个物品，大小分别为个物品，大小分别为4,3,2,2. 价价值分别为值分别为8,7,5,7. 包的大小为包的大小为6. 整数线性规划整数线性规划问题中的问题中的n,A,b,c已知已知. 9构造构造算法算法的目的是能够解决问题（或至少是问题某个子类）的的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例。所有实例而不单单是某一个实例。 衡量一个算法的好坏，通常由以下两个

9、要素的关系来衡量：衡量一个算法的好坏，通常由以下两个要素的关系来衡量：(1) C(I)：求解实例：求解实例I的计算时间，即算法中的加、减、乘、的计算时间，即算法中的加、减、乘、除和比较等基本运算的总次；除和比较等基本运算的总次；(2) d(I)：实例：实例I的输入规模的输入规模/长度，即实例长度，即实例I在计算机计算时的在计算机计算时的二进制输入数据的大小二进制输入数据的大小. 输入长度输入长度/ /规模的计算方法：规模的计算方法： 对于一个正整数对于一个正整数x，其二进制为：，其二进制为：1110222ssssxaaaa 二、多项式时间算法二、多项式时间算法10正整数正整数 x 输入长度的估

10、计输入长度的估计： 11定义定义1.4 假设问题和解决该问题的一个算法已经给定，若存在假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题为多项式函数且对该问题任意的一个实例任意的一个实例I，使得计算时间，使得计算时间成立，则称该算法为解决该问题的成立，则称该算法为解决该问题的多项式多项式( (时间时间) )算法算法(Polynomial time algorithm). 输入规模增大时，多项式时间算法的基本计算总次数的增输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢。加速度相对较慢。( )( ( )C Ig L I （其其中中 为为常常数数）当不存在

11、多项式函数当不存在多项式函数g(x)使得使得上式上式成立时，称相应的算法成立时，称相应的算法是非是非多项式时间算法多项式时间算法, 或或指数指数( (时间时间) )算法算法(Exponential time algorithm)12例例1 1：上述的非对称上述的非对称ATSPATSP问题，设城市数为问题，设城市数为n，第，第1 1个个城市为始终点。城市为始终点。2(1)log |,Ln nP |0ijijPdd 其其中中假设每一个数据假设每一个数据( (距离距离) )的绝对值都有上界的绝对值都有上界K，则：，则： 说明：输入长度不超过说明：输入长度不超过n的一个多项式函数。的一个多项式函数。2

12、2(1)log |(1)(1log)Ln nPn nK 13所以，枚举算法对所以，枚举算法对TSPTSP来说，不是一个多项式时间的算法。来说，不是一个多项式时间的算法。TSPTSP问题至今没有找到多项式时间算法问题至今没有找到多项式时间算法, ,但尚未证明其不存在但尚未证明其不存在TSP是否存在是否存在多项式时间算法多项式时间算法? - ? - 这是这是2121世纪数学和计算机科学的挑战性问题之一世纪数学和计算机科学的挑战性问题之一14例例2 2： 构造构造算法算法将将n个自然数从小到大排列起来个自然数从小到大排列起来 算法算法 输入输入自然数自然数a(1),a(2),a(1),a(2),a(

13、n).,a(n). for (i=1;in;i+) for (i=1;in;i+)for (j=i+1;j=n;j+)for (j=i+1;ja(j)if (a(i)a(j) k=a(i);a(i)=a(j);a(j)=k;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赋

14、值：赋值： 3(n-1)+(n-2)+3(n-1)+(n-2)+1=3n(n-1)/2+1=3n(n-1)/215三、强多项式算法和伪多项式算法三、强多项式算法和伪多项式算法 算法复杂性研究中算法复杂性研究中: :常将算法的计算时间表示为：常将算法的计算时间表示为： 问题中的简单而典型的参数问题中的简单而典型的参数( (如网络优化中如网络优化中n,m) 问题中出现的数值问题中出现的数值( (如弧上的权如弧上的权) )的最大值的最大值( (按绝对值按绝对值) )K等自变量的函数关系等自变量的函数关系如果算法运行时间的上界是如果算法运行时间的上界是m,n和和K的多项式函数，则称相应的算法为的多项式

15、函数，则称相应的算法为伪伪多项式（多项式（PseudopolynomialPseudopolynomial）（时间）算法）（时间）算法，或，或拟多项式（时间）算法拟多项式（时间）算法. . 实际问题的输入规模实际问题的输入规模/ /长度一定是长度一定是m,n和和logK的一个多项式函数的一个多项式函数. . 所以：所以：多项式算法等价于其运行时间的上界是多项式算法等价于其运行时间的上界是m,n和和logK的多项式函数的多项式函数. . 特别地特别地, , 如果运行时间的上界是如果运行时间的上界是m,n的多项式函数（即该多项式函数不包的多项式函数（即该多项式函数不包含含loglogK）, , 则称相应的算法为则称相应的算法为强多项式强多项式(Strongly Polynomial)(Strongly Polynomial)时间算法时间算法. . 1122( )(, ,log)( )( ( )L Ig m nKC IgL I 33( )(, ,log)C Igm nK 一般来说，伪多项式算法并不是多项式算法一般来说，伪多项式算法并不是多项式算法. . 16定义定义1.5 对于给定的一个优化问题，若对于给定的一个优化问题，