资源描述：
《计算复杂性的概念课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1网络优化第1章概论NetworkOptimization1.4计算复杂性的概念1定义1.3所谓组合(最)优化(CombinatorialOptimization)又称离散优化（DiscreteOptimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：优化问题三要素:(Min,f,F)或(Max,f,F)其中D表示有限个点组成的集合(定义域),f为目标函数,F={x
2、xD,g(x)0}为可行域1.4.1组合优化问题1、定义2给定n个容积分别为ai，价值分别为c
3、i的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：D={0,1}n2、例子例1.70-1背包问题(knapsackproblem)3一个商人到n城市推销商品，两个城市之间的距离为dij，如何选择一条道路使得商人每个城市走一遍之后回到起点，且所走的路径最短？其数学模型描述为：例1.8旅行商问题(TSP)D={0,1}n×(n-1)4例1.9整数线性规划(IntegerLinearProgramming)(ILP).我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).ILP中系数
4、是有理数时，都可以处理成整数的情况。5以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，物品的尺寸为wj，如何使所用的箱子个数最少?说明：许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁，故，大量的组合优化问题是通过文字语言叙述的。例1.10装箱问题(BinPacking)61.4.2多项式时间算法对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？完全枚举法可以求得最优解,但枚举时间有时不可能接受ATSP:(n-1
5、)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+10>2.65e+22(秒)即2.65e+22/(365*24*60*60)>8.4e+13(年)7问题（Problem）：是需要回答的一般性提问，通常含有若干个满足一定条件的参数.实例(instance)：问题中的参数赋予了具体值的例子。一、问题与实例的定义：问题通过下面的描述给定：（1）描述所有参数的特性（2）描述答案所满足的条件.问题实例TSP问题中各参数:100个城市，城市间距离已知.背包问题问题中各参数:4个物品，大小分别为4,3,
6、2,2.价值分别为8,7,5,7.包的大小为6.整数线性规划问题中的n,A,b,c已知.8构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例。衡量一个算法的好坏，通常由以下两个要素的关系来衡量：(1)C(I)：求解实例I的计算时间，即算法中的加、减、乘、除和比较等基本运算的总次；(2)d(I)：实例I的输入规模/长度，即实例I在计算机计算时的二进制输入数据的大小.输入长度/规模的计算方法：对于一个正整数x，其二进制为：二、多项式时间算法9正整数x输入长度的估计：10定义1.4假设问题和解决该
7、问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间成立，则称该算法为解决该问题的多项式(时间)算法(Polynomialtimealgorithm).输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢。当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或指数(时间)算法(Exponentialtimealgorithm)11例1：上述的非对称ATSP问题，设城市数为n，第1个城市为始终点。假设每一个数据(距离)的绝对值都有上界K，则：说明：输入长
8、度不超过n的一个多项式函数。12所以，枚举算法对TSP来说，不是一个多项式时间的算法。TSP问题至今没有找到多项式时间算法,但尚未证明其不存在TSP是否存在多项式时间算法?----这是21世纪数学和计算机科学的挑战性问题之一13例2：构造算法将n个自然数从小到大排列起来算法输入自然数a(1),a(2),…,a(n).for(i=1;ia(j)){k=a(i);a(i)=a(j);a(j)=k;}即该算法的计算复杂性（度）为O(n2)，是一个多项式算法。基本
9、运算的总次数(最坏情形）：2n(n-1)=O(n2)比较：（n-1)+(n-2)+…+1=n(n-1)/2赋值：3{(n-1)+(n-2)+…+1}=3n(n-1)/214三、强多项式算法和伪多项式算法算法复杂性研究中:常将算法的计算时间表示为：问题中的简单而典型的参数(如网络优化中n,m)问题中出现的
