计算复杂性的概念

11网

络

优

化

第1章概论

NetworkOptimization1.4计算复杂性的概念

2定义1.3所谓组合(最)优化(CombinatorialOptimization)又称离散优化（DiscreteOptimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：

优化问题三要素:(Min,f,F)或

(Max,f,F)

其中D表示有限个点组成的集合(定义域)

,f为目标函数,F={x|xD,g(x)0}为可行域

1.4.1组合优化问题1、定义3给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：

D={0,1}n

2、例子例1.70-1背包问题(knapsackproblem)4一个商人到n城市推销商品，两个城市之间的距离为dij，如何选择一条道路使得商人每个城市走一遍之后回到起点，且所走的路径最短？其数学模型描述为：

例1.8旅行商问题(TSP)D={0,1}n×(n-1)5例1.9整数线性规划(IntegerLinearProgramming)

(ILP)

.

我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).ILP中系数是有理数时，都可以处理成整数的情况。6以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，物品的尺寸为wj，如何使所用的箱子个数最少? 说明：许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁，故，大量的组合优化问题是通过文字语言叙述的。例1.10装箱问题(BinPacking)71.4.2多项式时间算法对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？

完全枚举法可以求得最优解,但枚举时间有时不可能接受

ATSP:(n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需

30!/10e+10>2.65e+22(秒)即2.65e+22/(365*24*60*60) >8.4e+13(年)8问题（Problem）：是需要回答的一般性提问，通常含有若干个满足一定条件的参数.实例(instance)：问题中的参数赋予了具体值的例子。一、问题与实例的定义：

问题通过下面的描述给定：（1）描述所有参数的特性（2）描述答案所满足的条件.

问题实例TSP问题中各参数:100个城市，城市间距离已知.背包问题问题中各参数:4个物品，大小分别为4,3,2,2.价值分别为8,7,5,7.包的大小为6.整数线性规划问题中的n,A,b,c已知.9构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例。

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

输入长度/规模的计算方法：

对于一个正整数x，其二进制为：二、多项式时间算法10正整数x输入长度的估计：

11定义1.4假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间成立，则称该算法为解决该问题的多项式(时间)算法(Polynomialtimealgorithm).输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢。当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或指数(时间)算法(Exponentialtimealgorithm)12例1：上述的非对称ATSP问题，设城市数为n，第1个城市为始终点。假设每一个数据(距离)的绝对值都有上界K，则：

说明：输入长度不超过n的一个多项式函数。13所以，枚举算法对TSP来说，不是一个多项式时间的算法。TSP问题至今没有找到多项式时间算法,但尚未证明其不存在TSP是否存在多项式时间算法?----这是21世纪数学和计算机科学的挑战性问题之一14例2：构造算法将n个自然数从小到大排列起来

算法输入自然数a(1),a(2),…,a(n).for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(a(i)>a(j)){ k=a(i);a(i)=a(j);a(j)=k; }即该算法的计算复杂性（度）为O(n2)，是一个多项式算法。基本运算的总次数(最坏情形）：2n(n-1)=O(n2)

比较：（n-1)+(n-2)+…+1=n(n-1)/2

赋值：

3{(n-1)+(n-2)+…+1}=3n(n-1)/215三、强多项式算法和伪多项式算法算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中n,m)问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(StronglyPolynomial)时间算法.一般来说，伪多项式算法并不是多项式算法.16定义1.5对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，