计算复杂性的概念.ppt
《计算复杂性的概念.ppt》由会员分享,可在线阅读,更多相关《计算复杂性的概念.ppt(42页珍藏版)》请在三一办公上搜索。
1、1,1.4 计算复杂性的概念,定义1.3 所谓组合(最)优化(Combinatorial Optimization)又称离散优化(Discrete Optimization),它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为:,优化问题三要素:(Min,f,F)或(Max,f,F),其中D表示有限个点组成的集合(定义域),f为目标函数,F=x|xD,g(x)0为可行域,1.4.1 组合优化 定义,2,1.4 计算复杂性的概念,1.4.1 组合优化 例,例1.7 0-1背包问题(knapsack problem)给定n个容积分别为ai,价值分别为ci的物品
2、.设有一个容积为b的背包,如何以最大的价值装包?用数学规划模型表示为:,D=0,1n,例1.10 装箱问题(Bin Packing)以尺寸为1的箱子装进给定的n个尺寸不超过1的物品,如何使所用的箱子个数最少?,3,1.4 计算复杂性的概念,1.4.1 组合优化 例,例1.9 整数线性规划(Integer Linear Programming),(IP).,我们假设线性整数规划的参数(约束矩阵和右端项系数)都是整数(或有理数).许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁,4,1.4 计算复杂性的概念,1.4.2 多项式时间算法,对于组合优化问题,我们关心的一般不是最
3、优解的存在性和唯一性,而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢?,完全枚举法可以求得最优解,但枚举时间有时不可能接受,ATSP:(n-1)!枚举(TOUR,周游或环游)设计算机每秒进行100亿次枚举,需30!/10e+10 2.65e+22(秒)即 2.65e+22/(365*24*60*60)8.4e+13(年),5,1.4 计算复杂性的概念,1.4.2 多项式时间算法,构造算法的目的是能够解决问题(或至少是问题某个子类)的所有实例而不单单是某一个实例,问题(Problem)是需要回答的一般性提问,通常含有若干个满足一定条件的参数.问题通过下面的描述给定:(
4、1)描述所有参数的特性,(2)描述答案所满足的条件.,问题中的参数赋予了具体值的例子称为实例(instance).,衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数(计算时间)C(I)同实例I在计算机计算时的二进制输入数据(输入规模/长度d(I))的大小关系来度量.计算模型,C(I)=f(d(I):该函数关系称为算法的计算复杂性(度),6,1.4 计算复杂性的概念,1.4.2 多项式时间算法,对于一个正整数x,二进制表示是以,如ATSP:二进制输入长度总量不超过(不考虑正负号、分隔符等),的系数来表示,其中,,x的二进制数的位数不超过,假设每一个数据(距离)的绝对值都有
5、上界K,输入长度是n的多项式函数所以网络优化中常用n,m等表示输入规模,7,1.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;,即该算法的计算复杂性(度)为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)/2,8,1.4 计算复杂性的概念,定义1.4 假设问题和解决该问题的一个算法已经给定,若存在g(x)为多项式
6、函数且对该问题任意的一个实例I,使得计算时间,成立,则称该算法为解决该问题的多项式(时间)算法(Polynomial time algorithm).当不存在多项式函数g(x)使得上式成立时,称相应的算法是非多项式时间算法,或指数(时间)算法(Exponential time algorithm),输入规模增大时,多项式时间算法的基本计算总次数的增加速度相对较慢.,1.4.2 多项式时间算法,注:上面定义中,要求对该问题的任意一个实例均成立,这种分析方法称为最坏性能分析(Worst-Case Analysis),9,1.4 计算复杂性的概念,1.4.2 多项式时间算法,10,1.4 计算复杂性
7、的概念,1.4.2 多项式时间算法,算法复杂性研究中:常将算法的计算时间表示为:问题中的简单而典型的参数(如网络优化中n,m),以及 问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系,如果算法运行时间的上界是m,n和K的多项式函数,则称相应的算法为伪多项式(Pseudopolynomial)(时间)算法,或拟多项式(时间)算法.,实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以:多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.,特别地,如果运行时间的上界是m,n的多项式函数(即该多项式函数不包含logK),则称相应的算法为强多项式(St
8、rongly Polynomial)时间算法.,一般来说,伪多项式算法并不是多项式算法.,11,1.4 计算复杂性的概念,TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存在,定义1.5 对于给定的一个优化问题,若存在一个求解该问题最优解的多项式时间算法,则称给定的优化问题是多项式可解问题,或简称多项式问题,所有多项式问题集记为P(Polynomial).,同样道理,可以定义强多项式问题,伪多项式问题等.,TSP是否存在多项式时间算法?-这是21世纪数学和计算机科学的挑战性问题之一,1.4.3 多项式问题,12,网 络 优 化,第 1 章 概 论(第2讲),Network Optim
9、ization,清华大学数学科学系 谢金星办公室:理科楼2206#(电话:)http:/,1.5 NP,NPC和NP-hard概念(计算复杂性理论),13,运筹学的ABC-A2B2C2(至少是组合优化、理论计算机科学的ABC),Approximation Algorithm(近似算法);Heuristic Branch and Bound(分枝定界)Computational Complexity(计算复杂性),口莫开,开口常说错。理论在监督,众目睽睽难逃脱。,计算复杂性理论的“Bible”Garey M R.and Johnson.D S,Computers and intractabili
10、ty:a guide to the theory of NP-completeness.San Francisco:.W.H.Freeman and Co.,1979(中译本:计算机和难解性:NP-C理论导论.张立昂等译,科学出版社,1987),14,1.5.1 问题、实例与输入规模,评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入规模的关系:,比多项式问题类可能更广泛的一个问题类是非确定多项式(Nondeterministic Polynomial,简记 NP)问题类,存在多项式算法的问题集合:多项式问题类(P),存在多项式函数 g(x)满足上式时,算法为多项式算法,NP 类是通过
11、判定问题引入的。,15,对任何一个优化问题,可以考虑其三种形式:最优化形式(原形:最优解)计值形式(最优值)判定形式(上界),定义1.6 如果一个问题的每一个实例只有“是”或“否”两种答案,则称这个问题为判定问题(Decision/recognition/feasibility problem).称有肯定答案的实例为“是”实例(yes-instance).称答案为“否”的实例为“否”实例或非“是”实例(no-instance).,1.5.2 判定问题-定义,例1.13 线性规划问题(LP)的判定形式LP判定问题:给定一个实数值z,(LP)是否有可行解使其目标值不超过z?即:给定z,是否有?,难
12、度降低,就有效算法的存在性而言,通常认为三种形式等价!,16,文字集,例1.15 适定性问题(Satisfiability problem)在逻辑运算中,布尔变量x的取值只有两个:“真”(1)和“假”(0),逻辑运算有“或(+)”,“与()”和“非().,1.5.2 判定问题-例,存在真值分配的表达式称为适定的(可满足的),文字集的任意一个子集中各元素(布尔变量)的“或”运算组成一个句子,多个句子的“与”运算组成一个表达式,如,适定性问题:给定布尔表达式,(SAT)是适定的吗?,17,1.5.2 判定问题-例,例1.16 三精确覆盖(3-Exact Covering:X3C)已知 的n个子集构
13、成的子集族,其中每个子集包含S中三个元素,F中是否存在m个子集,使得?若m个子集满足上式,则称这m个子集精确覆盖S.,18,定义1.7 若存在一个多项式函数g(x)和一个验证算法H,对一类判定问题A的任何一个“是”实例I,都存在一个字符串S是I的可行解,满足其输入长度d(S)不超过g(d(I),其中d(I)为I的输入长度,且算法H验证S为实例I的可行解的计算时间f(H)不超过g(d(I),则称判定问题A是非确定多项式的。,考虑将求解判定问题的算法分为两个阶段:(1)猜测阶段:求出或猜测该问题的一个解(2)检查或验证阶段:一旦解已经选定,将猜测的解作为输入,验证此解是否为该实例“是”的回答.我们
14、称实例“是”回答的解为实例的可行解,否则称为不可行解.,所有非确定多项式问题的集合用NP表示.,1.5.3 非确定多项式问题类(NP)定义,构造字符串(解)的过程及验证算法H一起构成一个算法,称为非确定多项式(时间)算法。,19,所以,可以从讨论基本可行解的性质入手,整系数问题等价于有理系数问题,1.5.3 非确定多项式问题类(NP)例,例1.17 整系数(或有理系数)的LP判定问题属于NP.,其实,LPP,所以LPNP.下面考虑通过定义来说明 LPNP,分析与思考:(注意:第1次印刷版教材上的证明可能有漏洞),(不)等式组有可行解,等价于它有基本可行解,LP判定问题等价于验证如下(不)等式组
15、的可行解问题 因此可以不考虑目标函数问题,仍记为,20,1.5.3 非确定多项式问题类(NP)例,引理1.1 LP问题的约束的基本可行解的各分量值有界,其二进制字符串表达式的输入长度不超过,例1.17 整系数(或有理系数)的LP判定问题属于NP.(续),输入长度不超过,又,分量值不超过,21,验证时最多需(m+1)n个乘,(m+1)(n-1)个加或减,n+m+1个比较,共计,LP实例的输入长度d(I)满足,1.5.3 非确定多项式问题类(NP)例,LP的一个基本可行解的输入长度不超过,例1.17 整系数(或有理系数)的LP判定问题属于NP.(续),对LP判定问题的一个“是”实例,上述约束组(等



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算复杂性 概念

链接地址:https://www.31ppt.com/p-6342174.html