算法复杂性课件.ppt

《算法复杂性课件.ppt》由会员分享，可在线阅读，更多相关《算法复杂性课件.ppt（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、点。使用枚举法求解，需要使用枚举法求解，需要(n-1)!次枚举。次枚举。以计算机以计算机1秒可以完成秒可以完成24个城市所有路径枚个城市所有路径枚举为单位。举为单位。城市数城市数 24 25 26 27 30计算时间计算时间 1秒秒 24秒秒 10分分 4.3小时小时 10.8年年第3页，此课件共72页哦1.问题与实例问题与实例问题问题(problem):需要回答的一种提问，通需要回答的一种提问，通常包含一些参数和取值未定的自由变量，可常包含一些参数和取值未定的自由变量，可以从两个方面加以描述：以从两个方面加以描述：（1）对所有参数的一般描述；）对所有参数的一般描述；（2）对回答（也称为）对回

3、答（也称为解解）所需要满足的特）所需要满足的特性的描述。性的描述。实例实例(instance)：当对一个问题中的参数：当对一个问题中的参数赋予特定的数值时，如何寻找相应的回答赋予特定的数值时，如何寻找相应的回答（解），这种提问称为该问题的一个实例。（解），这种提问称为该问题的一个实例。问题是对许多具体事例构成集合的一种抽象问题是对许多具体事例构成集合的一种抽象表述，而实例就是相应问题的一种具体表现表述，而实例就是相应问题的一种具体表现形式。形式。第4页，此课件共72页哦例：线性规划问题与实例例：线性规划问题与实例一个线性规划问题的实例是指矩阵和向量组一个线性规划问题的实例是指矩阵和向量组(A,

4、b,c)的某一特定取值，这些参数按照如的某一特定取值，这些参数按照如下的结构关联在一起，描述了问题（解）所下的结构关联在一起，描述了问题（解）所需要满足的特性。需要满足的特性。线性规划问题是对具有上述结构的所有实例线性规划问题是对具有上述结构的所有实例的一种抽象描述。的一种抽象描述。第5页，此课件共72页哦算法算法算法算法：是一组含义明确的简单指令。：是一组含义明确的简单指令。一个问题是算法可解的一个问题是算法可解的(solvable)：存在一个求解该：存在一个求解该问题的算法，只要让算法运行足够长的时间，并且保问题的算法，只要让算法运行足够长的时间，并且保证满足算法在运行过程中所需要的存储空

5、间，它就能证满足算法在运行过程中所需要的存储空间，它就能求解该问题的任何一个实例。求解该问题的任何一个实例。停机问题停机问题：不可能构造出一个程序来确定任意给出的程：不可能构造出一个程序来确定任意给出的程序是否会陷入无限循环。序是否会陷入无限循环。第6页，此课件共72页哦算法复杂性算法复杂性算法复杂性算法复杂性(algorithm complexity):描述算法的存储要求和运行时间要求，分为描述算法的存储要求和运行时间要求，分为算法的空间复杂性和算法的时间复杂性。算法的空间复杂性和算法的时间复杂性。-利用算法需要的初等运算次数来表示算利用算法需要的初等运算次数来表示算法的时间复杂性。法的时间

6、复杂性。第7页，此课件共72页哦多项式时间算法与指数时间算法多项式时间算法与指数时间算法输入规模输入规模(input size)：表示一个：表示一个实例实例所所需要的字符串长度。需要的字符串长度。一般的，使用一般的，使用 位二进制就可以位二进制就可以表示任意整数表示任意整数r。线性规划的输入规模为：线性规划的输入规模为：第8页，此课件共72页哦对应对应TSP，枚举算法的基本计算总次数为，枚举算法的基本计算总次数为(n-1)!n=n!实例的二进制输入长度总量不超过实例的二进制输入长度总量不超过 L=n(n-1)+log2|P|其中其中P为所有非零数为所有非零数dij的乘积。的乘积。假设假设 中每

7、个数据都有上中每个数据都有上界界K，则有，则有第9页，此课件共72页哦一个求解实例一个求解实例I的算法的基本计算总次数的算法的基本计算总次数C(I)同实例同实例I的计算机二进制输入长度的计算机二进制输入长度d(I)的关系的关系常用符号常用符号C(I)=f(d(I)=O(g(d(I)表示，它的表示，它的含义：求解实例含义：求解实例I的算法的基本计算总次数的算法的基本计算总次数C(I)是实例是实例输入长度输入长度d(I)的一个函数，该函的一个函数，该函数被另一个函数数被另一个函数g(x)控制，即存在一个函数控制，即存在一个函数g(x)和一个常数和一个常数a，使得，使得第10页，此课件共72页哦多项

8、式时间算法与指数时间算法多项式时间算法与指数时间算法定义：假设问题和解决该问题的一个算法已经定义：假设问题和解决该问题的一个算法已经给定，若给定该问题的一个实例给定，若给定该问题的一个实例I，存在多项式，存在多项式函数函数g(x)，使得，使得成立，则称该算法对成立，则称该算法对实例实例I是多项式时间算法；是多项式时间算法；若若存在存在g(x)为为多项式函数且对该问题任意一个实多项式函数且对该问题任意一个实例例I，都有上式成立，则称，都有上式成立，则称该算法为解决该问题该算法为解决该问题的的多项式时间算法多项式时间算法。当当g(x)为为指数函数时，称相应的算法为指数函数时，称相应的算法为指数时间

9、指数时间算法算法。第11页，此课件共72页哦Growth Rate:Sketch10nn22nn!=2O(n lg n)input lengthtime第12页，此课件共72页哦多项式时间算法的优点：多项式时间算法的优点：（1）随着问题输入规模的增加，算法的计）随着问题输入规模的增加，算法的计算量（即算法复杂性）呈多项式增长；算量（即算法复杂性）呈多项式增长；（2）一个多项式时间算法利用另一个多项）一个多项式时间算法利用另一个多项式时间算法作为其式时间算法作为其“子程序子程序”，构造一个新，构造一个新的复合型算法，则新算法仍是多项式时间算的复合型算法，则新算法仍是多项式时间算法。法。第13页，

10、此课件共72页哦单纯形算法的复杂性单纯形算法的复杂性单纯形算法需要单纯形算法需要2n-1次迭代。次迭代。第14页，此课件共72页哦定理：当定理：当2时，用单纯形算法求解上述问题时需要时，用单纯形算法求解上述问题时需要2n-1次迭代。次迭代。第15页，此课件共72页哦 椭球法椭球法 第一个可以在多項式时间內解决一般线性规划问题的第一个可以在多項式时间內解决一般线性规划问题的解法。解法。根据根据(P)与与(D)的对偶关系的对偶关系,我们可将两者的最优解以一组我们可将两者的最优解以一组最优性条件联结起来最优性条件联结起来:第16页，此课件共72页哦第17页，此课件共72页哦第18页，此课件共72页哦

11、 只要能有效的解决最优性条件的线性不等式只要能有效的解决最优性条件的线性不等式,就就能夠同时的解决一个线性规划问题能夠同时的解决一个线性规划问题(P)以及它的对偶以及它的对偶问题问题(D)。椭球法正是一种专门解决线性不等式的方法。椭球法正是一种专门解决线性不等式的方法。介绍如何以椭球法來解一组线性不等式介绍如何以椭球法來解一组线性不等式MuvMuv的解集合是一个凸集：的解集合是一个凸集：假设假设S,以原点以原点u1为圆心为圆心,足夠大的半径做一圆足夠大的半径做一圆E1,使得使得SE1。第19页，此课件共72页哦 否则否则,因为因为SE1是一个凸集是一个凸集,所以经过圆心所以经过圆心,可以可以切

12、掉不含切掉不含SE1 的半个圆的半个圆,而只剩下包含而只剩下包含SE1的半个的半个圆圆(以以1/2E1表示表示)。对。对1/2E1而言而言,可以做出一个最小的可以做出一个最小的椭圆椭圆E2,使得使得1/2E1 E2，椭圆的圆心记，椭圆的圆心记u2。SE1E2,若若Mu2 v成立成立,则则u2SE1必为其解。必为其解。否则经过否则经过u2又可切去半个又可切去半个E2,而使而使SE1包含在另一包含在另一半椭圆半椭圆1/2E2之中。之中。第20页，此课件共72页哦第21页，此课件共72页哦 在在p维空间中维空间中,每次做出的椭球体积都会逐渐缩小。每次做出的椭球体积都会逐渐缩小。以以V(Ek)及及V(

13、Ek+1)来来表示前后两个椭球的体积表示前后两个椭球的体积,那么可那么可以证明以证明V(Ek+1)e1/2(p+1)V(Ek)。所以。所以 V(Ek+1)0。可行內点解集合可行內点解集合：F0=xRn|Ax=b,x 0。假设假设F0非空。非空。第25页，此课件共72页哦內点法可粗略的分为三个步骤內点法可粗略的分为三个步骤:步骤一步骤一:找一个可行內点找一个可行內点x1F0。置。置k=1。步骤二步骤二:决定现有解决定现有解xk是否为是否为(P)的最优解。若是的最优解。若是,则则输出输出x =xk。否则就寻找一个好的移动方向。否则就寻找一个好的移动方向 ,以及以及适当的步长适当的步长 0。第26页

14、，此课件共72页哦Primal Affine Scaling内点法内点法 假想假想(P)的可行解集合位于第一象限的一个球的可行解集合位于第一象限的一个球,而现行而现行解解xk落在球心上落在球心上,此球的半径是此球的半径是r 0。最优解为：最优解为：第27页，此课件共72页哦 将将(P1)变得稍微复杂一些变得稍微复杂一些,将球改为第一象限来将球改为第一象限来考虑下列问题考虑下列问题:第28页，此课件共72页哦定义映射：定义映射：第29页，此课件共72页哦第30页，此课件共72页哦 在上述转化之下在上述转化之下,(P2)的近似问题在的近似问题在y空间中就可写成空间中就可写成:应用应用(P1)的解答

15、技巧的解答技巧,在在y空间中的近似最优解为：空间中的近似最优解为：在在x空间中空间中(P2)的近似最优解为：的近似最优解为：第31页，此课件共72页哦在在y空間中空間中(P)变成下列的近似问题变成下列的近似问题:第32页，此课件共72页哦 与与(P2)相比较相比较,(P)多了一些等式约束条件多了一些等式约束条件ADky=b。为了保持这些等式的继续成立。为了保持这些等式的继续成立,原来在原来在(P2)中的移中的移动方向动方向Dkc便需要投影在便需要投影在(ADk)这个矩阵这个矩阵的零空间的零空间(null space)之中，即经过投影后的方向应是之中，即经过投影后的方向应是Pk(Dkc)，其中其

16、中Pk是一个投影矩阵，定义为：是一个投影矩阵，定义为：所以所以(P)的近似最优解是的近似最优解是(P)的近似最优解是的近似最优解是第33页，此课件共72页哦Primal Affine Scaling內点法的重要步骤內点法的重要步骤:第34页，此课件共72页哦Karmarkar投影尺度算法投影尺度算法两个基本事实：两个基本事实：（1）如果一个内点居于多面体的中心，那）如果一个内点居于多面体的中心，那么目标函数的负梯度方向是比较好的可行方么目标函数的负梯度方向是比较好的可行方向；向；（2）在不改变问题基本特性的条件下，存）在不改变问题基本特性的条件下，存在一个适当的变换，能够将可行域中给定的在一个

17、适当的变换，能够将可行域中给定的内点置于变换后的可行域的中心。内点置于变换后的可行域的中心。第35页，此课件共72页哦基本思想：基本思想：（1）选定一个内点解作为迭代过程的初始点，利用可）选定一个内点解作为迭代过程的初始点，利用可行域的投影尺度变换，将当前的内点解置于变换后的可行域的投影尺度变换，将当前的内点解置于变换后的可行域的中心；行域的中心；（2）在变换后的可行域中沿着目标函数最速下降方向的）在变换后的可行域中沿着目标函数最速下降方向的正交投影移动，获得新的可行内点，并通过投影尺度逆变正交投影移动，获得新的可行内点，并通过投影尺度逆变换将新的可行内点映射到原来的可行域，作为新的迭代点。换

18、将新的可行内点映射到原来的可行域，作为新的迭代点。（3）重复这一过程，直至求出满足一定精度的近优）重复这一过程，直至求出满足一定精度的近优解。解。X空间空间Y空间空间投影尺度变换第36页，此课件共72页哦Karmarkar标准形标准形基本假设：基本假设：第37页，此课件共72页哦单纯形单纯形第38页，此课件共72页哦向量的投影向量的投影正交投影矩阵第39页，此课件共72页哦单纯形单纯形S的投影尺度变换的投影尺度变换第40页，此课件共72页哦变换变换T的性质的性质第41页，此课件共72页哦势函数势函数性质：性质：射影变换射影变换T把势函数变换成具有相同形式的函数把势函数变换成具有相同形式的函数目

19、标函数值所期望的下降量可通过势函数值的充目标函数值所期望的下降量可通过势函数值的充分小来达到分小来达到优化函数优化函数f(x)可用优化线性函数来近似可用优化线性函数来近似第42页，此课件共72页哦第43页，此课件共72页哦求解方法求解方法第44页，此课件共72页哦第45页，此课件共72页哦第46页，此课件共72页哦第47页，此课件共72页哦第48页，此课件共72页哦Karmarkar投影尺度算法投影尺度算法第49页，此课件共72页哦第50页，此课件共72页哦有关定理有关定理第51页，此课件共72页哦第52页，此课件共72页哦一般线性规划问题的处理一般线性规划问题的处理1利用对偶定理转化线性规划

20、问题利用对偶定理转化线性规划问题第53页，此课件共72页哦(P)存在最优解的充要条件是存在最优解的充要条件是第54页，此课件共72页哦记记于是问题归结为求解：于是问题归结为求解：第55页，此课件共72页哦记记第56页，此课件共72页哦两个特性：两个特性：第57页，此课件共72页哦进行如下投影变换：进行如下投影变换：第58页，此课件共72页哦两个特性：两个特性：第59页，此课件共72页哦用用Karmarkar投影尺度算法求解如下线性规划：投影尺度算法求解如下线性规划：引入松弛变量，化为标准型引入松弛变量，化为标准型第60页，此课件共72页哦化为化为Karmarkar标准型标准型第61页，此课件共72页哦第62页，此课件共72页哦路径跟踪法路径跟踪法第63页，此课件共72页哦Karush-Kuhn-Tucker条件松弛KKT条件第64页，此课件共72页哦第65页，此课件共72页哦第66页，此课件共72页哦定义原始定义原始-对偶可行集对偶可行集原始原始-对偶中心路径对偶中心路径第67页，此课件共72页哦第68页，此课件共72页哦第69页，此课件共72页哦移动方向的计算移动方向的计算第70页，此课件共72页哦第71页，此课件共72页哦步长的确定步长的确定第72页，此课件共72页哦