《计算复杂性的概念ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算复杂性的概念ppt课件.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 1网网 络络 优优 化化 第第 1 1 章章 概概 论论 Network Optimization1.4 1.4 计算复杂性的概念计算复杂性的概念 2定定义义1.3 1.3 所所谓谓组组合合(最最)优优化化(Combinatorial(Combinatorial Optimization)Optimization)又又称称离离散散优优化化（Discrete Discrete OptimizationOptimization），它它是是通通过过数数学学方方法法去去寻寻找找离离散散事事件件的的最最优优编排、分组、次序或筛选等编排、分组、次序或筛选等.这类问题可用数学模型描述为：这类问题可用数学
2、模型描述为：优化问题三要素优化问题三要素:(Min,f,F)或或(Max,f,F)其其中中D表表示示有有限限个个点点组组成成的的集集合合(定定义义域域),f为为目目标标函函数数,F=x|x D,g(x)0为可行域为可行域 1.4.1 1.4.1 组合优化问题组合优化问题1 1、定义、定义3给给定定n个个容容积积分分别别为为ai，价价值值分分别别为为ci的的物物品品.设设有有一一个个容容积积为为b的的背背包包，如如何何以最大的价值装包？用数学规划模型表示为：以最大的价值装包？用数学规划模型表示为：D=0,1n 2 2、例子、例子例例1.7 0-1背包问题背包问题(knapsack problem
3、)4一一个个商商人人到到n城城市市推推销销商商品品，两两个个城城市市之之间间的的距距离离为为dij，如如何何选选择择一一条条道道路路使使得得商商人人每每个个城城市市走走一一遍遍之之后后回回到到起起点点，且且所所走走的路径最短？其数学模型描述为：的路径最短？其数学模型描述为：例例1.8 旅行商问题旅行商问题(TSP)D=0,1n(n-1)5例例1.9 1.9 整数线性规划整数线性规划(Integer Linear Programming)(Integer Linear Programming)(ILP)(ILP).我我们们假假设设线线性性整整数数规规划划的的参参数数（约约束束矩矩阵阵和和右右端端
4、项项系系数数）都是整数都是整数(或有理数或有理数).ILPILP中系数是有理数时，都可以处理成整数的情况。中系数是有理数时，都可以处理成整数的情况。6以以尺尺寸寸为为1的的箱箱子子装装进进给给定定的的n个个尺尺寸寸不不超超过过1的的物物品品，物物品的尺寸为品的尺寸为wj，如何使所用的箱子个数最少，如何使所用的箱子个数最少?说说明明：许许多多组组合合优优化化问问题题可可以以用用整整数数规规划划模模型型表表示示,但但有有时时不不如如直直接接用用自自然然语语言言描描述述简简洁洁，故故，大大量量的的组组合合优优化化问问题题是通过文字语言叙述的。是通过文字语言叙述的。例例1.10 装箱问题装箱问题(Bi
5、n Packing)71.4.2 1.4.2 多项式时间算法多项式时间算法 对对于于组组合合优优化化问问题题，我我们们关关心心的的一一般般不不是是最最优优解解的的存存在在性性和和唯唯一一性性，而而是是如如何何找找到到有有效效的的算算法法求求得得一一个个最最优优解解.那那么么如如何何衡衡量量算算法法的的优优劣劣、有效与无效呢？有效与无效呢？完全枚举法可以求得最优解完全枚举法可以求得最优解,但但枚举时间有时不可能接受枚举时间有时不可能接受 ATSP:(ATSP:(n-1)!-1)!枚举枚举(TOUR,(TOUR,周游或环游周游或环游)设计算机每秒进行设计算机每秒进行100100亿次枚举亿次枚举,需
6、需30!/10e+10 2.65e+22(30!/10e+10 2.65e+22(秒秒)即即 2.65e+22/(365*24*60*60)2.65e+22/(365*24*60*60)8.4e+13(8.4e+13(年年)8问题（问题（Problem）：）：是需要回答的一般性提问，通常含有若干是需要回答的一般性提问，通常含有若干个满足一定条件的参数个满足一定条件的参数.实例实例(instance)：问题中的参数赋予了具体值的例子。问题中的参数赋予了具体值的例子。一、问题与实例的定义：一、问题与实例的定义：问题通过下面的描述给定：（问题通过下面的描述给定：（1）描述所有参数的特性）描述所有参数
7、的特性 （2）描述答案所满足的条件）描述答案所满足的条件.问题问题实例实例TSP 问题中各参数问题中各参数:100个城市，城市间距离个城市，城市间距离 已知已知.背包问题背包问题问题中各参数问题中各参数:4个物品，大小分别为个物品，大小分别为4,3,2,2.价价值分别为值分别为8,7,5,7.包的大小为包的大小为6.整数线性规划整数线性规划问题中的问题中的n,A,b,c已知已知.9构构造造算算法法的的目目的的是是能能够够解解决决问问题题（或或至至少少是是问问题题某某个个子子类类）的的所有实例而不单单是某一个实例。所有实例而不单单是某一个实例。衡量一个算法的好坏，通常由以下两个要素的关系来衡量：
8、衡量一个算法的好坏，通常由以下两个要素的关系来衡量：(1)C(I)：求求解解实实例例I的的计计算算时时间间，即即算算法法中中的的加加、减减、乘乘、除和比较等基本运算的总次；除和比较等基本运算的总次；(2)d(I)：实实例例I的的输输入入规规模模/长长度度，即即实实例例I在在计计算算机机计计算算时时的的二进制输入数据的大小二进制输入数据的大小.输入长度输入长度/规模的计算方法：规模的计算方法：对于一个正整数对于一个正整数x，其二进制为：，其二进制为：二、多项式时间算法二、多项式时间算法10正整数正整数 x 输入长度的估计输入长度的估计：11定定义义1.4 假假设设问问题题和和解解决决该该问问题题
9、的的一一个个算算法法已已经经给给定定，若若存存在在g(x)为多项式函数且对该问题为多项式函数且对该问题任意的一个实例任意的一个实例I，使得计算时间，使得计算时间成成立立，则则称称该该算算法法为为解解决决该该问问题题的的多多项项式式(时时间间)算算法法(Polynomial time algorithm).输入规模增大时，多项式时间算法的基本计算总次数的增输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢。加速度相对较慢。当当不不存存在在多多项项式式函函数数g(x)使使得得上上式式成成立立时时，称称相相应应的的算算法法是是非非多多 项项 式式 时时 间间 算算 法法,或或 指指 数
10、数(时时 间间)算算 法法(Exponential time algorithm)12例例1 1：上述的非对称上述的非对称ATSPATSP问题，设城市数为问题，设城市数为n，第，第1 1个个城市为始终点。城市为始终点。假设每一个数据假设每一个数据(距离距离)的绝对值都有上界的绝对值都有上界K，则：，则：说明：输入长度不超过说明：输入长度不超过n的一个多项式函数。的一个多项式函数。13所以，枚举算法对所以，枚举算法对TSPTSP来说，不是一个多项式时间的算法。来说，不是一个多项式时间的算法。TSPTSP问题至今没有找到多项式时间算法问题至今没有找到多项式时间算法,但尚未证明其不存在但尚未证明其不
11、存在TSP是否存在是否存在多项式时间算法多项式时间算法?-?-这是这是2121世纪数学和计算机科学的挑战性问题之一世纪数学和计算机科学的挑战性问题之一14例例2 2：构造构造算法算法将将n个自然数从小到大排列起来个自然数从小到大排列起来 算法算法 输入输入自然数自然数a(1),a(2),a(1),a(2),a(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;即该算法的计算复杂性（度）为即该
12、算法的计算复杂性（度）为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赋值：赋值：3(n-1)+(n-2)+3(n-1)+(n-2)+1=3n(n-1)/2+1=3n(n-1)/215三、强多项式算法和伪多项式算法三、强多项式算法和伪多项式算法 算法复杂性研究中算法复杂性研究中:常将算法的计算时间表示为：常将算法的计算时间表示为：问题中的简单而典型的参数问题中的简单而典型的参数(如网络优化中如网络优化
13、中n,m)问问题题中中出出现现的的数数值值(如如弧弧上上的的权权)的的最最大大值值(按按绝绝对对值值)K等自变量的函数关系等自变量的函数关系如如果果算算法法运运行行时时间间的的上上界界是是m,n和和K的的多多项项式式函函数数，则则称称相相应应的的算算法法为为伪伪多项式（多项式（PseudopolynomialPseudopolynomial）（时间）算法）（时间）算法，或，或拟多项式（时间）算法拟多项式（时间）算法.实际问题的输入规模实际问题的输入规模/长度一定是长度一定是m,n和和logK的一个多项式函数的一个多项式函数.所以：所以：多项式算法等价于其运行时间的上界是多项式算法等价于其运行时
14、间的上界是m,n和和logK的多项式函数的多项式函数.特特别别地地,如如果果运运行行时时间间的的上上界界是是m,n的的多多项项式式函函数数（即即该该多多项项式式函函数数不不包包含含loglogK）,则称相应的算法为则称相应的算法为强多项式强多项式(Strongly Polynomial)(Strongly Polynomial)时间算法时间算法.一般来说，伪多项式算法并不是多项式算法一般来说，伪多项式算法并不是多项式算法.16定义定义1.5 对于给定的一个优化问题，若对于给定的一个优化问题，若存在存在一个求解该问题一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称解问题，或简称多项式问题多项式问题，所有多项式问题集记为，所有多项式问题集记为P(Polynomial).同样道理,可以定义强多项式问题,伪多项式问题等.1.4.3 多项式问题多项式问题17布 置 作 业目的掌握图与网络的基本概念掌握算法复杂性的基本概念内容网络优化网络优化第第18页页 5;7(星形表示法星形表示法);9;11;