资源描述：
《计算复杂性的概念》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1.4计算复杂性的概念定义1.3所谓组合(最)优化(CombinatorialOptimization)又称离散优化（DiscreteOptimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：优化问题三要素:(Min,f,F)或(Max,f,F)其中D表示有限个点组成的集合(定义域),f为目标函数,F={x
2、xD,g(x)0}为可行域1.4.1组合优化–定义11.4计算复杂性的概念1.4.1组合优化–例例1.70-1背包问题(knapsackproblem)给
3、定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：D={0,1}n例1.10装箱问题(BinPacking)以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，如何使所用的箱子个数最少?21.4计算复杂性的概念1.4.1组合优化–例例1.9整数线性规划(IntegerLinearProgramming)(IP).我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁31.4计
4、算复杂性的概念1.4.2多项式时间算法对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？完全枚举法可以求得最优解,但枚举时间有时不可能接受ATSP:(n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+10>2.65e+22(秒)即2.65e+22/(365*24*60*60)>8.4e+13(年)41.4计算复杂性的概念1.4.2多项式时间算法构造算法的目的是能够解决问题（或至少是问题某个子类）的所有
5、实例而不单单是某一个实例问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件.问题中的参数赋予了具体值的例子称为实例(instance).衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量.计算模型C(I)=f(d(I)):该函数关系称为算法的计算复杂性（度）51.4计算复杂性的概念1.4.2多项式
6、时间算法对于一个正整数x，二进制表示是以如ATSP:二进制输入长度总量不超过(不考虑正负号、分隔符等)的系数来表示，其中，x的二进制数的位数不超过假设每一个数据(距离)的绝对值都有上界K输入长度是n的多项式函数所以网络优化中常用n,m等表示输入规模61.4计算复杂性的概念1.4.2多项式时间算法例构造算法将n个自然数从小到大排列起来算法输入自然数a(1),a(2),…,a(n).for(i=1;ia(j)){k=a(i);a(i)=a(j);a(j)=k;
7、}即该算法的计算复杂性（度）为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)/271.4计算复杂性的概念定义1.4假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间成立，则称该算法为解决该问题的多项式(时间)算法(Polynomialtimealgorithm).当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或
8、指数(时间)算法(Exponentialtimealgorithm)输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.1.4.2多项式时间算法注：上面定义中，要求对该问题的任意一个实例均成立，这种分析方法称为最坏性能分析（Worst-CaseAnalysis）81.4计算复杂性的概念1.4.2多项式时间算法近似值计算机提速10倍n10100100010121013nlogn3366499660.9e110.87e12n21001041061063.16e6n310001061091042.15e4108n4
9、10121016102010182n10241.27e301.05e301404310n1010101001010001213nlogn20791.93e137.89e297995n!3628800101584e2567141591.4计算复杂性的概念1.4.2多项式时间算法算法复杂性研究中:常将算法的
