算法和算法复杂性.ppt

NP-hard（NP难）问题 若NP中任何一个问题可在多项式时间归结为判定问题A，则称A为NP难或NP-hard问题。 图2 算法复杂性的四类问题关系图 P NP NPC NP-hard 专题一: 算法与复杂性 基 本 概 念 1、可计算性与算法 算法是用于求解严格确定的计算问题,能准确和全面理解的一系列指令。 相应于算法的数学实体就是英国数学家图灵（Turing）1936年提出的图灵机。图灵机是一种抽象化的计算机，一种标准的计算模型。由三部分组成：无限长的带、在带上可以左右移动的读写头和控制读写头的控制器。 图灵机中无限长的带被分成一个个小空格，每格容纳一个符号，对每一部图灵机而言，带上允许使用的符号是有限的； 图灵机的输入是由符号组成的有限序列，称之为符号行，输入符号行不能含空格符B。 读写头每次左或右移动一格，并根据控制器的指令阅读方格中的符号或抹去、重写方格中的符号，其初始位置是输入符号行最左边符号。 读写头 带 （B表示空格） B 0 1 1 0 0 0 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的不同而有较大差别。当取C≤0的极端情况，不需要进行旋转运算，初始可行解就是最优解；但若选取不利的参数，达到最优解所需要的迭代步骤可能就非常多。 为了避免由于不同输入而对算法行为产生巨大差别，考察所有规模为n的输入，对这些算法的不同行为中的最坏行为定义为该算法关于输入规模为n的复杂性。因此，算法复杂性是输入规模的函数，比如10n3,2n,nlog2n等。 输入规模足够大时，在复杂性函数中，增长速度较慢的项（如nlog2n+5n），终将被增长速度很快的项超过（该例中n1000时，nlog2n5n）。 在算法复杂性研究中，只有当输入规模很大时，研究其计算行为才有意义，因为： 只有规模大的输入，才能确定算法可应用性的限制。比如复杂性为10n3与复杂性为9n3的算法间的差别可以忽略不计，因为这可以通过技术革新，使计算机速度提高10倍而得到补偿。 (c)如果存在两个常数c,c0,使得当n足