算法复杂性精选课件.ppt

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

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

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

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

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

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

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

7、设 中每个数据都有上中每个数据都有上界界K，则有，则有第九页，本课件共有75页一个求解实例一个求解实例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，使得，使得第十页，本课件共有75

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

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

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

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

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

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

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

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

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

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

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

19、函数把势函数变换成具有相同形式的函数目标函数值所期望的下降量可通过势函数值的充目标函数值所期望的下降量可通过势函数值的充分小来达到分小来达到优化函数优化函数f(x)可用优化线性函数来近似可用优化线性函数来近似第四十二页，本课件共有75页第四十三页，本课件共有75页求解方法求解方法第四十四页，本课件共有75页第四十五页，本课件共有75页第四十六页，本课件共有75页第四十七页，本课件共有75页第四十八页，本课件共有75页Karmarkar投影尺度算法投影尺度算法第四十九页，本课件共有75页第五十页，本课件共有75页有关定理有关定理第五十一页，本课件共有75页第五十二页，本课件共有75页一般线性规划

20、问题的处理一般线性规划问题的处理1利用对偶定理转化线性规划问题利用对偶定理转化线性规划问题第五十三页，本课件共有75页(P)存在最优解的充要条件是存在最优解的充要条件是第五十四页，本课件共有75页记记于是问题归结为求解：于是问题归结为求解：第五十五页，本课件共有75页记记第五十六页，本课件共有75页两个特性：两个特性：第五十七页，本课件共有75页进行如下投影变换：进行如下投影变换：第五十八页，本课件共有75页两个特性：两个特性：第五十九页，本课件共有75页用用Karmarkar投影尺度算法求解如下线性规划：投影尺度算法求解如下线性规划：引入松弛变量，化为标准型引入松弛变量，化为标准型第六十页，

21、本课件共有75页化为化为Karmarkar标准型标准型第六十一页，本课件共有75页第六十二页，本课件共有75页路径跟踪法路径跟踪法第六十三页，本课件共有75页Karush-Kuhn-Tucker条件松弛KKT条件第六十四页，本课件共有75页第六十五页，本课件共有75页第六十六页，本课件共有75页定义原始定义原始-对偶可行集对偶可行集原始原始-对偶中心路径对偶中心路径第六十七页，本课件共有75页第六十八页，本课件共有75页第六十九页，本课件共有75页移动方向的计算移动方向的计算第七十页，本课件共有75页第七十一页，本课件共有75页步长的确定步长的确定第七十二页，本课件共有75页计算步骤：计算步骤：第七十三页，本课件共有75页第七十四页，本课件共有75页感谢大家观看第七十五页，本课件共有75页