《算法和算法复杂性》PPT课件.ppt

专题一: 算法与复杂性,1、可计算性与算法,算法是用于求解严格确定的计算问题,能准确和全面理解的一系列指令。,相应于算法的数学实体就是英国数学家图灵（Turing）1936年提出的图灵机。图灵机是一种抽象化的计算机，一种标准的计算模型。由三部分组成：无限长的带、在带上可以左右移动的读写头和控制读写头的控制器。,图灵机中无限长的带被分成一个个小空格，每格容纳一个符号，对每一部图灵机而言，带上允许使用的符号是有限的； 图灵机的输入是由符号组成的有限序列，称之为符号行，输入符号行不能含空格符B。 读写头每次左或右移动一格，并根据控制器的指令阅读方格中的符号或抹去、重写方格中的符号，其初始位置是输入符号行最左边符号。,控制器有有限个状态，其中启始状态和终止状态是两个特殊的状态；状态可依转移函数进行，（q，a）=（p，b，v）意为：读写头看到符号a时，处于状态q的控制器命令其抹掉a，重写b，并向v（左或右）移动一格，状态改变为p； 控制器开始处于启始状态，图灵机当且仅当控制器处于终止状态时停止，此时带上符号行为输出。,显然，图灵计算机计算的是从符号行到符号行的函数，但并不太限制其应用范围,它的计算时间是指读写头的移动次数,计算占用的空间是指带上被访问过的方格数,当输入符号行是x时,图灵机M的计算时间(或占用空间)记为Time M(x) (或Space M(x)。,对意义明确的数学问题是否会不存在算法呢？图灵精彩地论证了这样的不可判定问题确实存在！,一个典型问题就是“停机问题”：给定一个带有输入的计算机程序，它会停机吗？图灵证明了，不存在一个算法能对该问题的一切例子给出正确的答案。,对于给定的问题，如果存在一种算法，可以对该问题的一切例子给出正确的答案，那麽这个问题就是可以计算的。,可重复性归根于因果关系的确定性，这种确定性也是当今世界上存在的各式各样计算机的共同特点。,2、不确定型计算和算法复杂性,（1）不确定型计算：,一个不确定型图灵机M计算一函数f（x）时，必须假定M满足以下条件：,若f(x)无定义,则对输入x, M的任何计算道路都是(时间)无限长的;,若f(x)有定义,则对输入x, M必有一有限长的道路；并且对任何有限长的计算道路，计算结果都是f(x)。,对这种图灵机 M，Time M（x）表示输入x时，M可能使用的最短时间，Space M（x）表示输入x时，M可能使用的最少空间。可以在不确定型计算机上实施的计算称为不确定型计算。 （Non-deterministic computation）,& 算法复杂性,采用该算法得到最终答案时所用的时间。 与此有关的因素有： 计算机本身的速度 问题的规模一般指问题的输入长度,（2）算法复杂性与算法分析,为了衡量算法的效果所广泛采用的标准是：,注意：同一规模的例子用同一算法，同样的输入长度所需运算时间也可能相差很远！ 如，用单纯形法解LP，即使约束条件的系数矩阵阶数固定不变，所需的初等运算次数也会随着参数A、b、C的不同而有较大差别。当取C0的极端情况，不需要进行旋转运算，初始可行解就是最优解；但若选取不利的参数，达到最优解所需要的迭代步骤可能就非常多。,为了避免由于不同输入而对算法行为产生巨大差别，考察所有规模为n的输入，对这些算法的不同行为中的最坏行为定义为该算法关于输入规模为n的复杂性。因此，算法复杂性是输入规模的函数，比如10n3,2n,nlog2n等。,输入规模足够大时，在复杂性函数中，增长速度较慢的项（如nlog2n+5n），终将被增长速度很快的项超过（该例中n1000时，nlog2n5n）。,在算法复杂性研究中，只有当输入规模很大时，研究其计算行为才有意义，因为：,只有规模大的输入，才能确定算法可应用性的限制。比如复杂性为10n3与复杂性为9n3的算法间的差别可以忽略不计，因为这可以通过技术革新，使计算机速度提高10倍而得到补偿。,(c)如果存在两个常数c,c0,使得当n足够大时有cg(n)f(n)cg(n),则记f(n)=g(n)，用记号f(n)g(n)代替f(n)=(g(n),易见是一个等价关系，在该等价关系下，f(n)的等价类（即f(n)=(g(n)的所有g(n)的集合）称为f(n)的增长速度。,定义 设f(n),g(n)是定义在正整数上的正实值函数,(a)如果存在一个常数c0,使得当n足够大时,有f(n)cg(n),则记f(n)=O(g(n)；,(b)如果存在一个常数c0,使得当n足够大时有f(n)cg(n),则记f(n)=(g(n)；,求出一个算法所需时间比较好上界 的过程称为算法分析。,算法分析中常常使用初等运算算术运算、比较、转移指令等的步数表示一个算法在假设的计算机上执行时所需的时间，即每做一次初等运算，需要一个单位时间。而用算法的输入规模的函数度量该算法的复杂性。,为了把输入提供给计算机求解，必须用固定字母表（0，1，或打字机上的符号，或ASCII字母）上的符号串来表示它们，这就是所谓的编码。当把算法的输入表示为符号串时，那麽输入规模就定义为该符号串的长度（符号串中符号的数目），称为输入长度。,例1以某一个固定数为基底的运算系统（如十进制或二进制）中，表示一个整数n的输入规模： ，因为logBn=logn/logB, B固定后logB是一个常数。,例2.试分析LP的规模. 设A、b、c中的元素均为整数，则LP的规模就是表示A、b、c所需符号的数目。因为可以把二进制（十进制）表示的矩阵中元素排成一行，用符号线适当地隔开以表示矩阵的行或列，从而矩阵也可以表示为符号串。所以，mn的LP问题规模为(mn+ ）其中p是所有非零参数的乘积。,（3）多项式时间算法,决定一个算法的实际效用，要看其已知的最好时间上界之增长速度。目前计算机科学家们有一个公认的看法：解一个计算问题的算法，当其复杂性随输入规模的增加而呈多项式地增长时，这个算法才是实际有效的。,定义（多项式算法）设有解某种问题的一个算法，对于输入长度为L的具体问题，其计算步骤有一个上界P（L）， 若P（y）是y的多项式，则称此算法是一个多项式时间算法（Polynomial-Time Algorithm for Linear Programming），简称多项式算法。,特点:,表1 多项式和指数函数增长情况表,当输入规模增大时，任意一个多项式算法终将变得比指数算法更有效，见表1。,每次技术突破，计算机速度提高10倍，则多项式算法原来1小时内所能解算例子的最大规模可增加C倍，其中0C10,而指数算法所能解算的例子规模只能增加一个常数. 表2显示了多项式算法利用技术发展的优点情况.,表2 多项式算法利用技术发展的优点情况表,多项式算法有较好的封闭性 n个多项式算法可以结合起来解同一问题的某些特殊情形； 一个多项式算法也可以利用另一个多项式算法作为“子程序”，并且最后的结果仍然是一个多项式算法。,（4）P类、NP类、NP完全类、,称具有多项式时间算法的一类问题为P类问题，简称P问题。如：有向图中的路、最大匹配问题、最小支撑树问题等；,NP类问题也叫不确定性问题（或称非多项式确定问题）。如果有一个用于求解此问题的算法，对于它可以找到一个多项式时间算法来验证该算法所得的结果是否为此问题的解，则称此问题属于NP类问题，简称NP问题。,NP完备的（NP-Complete）如果一个判定问题A是NP的，而且所有其他NP问题都能多项式地归结到A，则称A是NP完备的。,所谓多项式地归结，指的是多项式地时间归结，其定义是： 设A1、A2都是判定（即是-否）问题，说A1在多项式时间内归结为A2，当且仅当A1有个多项式时间算法A1 ，并且A1是多次地以单位费用把A2的算法A2用作子程序的算法。则把A1叫做A1到A2的多项式时间归结。,于是，若问题A是NP完备的，若A有有效算法， 则每个NP问题也有有效算法。,命题：如果A1多项式归结到A2，而A2有多项式算法，则A1也有多项式算法 。,常用的证明一个问题为P的方法一、 先设计出求解问题的一个算法；然后证明其正确性，即可利用该算法精确求解问题；最后，通过仔细分析算法的实现过程来估计它所需的总的计算工作量，即其计算复杂性，若所得估计值可用问题规模参数（如输入长度、问题维数等）的一个多项式函数来界定，则表明该算法为多项式时间算法，从而得到问题P属于。如背包问题、排序问题等,采用这种方法来证明问题属于P时，一般总要充分 利用所证明问题的具体特性，以便设计出适当的 求解算法,使得它能够构成求解原问题的多项式时 间算法。由于其对于具体问题的依赖性与多变性， 很难指定一个通用的证明步骤或方法。,常用的证明一个问题为P的方法二、 通过某种转换或逻辑推理来进行。常见的技巧有：证明可采用一些简单的、可在多项式时间内完成的变换方法，将原问题转换为另一已知的P类问题的求解；说明可通过递推、分解等方法来对原问题进行简化，使简化后的问题很容易在多项式时间内求解，而所采用的分解等策略也可在多项式时间内完成；直接考察原问题的可行解所可能存在的各种情形，当然这些可能的不同情形不会超过问题规模的某个多项式，并说明在每种情况下均可在多项式时间内求解原问题,COOK定理 为了证明一个问题是NP-完备的，我们必须证明两件事： (a)该问题是NP的 (b)所有其他NP问题多项式转换到该问题,实际上，部分(b)通常用证明某个已知的NP-完备问 题可以多项式变换到要证的问题完成的.不过第一 个NP-完备性证明必须包含部分(b)的直接证明。 为此我们需要在证明中应用所有各种NP问题的共性。 共性便是对于每个是实例x