算法和算法复杂性幻灯片.ppt

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

1、算法和算法复杂性第1页，共32页，编辑于2022年，星期一图图灵灵机机中中无无限限长长的的带带被被分分成成一一个个个个小小空空格格，每每格格容容纳纳一一个个符符号号，对对每每一一部部图图灵灵机机而而言言，带带上上允允许许使使用用的的符符号号是是有限的；有限的；图图灵灵机机的的输输入入是是由由符符号号组组成成的的有有限限序序列列，称称之之为为符号行，输入符号行不能含空格符符号行，输入符号行不能含空格符B。读读写写头头每每次次左左或或右右移移动动一一格格，并并根根据据控控制制器器的的指指令令阅阅读读方方格格中中的的符符号号或或抹抹去去、重重写写方方格格中中的的符符号号，其其初始位置是输入符号行最左

2、边符号。初始位置是输入符号行最左边符号。读写头读写头 带带（B B表示空格）表示空格）B 0 1 1 0 0 0 B控制器控制器 第2页，共32页，编辑于2022年，星期一控制器控制器有有限个状态，其中启始状态和终有有限个状态，其中启始状态和终止状态是两个特殊的状态；状态可依止状态是两个特殊的状态；状态可依转移函数转移函数进行，进行，（q，a）=（p，b，v）意为：读写头）意为：读写头看到符号看到符号a时，处于状态时，处于状态q的控制器命令其抹掉的控制器命令其抹掉a，重写，重写b，并向，并向v（左或右）移动一格，状态改变（左或右）移动一格，状态改变为为p；控制器开始处于启始状态，图灵机当且仅当

3、控控制器开始处于启始状态，图灵机当且仅当控制器处于终止状态时停止，此时制器处于终止状态时停止，此时带上符号行带上符号行为输出。为输出。第3页，共32页，编辑于2022年，星期一显然，图灵计算机计算的是显然，图灵计算机计算的是从符号行到符号行从符号行到符号行的函数的函数，但并不太限制其应用范围，但并不太限制其应用范围,它的它的计算时间计算时间是指是指读写头的移动次数读写头的移动次数,计算占用的空间计算占用的空间是指带上被访问过是指带上被访问过的方格数的方格数,当输入符号行是当输入符号行是x时时,图灵机图灵机M的计算时间的计算时间(或或占用空间占用空间)记为记为TimeM(x)(或或SpaceM(

4、x)。对意义明确的数学问题是否会不存在算法呢对意义明确的数学问题是否会不存在算法呢？图灵精彩地论证了图灵精彩地论证了这样的不可判定问题确实存这样的不可判定问题确实存在！在！第4页，共32页，编辑于2022年，星期一一一个个典典型型问问题题就就是是“停停停停机机机机问问问问题题题题”：给给定定一一个个带带有有输输入入的的计计算算机机程程序序，它它会会停停机机吗吗？图图灵灵证证明明了了，不不存存在在一一个个算算法法能能对对该该问问题题的的一一切切例例子子给给出出正正确的答案。确的答案。对于给定的问题，如果对于给定的问题，如果存在一种算法，可以对存在一种算法，可以对该问题的一切例子给出正确的答案，那

5、麽这个问题该问题的一切例子给出正确的答案，那麽这个问题就是就是可以计算可以计算的。的。可重复性可重复性归根于归根于因果关系的确定性因果关系的确定性因果关系的确定性因果关系的确定性，这种确定，这种确定性也是当今世界上存在的各式各样计算机的共同特性也是当今世界上存在的各式各样计算机的共同特点。点。第5页，共32页，编辑于2022年，星期一2 2、不确定型计算和算法复杂性、不确定型计算和算法复杂性（1 1）不确定型计算：）不确定型计算：一个不确定型图灵机一个不确定型图灵机一个不确定型图灵机一个不确定型图灵机M M计算一函数计算一函数计算一函数计算一函数f f f f（x x x x）时，）时，）时，

6、）时，必须假定必须假定必须假定必须假定M M M M满足以下条件：满足以下条件：满足以下条件：满足以下条件：若若f(x)f(x)无定义无定义,则对输入则对输入x,Mx,M的任何计算道路的任何计算道路都是都是(时间时间)无限长的无限长的;若若f(x)f(x)有定义有定义,则对输入则对输入x,Mx,M必有一有限长的必有一有限长的道路；并且对任何有限长的计算道路，计算结道路；并且对任何有限长的计算道路，计算结果都是果都是f(x)f(x)。第6页，共32页，编辑于2022年，星期一 对这种图灵机对这种图灵机 M M，Time Time M M（x x）表示输入）表示输入x x时，时，M M可能使用的最

7、短时间可能使用的最短时间，Space Space M M（x x）表示输入）表示输入x x时，时，M M可能使用的最少空间可能使用的最少空间。可以在不确定型计可以在不确定型计算机上实施的计算称为算机上实施的计算称为不确定型计算不确定型计算不确定型计算不确定型计算。（Non-deterministic computationNon-deterministic computation）第7页，共32页，编辑于2022年，星期一&算法复杂性算法复杂性采用该算法得到最终答案时所用的时间采用该算法得到最终答案时所用的时间。与此有关的因素有：与此有关的因素有：计算机本身的速度计算机本身的速度问题的规模问题

8、的规模一般指问题的输入长度一般指问题的输入长度（2 2）算法复杂性与算法分析）算法复杂性与算法分析为了衡量算法的效果所广泛采用的为了衡量算法的效果所广泛采用的标准标准是：是：第8页，共32页，编辑于2022年，星期一注注注注意意意意：同同一一规规模模的的例例子子用用同同一一算算法法，同同样样的的输输入长度所需运算时间也可能相差很远！入长度所需运算时间也可能相差很远！如如，用用单单纯纯形形法法解解LPLP，即即即即使使使使约约约约束束束束条条条条件件件件的的的的系系系系数数数数矩矩矩矩阵阵阵阵阶阶阶阶数数数数固固固固定定定定不不不不变变变变，所所所所需需需需的的的的初初初初等等等等运运运运算算算

9、算次次次次数数数数也也也也会会会会随随随随着着着着参参参参数数数数A A、b b、C C的的不不同同而而有有较较大大差差别别。当当取取C0C0的的的的极极极极端端端端情情情情况况况况，不不不不需需需需要要要要进进进进行行行行旋旋旋旋转转转转运运运运算算算算，初初初初始始始始可可可可行行行行解解解解就就就就是是是是最最最最优优优优解解解解；但但但但若若若若选选选选取取取取不不不不利利利利的的的的参参参参数数数数，达达达达到到到到最最最最优解所需要的迭代步骤可能就非常多。优解所需要的迭代步骤可能就非常多。优解所需要的迭代步骤可能就非常多。优解所需要的迭代步骤可能就非常多。第9页，共32页，编辑于2

10、022年，星期一 为为了了避避免免由由于于不不同同输输入入而而对对算算法法行行为为产产生生巨巨大大差差别别，考考察察所所有有规规模模为为n n的的输输入入，对对这这些些算算法法的的不不同同行行为为中中的的最最坏坏行行为为定定义义为为该该算算法法关关于于输输入入规规模模为为n n的的复复杂杂性性。因因此此，算算法法复复杂杂性性是是输输入入规规模模的的函函数数，比如比如10n10n3 3,2,2n n,nlog,nlog2 2n n等。等。第10页，共32页，编辑于2022年，星期一输输入入规规模模足足够够大大时时，在在复复杂杂性性函函数数中中，增增增增长长长长速速速速度度度度较较慢慢的的项项（如

11、如nlog2n+5n），终终将将被被增增长长速速度度很很快快的的项超过（该例中项超过（该例中n1000时，时，nlog2n5n）。）。在算法复杂性研究中，只有当输入规模很在算法复杂性研究中，只有当输入规模很大时，研究其计算行为才有意义，因为：大时，研究其计算行为才有意义，因为：只有规模大的输入，才能确定只有规模大的输入，才能确定算法可应用性的限制算法可应用性的限制算法可应用性的限制算法可应用性的限制。比如复杂性为比如复杂性为10n3与复杂性为与复杂性为9n3的算法间的差别可的算法间的差别可以忽略不计，因为这可以通过技术革新，使计算机以忽略不计，因为这可以通过技术革新，使计算机速度提高速度提高1

12、0倍而得到补偿。倍而得到补偿。第11页，共32页，编辑于2022年，星期一(c)(c)如果存在两个常数如果存在两个常数c,c0,c,c0,使得当使得当n n足够大时有足够大时有cg(n)f(n)cg(n),cg(n)f(n)cg(n),则记则记f(n)=g(n)f(n)=g(n)，用记号，用记号f(n)g(n)f(n)g(n)代替代替f(n)=(g(n),f(n)=(g(n),易见易见是一个等价关是一个等价关系，在该等价关系下，系，在该等价关系下，f(n)f(n)的等价类（即的等价类（即f(n)=(g(n)f(n)=(g(n)的所有的所有g(n)g(n)的集合）称为的集合）称为f(n)f(n)

13、f(n)f(n)的增长速度。的增长速度。的增长速度。的增长速度。定义定义定义定义 设设f(n),g(n)f(n),g(n)是定义在正整数上的正实值函数是定义在正整数上的正实值函数(a)(a)如果存在一个常数如果存在一个常数c0,c0,使得当使得当n n足够大时足够大时,有有f(n)cg(n),f(n)cg(n),则记则记f(n)=O(g(n)f(n)=O(g(n)；(b)(b)如果存在一个常数如果存在一个常数c0,c0,使得当使得当n n足够大时有足够大时有f(n)cg(n),f(n)cg(n),则记则记f(n)=(g(n)f(n)=(g(n)；第12页，共32页，编辑于2022年，星期一求出

14、一个算法所需时间比较好上界求出一个算法所需时间比较好上界的过程称为的过程称为算法分析算法分析。算算法法分分析析中中常常常常使使用用初初等等运运算算算算术术运运算算、比比较较、转转移移指指令令等等的的步步数数表表示示一一个个算算法法在在假假设设的的计计算算机机上上执执行行时时所所需需的的时时间间，即即每每做做一一次次初初等等运运算算，需需要要一一个个单单位位时时间间。而而用用用用算算算算法法法法的的的的输输输输入入入入规规规规模的函数度量该算法的复杂性。模的函数度量该算法的复杂性。模的函数度量该算法的复杂性。模的函数度量该算法的复杂性。第13页，共32页，编辑于2022年，星期一 为为了了把把输

15、输入入提提供供给给计计算算机机求求解解，必必须须用用固固定定字字母母表表（0，1，或或打打字字机机上上的的符符号号，或或ASCII字字母母）上上的的符符号号串串来来表表示示它它们们，这这就就是是所所谓谓的的编编码码。当当把把算算法法的的输输入入表表示示为为符符号号串串时时，那那麽麽输输入入规规模模就就定定义义为为该该符符号号串串的的长长度度（符符号号串串中中符符号号的的数数目目），称称为为输入长度输入长度。第14页，共32页，编辑于2022年，星期一例例1以以某某一一个个固固定定数数为为基基底底的的运运算算系系统统（如如十十进进制制或或二二进进制制）中中，表表示示一一个个整整数数n的的输输入入

16、规规模模：，因为，因为logBn=logn/logB,B固定后固定后logB是一个常数。是一个常数。例例2.试分析试分析LP的规模的规模.设设A、b、c中中的的元元素素均均为为整整数数，则则LP的的规规模模就就是是表表示示A、b、c所所需需符符号号的的数数目目。因因为为可可以以把把二二进进制制（十十进进制制）表表示示的的矩矩阵阵中中元元素素排排成成一一行行，用用符符号号线线适适当当地地隔隔开开以以表表示示矩矩阵阵的的行行或或列列，从从而而矩矩阵阵也也可可以以表表示示为为符符号号串串。所所以以，mn的的LP问问题题规规模模为为(mn+）其中）其中p是所有非零参数的乘积。是所有非零参数的乘积。第1

17、5页，共32页，编辑于2022年，星期一（3 3）多项式时间算法）多项式时间算法决定一个算法的决定一个算法的实际效用实际效用，要看其，要看其已知已知的最好时间上界之增长速度的最好时间上界之增长速度。目前计算机。目前计算机科学家们有一个公认的看法：科学家们有一个公认的看法：解一个计算解一个计算问题的算法，当其复杂性随输入规模的增问题的算法，当其复杂性随输入规模的增加而加而呈多项式地增长呈多项式地增长时，这个算法才是时，这个算法才是实际有效的实际有效的。第16页，共32页，编辑于2022年，星期一定义定义（多项式算法）（多项式算法）设有解某种问题的一设有解某种问题的一个算法，对于输入长度为个算法，

18、对于输入长度为L L的具体问题，其的具体问题，其计算步骤有一个上界计算步骤有一个上界P P（L L），），若若P P（y y）是）是y y的多项式，的多项式，则称此算法是一个则称此算法是一个多项式时间多项式时间算法算法（Polynomial-Time Algorithm for Polynomial-Time Algorithm for Linear ProgrammingLinear Programming），简称），简称多项式算法多项式算法。第17页，共32页，编辑于2022年，星期一函函数数近近似似值值NNlognn3106n81033100010141006641000，0001022

19、1000996610910302nnlognn！102420993，628，80012710301931013101581.05103017.8910294102567特点特点:表表表表1 1 1 1 多项式和指数函数增长情况表多项式和指数函数增长情况表多项式和指数函数增长情况表多项式和指数函数增长情况表 当输入规模增大时，任意一个多项式算法当输入规模增大时，任意一个多项式算法终将变得比指数算法更有效，见表终将变得比指数算法更有效，见表1 1。第18页，共32页，编辑于2022年，星期一在某种意义上，它很好地利用了技术发展的优点。在某种意义上，它很好地利用了技术发展的优点。每每次次技技术术突突

20、破破，计计算算机机速速度度提提高高10倍倍，则则多多项项式式算算法法原原来来1小小时时内内所所能能解解算算例例子子的的最最大大规规模模可可增增加加C倍倍，其其中中0C10,而而指指数数算算法法所所能能解解算算的的例例子子规规模模只只能增加一个常数能增加一个常数.表表2显示了多项式算法利用技术发展的优点情况显示了多项式算法利用技术发展的优点情况.第19页，共32页，编辑于2022年，星期一表表2 2 多项式算法利用技术发展的优点情况表多项式算法利用技术发展的优点情况表函函数数一一天天内内能能解解例子的规模例子的规模计计算算机机速速度度提提高高10倍倍后所能解例子的规模后所能解例子的规模nnlog

21、nn2n3108n410120.94810111061041010130.8710123.161062.15104182n10nnlognn!4012791443139515第20页，共32页，编辑于2022年，星期一 多项式算法有较好的封闭性多项式算法有较好的封闭性 n n个多项式算法可以结合起来解同个多项式算法可以结合起来解同一问题的某些特殊情形；一问题的某些特殊情形；一个多项式算法也可以利用另一个一个多项式算法也可以利用另一个多项式算法作为多项式算法作为“子程序子程序”，并且最后，并且最后的结果仍然是一个多项式算法。的结果仍然是一个多项式算法。第21页，共32页，编辑于2022年，星期一

22、（4 4）P P类、类、NPNP类、类、NPNP完全类、完全类、称具有多项式时间算法的一类问题为称具有多项式时间算法的一类问题为P P类问题类问题，简称简称P P问题问题。如：有向图中的路、最大匹配问题、。如：有向图中的路、最大匹配问题、最小支撑树问题等；最小支撑树问题等；NPNP类问题类问题也叫不确定性问题（或称非多项式确也叫不确定性问题（或称非多项式确定问题）。如果有一个用于求解此问题的算法，定问题）。如果有一个用于求解此问题的算法，对于它可以找到一个多项式时间算法来验证该算对于它可以找到一个多项式时间算法来验证该算法所得的结果是否为此问题的解，则称此问题属法所得的结果是否为此问题的解，则

23、称此问题属于于NPNP类问题，简称类问题，简称NPNP问题问题。NPNP完备的（完备的（NP-CompleteNP-Complete）如果一个判定问如果一个判定问题题A A是是NPNP的，而且所有其他的，而且所有其他NPNP问题都能多项式地归结问题都能多项式地归结到到A A，则称，则称A A是是NPNP完备的。完备的。第22页，共32页，编辑于2022年，星期一 所谓所谓多项式地归结，多项式地归结，指的是指的是多项式地时间归结，多项式地时间归结，其定义是：其定义是：设设A A1 1、A A2 2都是判定（即是都是判定（即是-否）问题，说否）问题，说A A1 1在多项式时在多项式时间内归结为间内

24、归结为A A2 2，当且仅当，当且仅当A A1 1有个多项式时间算法有个多项式时间算法A A1 1 ，并且，并且A A1 1是多次地以单位费用把是多次地以单位费用把A A2 2的算法的算法A2用作子程用作子程序的算法。则把序的算法。则把A A1 1叫做叫做A A1 1到到A A2 2的多项式时间归结。的多项式时间归结。于是，若问题于是，若问题于是，若问题于是，若问题A A A A是是是是NPNP完备的，若完备的，若完备的，若完备的，若A A有有效算法，有有效算法，有有效算法，有有效算法，则每个则每个则每个则每个NPNP问题也有有效算法问题也有有效算法问题也有有效算法问题也有有效算法。命题命题命

25、题命题：如果：如果A1多项式归结到多项式归结到A2，而，而A2有多项式算法，则有多项式算法，则A1也有多项式算法也有多项式算法。第23页，共32页，编辑于2022年，星期一 常用的证明一个问题为常用的证明一个问题为P P的方法一、的方法一、先先设计出求解问题设计出求解问题的一个算法的一个算法；然后证明其；然后证明其正确性正确性，即可利用该算法精确求解问题即可利用该算法精确求解问题；最后，通过仔细分；最后，通过仔细分析算法的实现过程来估计它所需的总的计算工作量，析算法的实现过程来估计它所需的总的计算工作量，即其即其计算复杂性计算复杂性，若所得估计值可用问题规模参数，若所得估计值可用问题规模参数（

26、如输入长度、问题维数等）的一个多项式函数来界（如输入长度、问题维数等）的一个多项式函数来界定，则表明该算法为多项式时间算法，从而得到问题定，则表明该算法为多项式时间算法，从而得到问题P P属于属于。如背包问题、排序问题等。如背包问题、排序问题等采用这种方法来证明问题属于采用这种方法来证明问题属于P P P P时，一般总要充分时，一般总要充分时，一般总要充分时，一般总要充分利用所证明问题的具体特性，以便设计出适当的利用所证明问题的具体特性，以便设计出适当的利用所证明问题的具体特性，以便设计出适当的利用所证明问题的具体特性，以便设计出适当的求解算法求解算法,使得它能够构成求解原问题的多项式时使得它

27、能够构成求解原问题的多项式时间算法。由于其对于具体问题的依赖性与多变性，间算法。由于其对于具体问题的依赖性与多变性，间算法。由于其对于具体问题的依赖性与多变性，间算法。由于其对于具体问题的依赖性与多变性，很难指定一个通用的证明步骤或方法。很难指定一个通用的证明步骤或方法。很难指定一个通用的证明步骤或方法。很难指定一个通用的证明步骤或方法。第24页，共32页，编辑于2022年，星期一 常用的证明一个问题为常用的证明一个问题为P P的方法二、的方法二、通过某种转换或逻辑推理来进行。通过某种转换或逻辑推理来进行。常见的技巧有：证常见的技巧有：证明可采用一些简单的、可在多项式时间内完成的变换明可采用一

28、些简单的、可在多项式时间内完成的变换方法，将原问题转换为另一已知的方法，将原问题转换为另一已知的P P类问题的求解；类问题的求解；说明可通过递推、分解等方法来对原问题进行简化，说明可通过递推、分解等方法来对原问题进行简化，使简化后的问题很容易在多项式时间内求解，而所采使简化后的问题很容易在多项式时间内求解，而所采用的分解等策略也可在多项式时间内完成；直接考察用的分解等策略也可在多项式时间内完成；直接考察原问题的可行解所可能存在的各种情形，当然这些可原问题的可行解所可能存在的各种情形，当然这些可能的不同情形不会超过问题规模的某个多项式，并说能的不同情形不会超过问题规模的某个多项式，并说明在每种情

29、况下均可在多项式时间内求解原问题明在每种情况下均可在多项式时间内求解原问题第25页，共32页，编辑于2022年，星期一 COOKCOOK定理定理 为了证明一个问题是为了证明一个问题是NP-NP-完备的，我们必须证明完备的，我们必须证明两件事：两件事：(a)(a)该问题是该问题是NPNP的的(b)(b)所有其他所有其他NPNP问题多项式转换到该问题问题多项式转换到该问题实际上，部分实际上，部分实际上，部分实际上，部分(b)(b)(b)(b)通常用证明某个已知的通常用证明某个已知的通常用证明某个已知的通常用证明某个已知的NP-NP-NP-NP-完备问完备问完备问完备问题可以多项式变换到要证的问题完

30、成的题可以多项式变换到要证的问题完成的题可以多项式变换到要证的问题完成的题可以多项式变换到要证的问题完成的.不过第一不过第一个个NP-NP-NP-NP-完备性证明必须包含部分完备性证明必须包含部分完备性证明必须包含部分完备性证明必须包含部分(b)(b)的直接证明。的直接证明。的直接证明。的直接证明。为此我们需要在证明中应用所有各种为此我们需要在证明中应用所有各种NPNPNPNP问题的共性。问题的共性。共性便是对于每个共性便是对于每个共性便是对于每个共性便是对于每个是是是是实例实例实例实例x x x x至少存在一个证明至少存在一个证明至少存在一个证明至少存在一个证明c(x)c(x)c(x)c(x

31、)和一个证明检验算法和一个证明检验算法第26页，共32页，编辑于2022年，星期一证明检验算法证明检验算法证明检验算法证明检验算法in s ta n c e$c e rtific a te符号串程序读写头第27页，共32页，编辑于2022年，星期一上述指令的含义如下：上述指令的含义如下：上述指令的含义如下：上述指令的含义如下：程序的最后语句：程序的最后语句：程序的最后语句：程序的最后语句：第28页，共32页，编辑于2022年，星期一NPNPNPNP定义：定义：第29页，共32页，编辑于2022年，星期一 通过通过COOKCOOK定理可以证明得出以下定理定理可以证明得出以下定理定理定理1:1:适

32、定性是适定性是NPNP完备的完备的定理定理2:2:适定性是适定性是NPNP完备的完备的定理定理3:3:团是团是NPNP完备的完备的定理定理4:4:对于图对于图G=(V,E)G=(V,E)和和V V的子集的子集S S，下述三个判断，下述三个判断 是等价的：是等价的：a)a)S S是是G G的一个团的一个团b)b)S S是是G G的补图的补图G G的独立集的独立集c)c)V-SV-S是是G G的点覆盖的点覆盖 -第30页，共32页，编辑于2022年，星期一 通过通过COOKCOOK定理可以证明得出以下定理定理可以证明得出以下定理定理定理5:5:多处理时间表是多处理时间表是NP-NP-完备的完备的定

33、理定理6:6:哈密顿圈是哈密顿圈是NP-NP-完备的完备的推论一推论一:哈密顿路问题是哈密顿路问题是NP-NP-完备的完备的推论二推论二:货郎问题是货郎问题是NP-NP-完备的完备的定理定理7:7:维匹配问题是维匹配问题是NPNP完备的完备的定理定理8:0-18:0-1背包问题是背包问题是NPNP完备的完备的推论一推论一:划分是划分是NP-NP-完备的完备的推论二推论二:整数背包是整数背包是NP-NP-完备的完备的第31页，共32页，编辑于2022年，星期一 NP-hardNP-hard（NPNP难）问题难）问题 若若NPNP中任何一个问题可在多项式时间归结中任何一个问题可在多项式时间归结为判定问题为判定问题A A，则称，则称A A为为NPNP难或难或NP-hardNP-hard问题。问题。图图2 2 算法复杂性的四类问题关系图算法复杂性的四类问题关系图PNPNPCNP-hard第32页，共32页，编辑于2022年，星期一