算法复杂性精选PPT.ppt

《算法复杂性精选PPT.ppt》由会员分享，可在线阅读，更多相关《算法复杂性精选PPT.ppt（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于算法复杂性关于算法复杂性第1页，讲稿共75张，创作于星期二 旅行商旅行商(TSP)问题问题一个商人欲到一个商人欲到n个城市推销商品，每两个城市个城市推销商品，每两个城市i和和j之间的距离为之间的距离为dij，如何选，如何选择一条道路，使得商人每个城市走过一遍后回到起点且所走路径最短。择一条道路，使得商人每个城市走过一遍后回到起点且所走路径最短。解：设解：设xij=1若商人行走的路线中包含从城市若商人行走的路线中包含从城市i到到j的路径，否则的路径，否则xij=0。第2页，讲稿共75张，创作于星期二可行解：用可行解：用n个城市的一个排列表示商人按个城市的一个排列表示商人按这个排列序推销并返回

2、起点。这个排列序推销并返回起点。使用枚举法求解，需要使用枚举法求解，需要(n-1)!次枚举。次枚举。以计算机以计算机1秒可以完成秒可以完成24个城市所有路径枚个城市所有路径枚举为单位。举为单位。城市数城市数 24 25 26 27 30计算时间计算时间 1秒秒 24秒秒 10分分 4.3小时小时 10.8年年第3页，讲稿共75张，创作于星期二1.问题与实例问题与实例问题问题(problem):需要回答的一种提问，通需要回答的一种提问，通常包含一些参数和取值未定的自由变量，可常包含一些参数和取值未定的自由变量，可以从两个方面加以描述：以从两个方面加以描述：（1）对所有参数的一般描述；）对所有参数

3、的一般描述；（2）对回答（也称为）对回答（也称为解解）所需要满足的特）所需要满足的特性的描述。性的描述。实例实例(instance)：当对一个问题中的参数：当对一个问题中的参数赋予特定的数值时，如何寻找相应的回答赋予特定的数值时，如何寻找相应的回答（解），这种提问称为该问题的一个实例。（解），这种提问称为该问题的一个实例。问题是对许多具体事例构成集合的一种抽象问题是对许多具体事例构成集合的一种抽象表述，而实例就是相应问题的一种具体表现表述，而实例就是相应问题的一种具体表现形式。形式。第4页，讲稿共75张，创作于星期二例：线性规划问题与实例例：线性规划问题与实例一个线性规划问题的实例是指矩阵和向

4、量一个线性规划问题的实例是指矩阵和向量组组(A,b,c)的某一特定取值，这些参数按照的某一特定取值，这些参数按照如下的结构关联在一起，描述了问题（解）如下的结构关联在一起，描述了问题（解）所需要满足的特性。所需要满足的特性。线性规划问题是对具有上述结构的所有实例线性规划问题是对具有上述结构的所有实例的一种抽象描述。的一种抽象描述。第5页，讲稿共75张，创作于星期二算法算法算法算法：是一组含义明确的简单指令。：是一组含义明确的简单指令。一个问题是算法可解的一个问题是算法可解的(solvable)：存在一个求解该问：存在一个求解该问题的算法，只要让算法运行足够长的时间，并且保证满足题的算法，只要让

5、算法运行足够长的时间，并且保证满足算法在运行过程中所需要的存储空间，它就能求解该问题算法在运行过程中所需要的存储空间，它就能求解该问题的任何一个实例。的任何一个实例。停机问题停机问题：不可能构造出一个程序来确定任意给出的程：不可能构造出一个程序来确定任意给出的程序是否会陷入无限循环。序是否会陷入无限循环。第6页，讲稿共75张，创作于星期二算法复杂性算法复杂性算法复杂性算法复杂性(algorithm complexity):描述算法的存储要求和运行时间要求，分描述算法的存储要求和运行时间要求，分为算法的空间复杂性和算法的时间复杂性。为算法的空间复杂性和算法的时间复杂性。-利用算法需要的初等运算次

6、数来表示算利用算法需要的初等运算次数来表示算法的时间复杂性。法的时间复杂性。第7页，讲稿共75张，创作于星期二多项式时间算法与指数时间算法多项式时间算法与指数时间算法输入规模输入规模(input size)：表示一个：表示一个实例实例所所需要的字符串长度。需要的字符串长度。一般的，使用一般的，使用 位二进制就可以位二进制就可以表示任意整数表示任意整数r。线性规划的输入规模为：线性规划的输入规模为：第8页，讲稿共75张，创作于星期二对应对应TSP，枚举算法的基本计算总次数为，枚举算法的基本计算总次数为(n-1)!n=n!实例的二进制输入长度总量不超过实例的二进制输入长度总量不超过 L=n(n-1

7、)+log2|P|其中其中P为所有非零数为所有非零数dij的乘积。的乘积。假设假设 中每个数据都有上中每个数据都有上界界K，则有，则有第9页，讲稿共75张，创作于星期二一个求解实例一个求解实例I的算法的基本计算总次数的算法的基本计算总次数C(I)同实例同实例I的计算机二进制输入长度的计算机二进制输入长度d(I)的关系的关系常用符号常用符号C(I)=f(d(I)=O(g(d(I)表示，它的表示，它的含义：求解实例含义：求解实例I的算法的基本计算总次数的算法的基本计算总次数C(I)是实例是实例输入长度输入长度d(I)的一个函数，该函的一个函数，该函数被另一个函数数被另一个函数g(x)控制，即存在一

8、个函数控制，即存在一个函数g(x)和一个常数和一个常数a，使得，使得第10页，讲稿共75张，创作于星期二多项式时间算法与指数时间算法多项式时间算法与指数时间算法定义：假设问题和解决该问题的一个算法已经定义：假设问题和解决该问题的一个算法已经给定，若给定该问题的一个实例给定，若给定该问题的一个实例I，存在多项式，存在多项式函数函数g(x)，使得，使得成立，则称该算法对成立，则称该算法对实例实例I是多项式时间算法；是多项式时间算法；若若存在存在g(x)为为多项式函数且对该问题任意一个实多项式函数且对该问题任意一个实例例I，都有上式成立，则称，都有上式成立，则称该算法为解决该问题该算法为解决该问题的

9、的多项式时间算法多项式时间算法。当当g(x)为为指数函数时，称相应的算法为指数函数时，称相应的算法为指数时间指数时间算法算法。第11页，讲稿共75张，创作于星期二Growth Rate:Sketch10nn22nn!=2O(n lg n)input lengthtime第12页，讲稿共75张，创作于星期二多项式时间算法的优点：多项式时间算法的优点：（1）随着问题输入规模的增加，算法的计）随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长；算量（即算法复杂性）呈多项式增长；（2）一个多项式时间算法利用另一个多项）一个多项式时间算法利用另一个多项式时间算法作为其式时间算法作为其“子程

10、序子程序”，构造一个，构造一个新的复合型算法，则新算法仍是多项式时新的复合型算法，则新算法仍是多项式时间算法。间算法。第13页，讲稿共75张，创作于星期二单纯形算法的复杂性单纯形算法的复杂性单纯形算法需要单纯形算法需要2n-1次迭代。次迭代。第14页，讲稿共75张，创作于星期二定理：当定理：当2时，用单纯形算法求解上述问题时需要时，用单纯形算法求解上述问题时需要2n-1次迭代。次迭代。第15页，讲稿共75张，创作于星期二 椭球法椭球法 第一个可以在多項式时间內解决一般线性规划问题的解法。第一个可以在多項式时间內解决一般线性规划问题的解法。根据根据(P)与与(D)的对偶关系的对偶关系,我们可将两

11、者的最优解以一组我们可将两者的最优解以一组最优性条件联结起来最优性条件联结起来:第16页，讲稿共75张，创作于星期二第17页，讲稿共75张，创作于星期二第18页，讲稿共75张，创作于星期二 只要能有效的解决最优性条件的线性不等式只要能有效的解决最优性条件的线性不等式,就能就能夠同时的解决一个线性规划问题夠同时的解决一个线性规划问题(P)以及它的对偶问题以及它的对偶问题(D)。椭球法正是一种专门解决线性不等式的方法。椭球法正是一种专门解决线性不等式的方法。介绍如何以椭球法來解一组线性不等式介绍如何以椭球法來解一组线性不等式MuvMuv的解集合是一个凸集：的解集合是一个凸集：假设假设S,以原点以原

12、点u1为圆心为圆心,足夠大的半径做一圆足夠大的半径做一圆E1,使得使得SE1。第19页，讲稿共75张，创作于星期二 否则否则,因为因为SE1是一个凸集是一个凸集,所以经过圆心所以经过圆心,可以切可以切掉不含掉不含SE1 的半个圆的半个圆,而只剩下包含而只剩下包含SE1的半个圆的半个圆(以以1/2E1表示表示)。对。对1/2E1而言而言,可以做出一个最小的椭可以做出一个最小的椭圆圆E2,使得使得1/2E1 E2，椭圆的圆心记，椭圆的圆心记u2。SE1E2,若若Mu2 v成立成立,则则u2SE1必为其解。必为其解。否则经过否则经过u2又可切去半个又可切去半个E2,而使而使SE1包含在另一包含在另一

13、半椭圆半椭圆1/2E2之中。之中。第20页，讲稿共75张，创作于星期二第21页，讲稿共75张，创作于星期二 在在p维空间中维空间中,每次做出的椭球体积都会逐渐缩小。以每次做出的椭球体积都会逐渐缩小。以V(Ek)及及V(Ek+1)来来表示前后两个椭球的体积表示前后两个椭球的体积,那么可以证那么可以证明明V(Ek+1)e1/2(p+1)V(Ek)。所以。所以 V(Ek+1)0。可行內点解集合可行內点解集合：F0=xRn|Ax=b,x 0。假设假设F0非空。非空。第25页，讲稿共75张，创作于星期二內点法可粗略的分为三个步骤內点法可粗略的分为三个步骤:步骤一步骤一:找一个可行內点找一个可行內点x1F

14、0。置。置k=1。步骤二步骤二:决定现有解决定现有解xk是否为是否为(P)的最优解。若是的最优解。若是,则则输出输出x =xk。否则就寻找一个好的移动方向。否则就寻找一个好的移动方向 ,以及适当以及适当的步长的步长 0。第26页，讲稿共75张，创作于星期二Primal Affine Scaling内点法内点法 假想假想(P)的可行解集合位于第一象限的一个球的可行解集合位于第一象限的一个球,而现行而现行解解xk落在球心上落在球心上,此球的半径是此球的半径是r 0。最优解为：最优解为：第27页，讲稿共75张，创作于星期二 将将(P1)变得稍微复杂一些变得稍微复杂一些,将球改为第一象限来考将球改为第

15、一象限来考虑下列问题虑下列问题:第28页，讲稿共75张，创作于星期二定义映射：定义映射：第29页，讲稿共75张，创作于星期二第30页，讲稿共75张，创作于星期二 在上述转化之下在上述转化之下,(P2)的近似问题在的近似问题在y空间中就可写成空间中就可写成:应用应用(P1)的解答技巧的解答技巧,在在y空间中的近似最优解为：空间中的近似最优解为：在在x空间中空间中(P2)的近似最优解为：的近似最优解为：第31页，讲稿共75张，创作于星期二在在y空間中空間中(P)变成下列的近似问题变成下列的近似问题:第32页，讲稿共75张，创作于星期二 与与(P2)相比较相比较,(P)多了一些等式约束条件多了一些等

16、式约束条件ADky=b。为了保持这些等式的继续成立。为了保持这些等式的继续成立,原来在原来在(P2)中的移动方向中的移动方向Dkc便需要投影在便需要投影在(ADk)这个矩阵这个矩阵的零的零空间空间(null space)之中，即经过投影后的方向应是之中，即经过投影后的方向应是Pk(Dkc)，其中其中Pk是一个投影矩阵，定义为：是一个投影矩阵，定义为：所以所以(P)的近似最优解是的近似最优解是(P)的近似最优解是的近似最优解是第33页，讲稿共75张，创作于星期二Primal Affine Scaling內点法的重要步骤內点法的重要步骤:第34页，讲稿共75张，创作于星期二Karmarkar投影尺

17、度算法投影尺度算法两个基本事实：两个基本事实：（1）如果一个内点居于多面体的中心，那）如果一个内点居于多面体的中心，那么目标函数的负梯度方向是比较好的可行么目标函数的负梯度方向是比较好的可行方向；方向；（2）在不改变问题基本特性的条件下，存）在不改变问题基本特性的条件下，存在一个适当的变换，能够将可行域中给定在一个适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。的内点置于变换后的可行域的中心。第35页，讲稿共75张，创作于星期二基本思想：基本思想：（1）选定一个内点解作为迭代过程的初始点，利用）选定一个内点解作为迭代过程的初始点，利用可行域的投影尺度变换，将当前的内点解置于变换后

18、可行域的投影尺度变换，将当前的内点解置于变换后的可行域的中心；的可行域的中心；（2）在变换后的可行域中沿着目标函数最速下降方向）在变换后的可行域中沿着目标函数最速下降方向的正交投影移动，获得新的可行内点，并通过投影尺度的正交投影移动，获得新的可行内点，并通过投影尺度逆变换将新的可行内点映射到原来的可行域，作为新的逆变换将新的可行内点映射到原来的可行域，作为新的迭代点。迭代点。（3）重复这一过程，直至求出满足一定精度的近优解。）重复这一过程，直至求出满足一定精度的近优解。X空间空间Y空间空间投影尺度变换第36页，讲稿共75张，创作于星期二Karmarkar标准形标准形基本假设：基本假设：第37页

19、，讲稿共75张，创作于星期二单纯形单纯形第38页，讲稿共75张，创作于星期二向量的投影向量的投影正交投影矩阵第39页，讲稿共75张，创作于星期二单纯形单纯形S的投影尺度变换的投影尺度变换第40页，讲稿共75张，创作于星期二变换变换T的性质的性质第41页，讲稿共75张，创作于星期二势函数势函数性质：性质：射影变换射影变换T把势函数变换成具有相同形式的函数把势函数变换成具有相同形式的函数目标函数值所期望的下降量可通过势函数值的充目标函数值所期望的下降量可通过势函数值的充分小来达到分小来达到优化函数优化函数f(x)可用优化线性函数来近似可用优化线性函数来近似第42页，讲稿共75张，创作于星期二第43

20、页，讲稿共75张，创作于星期二求解方法求解方法第44页，讲稿共75张，创作于星期二第45页，讲稿共75张，创作于星期二第46页，讲稿共75张，创作于星期二第47页，讲稿共75张，创作于星期二第48页，讲稿共75张，创作于星期二Karmarkar投影尺度算法投影尺度算法第49页，讲稿共75张，创作于星期二第50页，讲稿共75张，创作于星期二有关定理有关定理第51页，讲稿共75张，创作于星期二第52页，讲稿共75张，创作于星期二一般线性规划问题的处理一般线性规划问题的处理1利用对偶定理转化线性规划问题利用对偶定理转化线性规划问题第53页，讲稿共75张，创作于星期二(P)存在最优解的充要条件是存在最

21、优解的充要条件是第54页，讲稿共75张，创作于星期二记记于是问题归结为求解：于是问题归结为求解：第55页，讲稿共75张，创作于星期二记记第56页，讲稿共75张，创作于星期二两个特性：两个特性：第57页，讲稿共75张，创作于星期二进行如下投影变换：进行如下投影变换：第58页，讲稿共75张，创作于星期二两个特性：两个特性：第59页，讲稿共75张，创作于星期二用用Karmarkar投影尺度算法求解如下线性规划：投影尺度算法求解如下线性规划：引入松弛变量，化为标准型引入松弛变量，化为标准型第60页，讲稿共75张，创作于星期二化为化为Karmarkar标准型标准型第61页，讲稿共75张，创作于星期二第6

22、2页，讲稿共75张，创作于星期二路径跟踪法路径跟踪法第63页，讲稿共75张，创作于星期二Karush-Kuhn-Tucker条件松弛KKT条件第64页，讲稿共75张，创作于星期二第65页，讲稿共75张，创作于星期二第66页，讲稿共75张，创作于星期二定义原始定义原始-对偶可行集对偶可行集原始原始-对偶中心路径对偶中心路径第67页，讲稿共75张，创作于星期二第68页，讲稿共75张，创作于星期二第69页，讲稿共75张，创作于星期二移动方向的计算移动方向的计算第70页，讲稿共75张，创作于星期二第71页，讲稿共75张，创作于星期二步长的确定步长的确定第72页，讲稿共75张，创作于星期二计算步骤：计算步骤：第73页，讲稿共75张，创作于星期二第74页，讲稿共75张，创作于星期二感感谢谢大大家家观观看看第75页，讲稿共75张，创作于星期二