《算法和算法复杂性课件.ppt》由会员分享，可在线阅读，更多相关《算法和算法复杂性课件.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图图灵灵机机中中无无限限长长的的带带被被分分成成一一个个个个小小空空格格，每每格格容容纳纳一一个个符符号号，对对每每一一部部图图灵灵机机而而言言，带带上上允允许使用的符号是有限的；许使用的符号是有限的；图图灵灵机机的的输输入入是是由由符符号号组组成成的的有有限限序序列列，称称之为符号行，输入符号行不能含空格符之为符号行，输入符号行不能含空格符B。读读写写头头每每次次左左或或右右移移动动一一格格，并并根根据据控控制制器器的的指指令令阅阅读读方方格格中中的的符符号号或或抹抹去去、重重写写方方格格中中的的符号，其初始位置是输入符号行最左边符号。符号，其初始位置是输入符号行最左边符号。读写头读写头 带
2、带（B B表示空格）表示空格）B 0 1 1 0 0 0 B控制器控制器 控制器控制器有有限个状态，其中启始状态和有有限个状态，其中启始状态和终止状态是两个特殊的状态；状态可依终止状态是两个特殊的状态；状态可依转移转移函数函数进行，进行，（q，a）=（p，b，v）意为：）意为：读写头看到符号读写头看到符号a时，处于状态时，处于状态q的控制器命的控制器命令其抹掉令其抹掉a，重写，重写b，并向，并向v（左或右）移动（左或右）移动一格，状态改变为一格，状态改变为p；控制器开始处于启始状态，图灵机当且控制器开始处于启始状态，图灵机当且仅当控制器处于终止状态时停止，此时仅当控制器处于终止状态时停止，此时
3、带上带上符号行符号行为输出。为输出。显然，图灵计算机计算的是显然，图灵计算机计算的是从符号行到符号从符号行到符号行的函数行的函数，但并不太限制其应用范围，但并不太限制其应用范围,它的它的计算计算时间时间是指读写头的移动次数是指读写头的移动次数,计算占用的空间计算占用的空间是是指带上被访问过的方格数指带上被访问过的方格数,当输入符号行是当输入符号行是x时时,图图灵机灵机M的计算时间的计算时间(或占用空间或占用空间)记为记为TimeM(x)(或或SpaceM(x)。对意义明确的数学问题是否会不存在算法对意义明确的数学问题是否会不存在算法对意义明确的数学问题是否会不存在算法对意义明确的数学问题是否会
4、不存在算法呢？呢？呢？呢？图灵精彩地论证了图灵精彩地论证了这样的不可判定问题这样的不可判定问题这样的不可判定问题这样的不可判定问题确实存在！确实存在！确实存在！确实存在！一一个个典典型型问问题题就就是是“停停停停机机机机问问问问题题题题”：给给定定一一个个带带有有输输入入的的计计算算机机程程序序，它它会会停停机机吗吗？图图灵灵证证明明了了，不不存存在在一一个个算算法法能能对对该该问问题题的的一切例子给出正确的答案。一切例子给出正确的答案。对于给定的问题，如果对于给定的问题，如果存在一种算法，可存在一种算法，可以对该问题的一切例子给出正确的答案，那以对该问题的一切例子给出正确的答案，那麽这个问题
5、就是麽这个问题就是可以计算可以计算可以计算可以计算的。的。可重复性可重复性归根于归根于因果关系的确定性因果关系的确定性因果关系的确定性因果关系的确定性，这，这种确定性也是当今世界上存在的各式各样计种确定性也是当今世界上存在的各式各样计算机的共同特点。算机的共同特点。2 2、不确定型计算和算法复杂性、不确定型计算和算法复杂性（1 1 1 1）不确定型计算：）不确定型计算：）不确定型计算：）不确定型计算：一个不确定型图灵机一个不确定型图灵机一个不确定型图灵机一个不确定型图灵机M M 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)。对这种图灵机对这种图灵机 M M，Time Time M M（x x）表示输入）表示输入x x时，时，M M可能使用的最短时间可能使用的最短时间，Space Space M M（x x）表示输
7、入表示输入x x时，时，M M可能使用的最少空间可能使用的最少空间。可以可以在不确定型计算机上实施的计算称为在不确定型计算机上实施的计算称为不确定不确定不确定不确定型计算型计算型计算型计算。（Non-deterministic computationNon-deterministic computation）&算法复杂性算法复杂性采用该算法得到最终答案时所用的时间采用该算法得到最终答案时所用的时间。与此有关的因素有：与此有关的因素有：计算机本身的速度计算机本身的速度问题的规模问题的规模一般指问题的输入长度一般指问题的输入长度（2 2）算法复杂性与算法分析）算法复杂性与算法分析为了衡量算法的效果
8、所广泛采用的为了衡量算法的效果所广泛采用的标准标准是：是：注注注注意意意意：同同同同一一一一规规规规模模模模的的的的例例例例子子子子用用用用同同同同一一一一算算算算法法法法，同同同同样样样样的的的的输入长度所需运算时间也可能相差很远！输入长度所需运算时间也可能相差很远！输入长度所需运算时间也可能相差很远！输入长度所需运算时间也可能相差很远！如如如如，用用用用单单单单纯纯纯纯形形形形法法法法解解解解LPLP，即即即即使使使使约约约约束束束束条条条条件件件件的的的的系系系系数数数数矩矩矩矩阵阵阵阵阶阶阶阶数数数数固固固固定定定定不不不不变变变变，所所所所需需需需的的的的初初初初等等等等运运运运算算
9、算算次次次次数数数数也也也也会会会会随随随随着着着着参参参参数数数数A A、b b、C C的的的的不不不不同同同同而而而而有有有有较较较较大大大大差差差差别别别别。当当当当取取取取C0C0的的的的极极极极端端端端情情情情况况况况，不不不不需需需需要要要要进进进进行行行行旋旋旋旋转转转转运运运运算算算算，初初初初始始始始可可可可行行行行解解解解就就就就是是是是最最最最优优优优解解解解；但但但但若若若若选选选选取取取取不不不不利利利利的的的的参参参参数数数数，达达达达到到到到最最最最优优优优解解解解所所所所需需需需要要要要的的的的迭迭迭迭代代代代步步步步骤骤骤骤可能就非常多。可能就非常多。可能就非
10、常多。可能就非常多。为为了了避避免免由由于于不不同同输输入入而而对对算算法法行行为为产产生生巨巨大大差差别别，考考察察所所有有规规模模为为n n的的输输入入，对对这这些些算算法法的的不不同同行行为为中中的的最最坏坏行行为为定定义义为为该该算算法法关关于于输输入入规规模模为为n n的的复复杂杂性性。因因此此，算算法法复复杂杂性性是是输输入入规模的函数，比如规模的函数，比如10n10n3 3,2,2n n,nlog,nlog2 2n n等。等。输入入规模模足足够大大时，在在复复杂性性函函数数中中，增增增增长长速速速速度度度度较慢慢的的项（如如nlog2n+5n），终将将被被增增长速速度度很很快快的
11、的项超超过（该例例中中n1000时，nlog2n5n）。）。在算法复杂性研究中，只有当输入规模很在算法复杂性研究中，只有当输入规模很大时，研究其计算行为才有意义，因为：大时，研究其计算行为才有意义，因为：只有只有规模大的模大的输入，才能确定入，才能确定算法可算法可算法可算法可应应用性的用性的用性的用性的限制限制限制限制。比如复。比如复杂性性为10n3与复与复杂性性为9n3的算的算法法间的差的差别可以忽略不可以忽略不计，因，因为这可以通可以通过技技术革新，使革新，使计算机速度提高算机速度提高10倍而得到倍而得到补偿。(c)(c)如果存在两个常数如果存在两个常数c,c0,c,c0,使得当使得当n
12、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)f(n)f(n)的增的增的增的增长速度。长速度。长速度。长速度。定义定义定义定义 设设f(n),g(n)f(n),g(n)是定义在正整数上的正实值函数是定
13、义在正整数上的正实值函数(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)；求出一个算法所需时间比较好上界求出一个算法所需时间比较好上界的过程称为的过程称为算法分析算法分析。算算法法分分析析中中常常常常使使用用初初等等运运算算算算术运运算算、比比较、转移移指指令令等等的的步步数
14、数表表示示一一个个算算法法在在假假设的的计算算机机上上执行行时所所需需的的时间，即即每每做做一一次次初初等等运运算算，需需要要一一个个单位位时间。而而用用用用算算算算法法法法的的的的输输入入入入规规模模模模的的的的函函函函数数数数度度度度量量量量该该算算算算法法法法的的的的复复复复杂杂性。性。性。性。为了了把把输入入提提供供给计算算机机求求解解，必必须用用固固定定字字母母表表（0，1，或或打打字字机机上上的的符符号号，或或ASCII字字母母）上上的的符符号号串串来来表表示示它它们，这就就是是所所谓的的编码。当当把把算算法法的的输入入表表示示为符符号号串串时，那那麽麽输入入规模模就就定定义为该符
15、符号号串串的的长度度（符符号号串串中中符符号的数目），称号的数目），称为输入入长度度。例例1以以某某一一个个固固定定数数为为基基底底的的运运算算系系统统（如如十十进进制制或或二二进进制制）中中，表表示示一一个个整整数数n的的输输入入规规模模：，因为，因为logBn=logn/logB,B固定后固定后logB是一个常数。是一个常数。例例2.试分析试分析LP的规模的规模.设设A、b、c中中的的元元素素均均为为整整数数，则则LP的的规规模模就就是是表表示示A、b、c所所需需符符号号的的数数目目。因因为为可可以以把把二二进进制制（十十进进制制）表表示示的的矩矩阵阵中中元元素素排排成成一一行行，用用符符
16、号号线线适适当当地地隔隔开开以以表表示示矩矩阵阵的的行行或或列列，从从而而矩矩阵阵也也可可以以表表示示为为符符号号串串。所所以以，mn的的LP问问题题规规模模为为(mn+）其中）其中p是所有非零参数的乘积。是所有非零参数的乘积。（3 3）多项式时间算法）多项式时间算法决定一个算法的决定一个算法的实际效用实际效用，要看其，要看其已知的最好时间上界之增长速度已知的最好时间上界之增长速度。目。目前计算机科学家们有一个公认的看法：前计算机科学家们有一个公认的看法：解一个计算问题的算法，当其复杂性解一个计算问题的算法，当其复杂性随输入规模的增加而随输入规模的增加而呈多项式地增长呈多项式地增长时，这个算法
17、才是实际有效的时，这个算法才是实际有效的。定义定义（多项式算法）（多项式算法）设有解某种问题设有解某种问题的一个算法，对于输入长度为的一个算法，对于输入长度为L L的具体问的具体问题，其题，其计算步骤有一个上界计算步骤有一个上界P P（L L），），若若P P（y y）是）是y y的多项式，的多项式，则称此算法是一则称此算法是一个个多项式时间算法多项式时间算法（Polynomial-Time Polynomial-Time Algorithm for Linear ProgrammingAlgorithm for Linear Programming），），简称简称多项式算法多项式算法。函函数
18、数近近似似值值NNlognn3106n81033100010141006641000，00010221000996610910302nnlognn！102420993，628，80012710301931013101581.05103017.8910294102567特点特点:表表表表1 1 1 1 多项式和指数函数增长情况表多项式和指数函数增长情况表多项式和指数函数增长情况表多项式和指数函数增长情况表 当输入规模增大时，任意一个多项式算当输入规模增大时，任意一个多项式算法终将变得比指数算法更有效，见表法终将变得比指数算法更有效，见表1 1。在某种意义上，它很好地利用了技术发展的优点。在某种意
19、义上，它很好地利用了技术发展的优点。每每次次技技术术突突破破，计计算算机机速速度度提提高高10倍倍，则则多多项项式式算算法法原原来来1小小时时内内所所能能解解算算例例子子的的最最大大规规模模可可增增加加C倍倍，其其中中0C10,而而指指数数算算法法所所能能解解算算的例子规模只能增加一个常数的例子规模只能增加一个常数.表表2显显示示了了多多项项式式算算法法利利用用技技术术发发展展的的优优点点情情况况.表表2 2 多项式算法利用技术发展的优点情况表多项式算法利用技术发展的优点情况表函函数数一一天天内内能能解解例子的规模例子的规模计计算算机机速速度度提提高高10倍倍后所能解例子的规模后所能解例子的规
20、模nnlognn2n3108n410120.94810111061041010130.8710123.161062.15104182n10nnlognn!4012791443139515 多项式算法有较好的封闭性多项式算法有较好的封闭性 n n个多项式算法可以结合起来解同个多项式算法可以结合起来解同一问题的某些特殊情形；一问题的某些特殊情形；一个多项式算法也可以利用另一一个多项式算法也可以利用另一个多项式算法作为个多项式算法作为“子程序子程序”，并且，并且最后的结果仍然是一个多项式算法。最后的结果仍然是一个多项式算法。（4 4）P P类、类、NPNP类、类、NPNP完全类、完全类、称具有多项式
21、时间算法的一类问题为称具有多项式时间算法的一类问题为P P类类问题问题，简称，简称P P问题问题。如：有向图中的路、最大。如：有向图中的路、最大匹配问题、最小支撑树问题等；匹配问题、最小支撑树问题等；NPNP类问题类问题也叫不确定性问题（或称非多项式也叫不确定性问题（或称非多项式确定问题）。如果有一个用于求解此问题的算确定问题）。如果有一个用于求解此问题的算法，对于它可以找到一个多项式时间算法来验法，对于它可以找到一个多项式时间算法来验证该算法所得的结果是否为此问题的解，则称证该算法所得的结果是否为此问题的解，则称此问题属于此问题属于NPNP类问题，简称类问题，简称NPNP问题问题。NPNP完
22、备的（完备的（NP-CompleteNP-Complete）如果一个判如果一个判定问题定问题A A是是NPNP的，而且所有其他的，而且所有其他NPNP问题都能多问题都能多项式地归结到项式地归结到A A，则称，则称A A是是NPNP完备的。完备的。所谓所谓多项式地归结，多项式地归结，指的是指的是多项式地时间归结，多项式地时间归结，其定义是：其定义是：设设A A1 1、A A2 2都是判定（即是都是判定（即是-否）问题，说否）问题，说A A1 1在多项式在多项式时间内归结为时间内归结为A A2 2，当且仅当，当且仅当A A1 1有个多项式时间算法有个多项式时间算法A A1 1 ，并且，并且A A1
23、 1是多次地以单位费用把是多次地以单位费用把A A2 2的算法的算法A2用作用作子程序的算法。则把子程序的算法。则把A A1 1叫做叫做A A1 1到到A A2 2的多项式时间归的多项式时间归结。结。于是，若问题于是，若问题于是，若问题于是，若问题A A A A是是是是NPNPNPNP完备的，若完备的，若完备的，若完备的，若A A A A有有效算法，有有效算法，有有效算法，有有效算法，则每个则每个则每个则每个NPNPNPNP问题也有有效算法问题也有有效算法问题也有有效算法问题也有有效算法。命题命题命题命题：如果：如果A1多项式归结到多项式归结到A2，而，而A2有多项式算法，有多项式算法，则则A
24、1也有多项式算法也有多项式算法。常用的证明一个问题为常用的证明一个问题为P P的方法一、的方法一、先先设计出求解问题设计出求解问题的一个算法的一个算法；然后证明其；然后证明其正确正确性性，即可利用该算法精确求解问题，即可利用该算法精确求解问题；最后，通过；最后，通过仔细分析算法的实现过程来估计它所需的总的计算仔细分析算法的实现过程来估计它所需的总的计算工作量，即其工作量，即其计算复杂性计算复杂性，若所得估计值可用问题，若所得估计值可用问题规模参数（如输入长度、问题维数等）的一个多项规模参数（如输入长度、问题维数等）的一个多项式函数来界定，则表明该算法为多项式时间算法，式函数来界定，则表明该算法
25、为多项式时间算法，从而得到问题从而得到问题P P属于属于。如背包问题、排序问题等。如背包问题、排序问题等采用这种方法来证明问题属于采用这种方法来证明问题属于采用这种方法来证明问题属于采用这种方法来证明问题属于P P P P时，一般总要充分时，一般总要充分时，一般总要充分时，一般总要充分利用所证明问题的具体特性，以便设计出适当的利用所证明问题的具体特性，以便设计出适当的利用所证明问题的具体特性，以便设计出适当的利用所证明问题的具体特性，以便设计出适当的求解算法求解算法求解算法求解算法,使得它能够构成求解原问题的多项式时使得它能够构成求解原问题的多项式时使得它能够构成求解原问题的多项式时使得它能够
26、构成求解原问题的多项式时间算法。由于其对于具体问题的依赖性与多变性，间算法。由于其对于具体问题的依赖性与多变性，间算法。由于其对于具体问题的依赖性与多变性，间算法。由于其对于具体问题的依赖性与多变性，很难指定一个通用的证明步骤或方法。很难指定一个通用的证明步骤或方法。很难指定一个通用的证明步骤或方法。很难指定一个通用的证明步骤或方法。常用的证明一个问题为常用的证明一个问题为P P的方法二、的方法二、通过某种转换或逻辑推理来进行。通过某种转换或逻辑推理来进行。常见的技巧有：常见的技巧有：证明可采用一些简单的、可在多项式时间内完成的证明可采用一些简单的、可在多项式时间内完成的变换方法，将原问题转换
27、为另一已知的变换方法，将原问题转换为另一已知的P P类问题的类问题的求解；说明可通过递推、分解等方法来对原问题进求解；说明可通过递推、分解等方法来对原问题进行简化，使简化后的问题很容易在多项式时间内求行简化，使简化后的问题很容易在多项式时间内求解，而所采用的分解等策略也可在多项式时间内完解，而所采用的分解等策略也可在多项式时间内完成；直接考察原问题的可行解所可能存在的各种情成；直接考察原问题的可行解所可能存在的各种情形，当然这些可能的不同情形不会超过问题规模的形，当然这些可能的不同情形不会超过问题规模的某个多项式，并说明在每种情况下均可在多项式时某个多项式，并说明在每种情况下均可在多项式时间内
28、求解原问题间内求解原问题 COOKCOOK定理定理 为了证明一个问题是为了证明一个问题是NP-NP-完备的，我们必须证完备的，我们必须证明两件事：明两件事：(a)(a)该问题是该问题是NPNP的的(b)(b)所有其他所有其他NPNP问题多项式转换到该问题问题多项式转换到该问题实际上，部分实际上，部分实际上，部分实际上，部分(b)(b)(b)(b)通常用证明某个已知的通常用证明某个已知的通常用证明某个已知的通常用证明某个已知的NP-NP-NP-NP-完备问完备问完备问完备问题可以多项式变换到要证的问题完成的题可以多项式变换到要证的问题完成的题可以多项式变换到要证的问题完成的题可以多项式变换到要证
29、的问题完成的.不过第一不过第一不过第一不过第一个个个个NP-NP-NP-NP-完备性证明必须包含部分完备性证明必须包含部分完备性证明必须包含部分完备性证明必须包含部分(b)(b)(b)(b)的直接证明。的直接证明。的直接证明。的直接证明。为此我们需要在证明中应用所有各种为此我们需要在证明中应用所有各种为此我们需要在证明中应用所有各种为此我们需要在证明中应用所有各种NPNPNPNP问题的共性。问题的共性。问题的共性。问题的共性。共性便是对于每个共性便是对于每个共性便是对于每个共性便是对于每个是是是是实例实例实例实例x x x x至少存在一个证明至少存在一个证明至少存在一个证明至少存在一个证明c(
30、x)c(x)c(x)c(x)和一个证明检验算法和一个证明检验算法和一个证明检验算法和一个证明检验算法证明检验算法证明检验算法证明检验算法证明检验算法in stan ce$certificate符号串程序读写头上述指令的含义如下：上述指令的含义如下：上述指令的含义如下：上述指令的含义如下：程序的最后语句：程序的最后语句：程序的最后语句：程序的最后语句：NPNPNPNP定义：定义：定义：定义：通过通过COOKCOOK定理可以证明得出以下定理定理可以证明得出以下定理定理定理1:1:适定性是适定性是NPNP完备的完备的定理定理2:2:适定性是适定性是NPNP完备的完备的定理定理3:3:团是团是NPNP
31、完备的完备的定理定理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的点覆盖的点覆盖 -通过通过COOKCOOK定理可以证明得出以下定理定理可以证明得出以下定理定理定理5:5:多处理时间表是多处理时间表是NP-NP-完备的完备的定理定理6:6:哈密顿圈是哈密顿圈是NP-NP-完备的完备的推论一推论一:哈密顿路问题是哈密顿路问题是NP-NP-完备的完备的推论二推论二:货郎问题是货郎问题是NP-NP-完备的完备的定理定理7:7:维匹配问题是维匹配问题是NPNP完备的完备的定理定理8:0-18:0-1背包问题是背包问题是NPNP完备的完备的推论一推论一:划分是划分是NP-NP-完备的完备的推论二推论二:整数背包是整数背包是NP-NP-完备的完备的 NP-hardNP-hard（NPNP难）问题难）问题 若若NPNP中任何一个问题可在多项式时间归结中任何一个问题可在多项式时间归结为判定问题为判定问题A A，则称，则称A A为为NPNP难或难或NP-hardNP-hard问题。问题。图图2 2 算法复杂性的四类问题关系图算法复杂性的四类问题关系图PNPNPCNP-hard