算法设计与分析-课件.pptx

1、1第一章第一章 算法概述算法概述第二章第二章 递归与分治策略递归与分治策略第三章第三章 动态规划动态规划第四章第四章 贪心算法贪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 随机化算法随机化算法算法设计与分析算法设计与分析 目录目录21.11.1 算法与程序算法与程序1.21.2 算法复杂度分析算法复杂度分析1.31.3 NPNP完全性理论完全性理论算法设计与分析算法设计与分析 第一章第一章 目录目录3“算法是任何定义好的计算程式，它取某些值算法是任何定义好的计算程式，它取某些值或值的集合作为输入，并产生某些值或值的集或值的集合作为输入，并产生某些值或值的集合

2、作为输出。合作为输出。”1.11.1 算法与程序算法与程序 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述算法算法:是将问题的输入转化为输出的一系列是将问题的输入转化为输出的一系列 计算或操作步骤计算或操作步骤.1 1 算法定义及其特性算法定义及其特性 4 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述例：求两个不全为例：求两个不全为0的非负整数的非负整数m,n的最大公约数的最大公约数 gcd(m,n)的的欧几里德算法描述欧几里德算法描述:1.如果如果n=0,返回返回m的值作为结果，过程结束；的值作为结果，过程结束；否则，进入第二步；否则，进入第二步；2.用用n

3、去除去除m，将余数赋给，将余数赋给 r;3.将将n的值赋给的值赋给m，将，将r的值赋给的值赋给n,返回第一步。返回第一步。算法描述举例5计算机算法与人工算法计算机算法与人工算法 算法概述算法概述例如例如 求定积分求定积分:s=人工处理步骤为人工处理步骤为找出找出f(x)的源函数的源函数F(x)利用牛利用牛-莱公式莱公式:s=F(b)-F(a)dxxfba)(算法设计与分析算法设计与分析 算法概述算法概述有些问题没有计算机算法有些问题没有计算机算法.有些问题计算机算法与人工算法不同有些问题计算机算法与人工算法不同.计算机算法：计算定积分采用数值积分的方计算机算法：计算定积分采用数值积分的方法法,

4、得到一个近似解得到一个近似解.6算法设计与分析算法设计与分析 算法概述算法概述算法的定义因看待的角度不同而不同算法的定义因看待的角度不同而不同哲学家：算法是解决一个问题的抽象行为哲学家：算法是解决一个问题的抽象行为序列。序列。码农：算法是一个计算过程，它接受一些码农：算法是一个计算过程，它接受一些输入，并产生某些输出。输入，并产生某些输出。高大上：算法是解决一个精确定义的计算高大上：算法是解决一个精确定义的计算问题的工具。问题的工具。核心：算法是解决问题的办法和法则，算法必核心：算法是解决问题的办法和法则，算法必须能够让人一步一步照着执行。须能够让人一步一步照着执行。7算法的特征算法的特征1.

5、1.有穷性有穷性 一个算法须在执行有限个运算步后终止一个算法须在执行有限个运算步后终止,每一步必须每一步必须在有限时间内完成在有限时间内完成.实际应用中实际应用中,算法的有穷性应该包括算法的有穷性应该包括执行时间的合理性执行时间的合理性.算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述 程序程序是算法的程序设计语言的具体实现是算法的程序设计语言的具体实现.可不满足性质可不满足性质1.1.一个算法面向一个问题，而不是仅仅求解一个问题的实例一个算法面向一个问题，而不是仅仅求解一个问题的实例 操作系统程序：是一个在无限循环中执操作系统程序：是一个在无限循环中执行的程序，而不是一个算法。

6、行的程序，而不是一个算法。8 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述例如例如 计算分段函数计算分段函数 f(x)=算法描述：输入变量算法描述：输入变量x,1 x100 0 x10若若x大于大于100的数，输出的数，输出1;若若x小于小于10的数，输出的数，输出0.输入输入10=x 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述5.5.输出输出 算法产生至少有一个输出项算法产生至少有一个输出项10 1.1.问题的陈述问题的陈述 理解问题，并用科学规范的语言把所求解问题进行准理解问题，并用科学规范的语言把所求解问题进行准确的描述确的描述,包括所有已知条件和输

7、出要求包括所有已知条件和输出要求.2.2.建立数学模型建立数学模型 通过对问题分析通过对问题分析,找出其中所有操作对象以及对象之找出其中所有操作对象以及对象之间的关系间的关系,并用数学语言加以描述并用数学语言加以描述.对非数值型解法来说对非数值型解法来说,数学模型通常是链表数学模型通常是链表,树树,图图,集合等数据结构集合等数据结构.2.2.算法设计过程算法设计过程(程序设计过程程序设计过程)算法设计与分析算法设计与分析 算法概述算法概述113.3.算法设计算法设计 根据数据模型根据数据模型,给出求解问题的一系列步骤给出求解问题的一系列步骤,且这些步骤可通过计算机的各种操作来实现且这些步骤可通

8、过计算机的各种操作来实现.4.4.算法的正确性证明算法的正确性证明 算法的正确性算法的正确性:对一切合法的输入对一切合法的输入,算法均能算法均能在有限次的计算后产生正确的输出在有限次的计算后产生正确的输出.算法设计与分析算法设计与分析 算法概述算法概述 5.5.算法的程序实现算法的程序实现 将一个算法描述正确地编写成机器语言程序将一个算法描述正确地编写成机器语言程序.12问题的求解过程问题的求解过程 算法概述算法概述6.6.算法分析算法分析 对执行该算法所消耗的计算机对执行该算法所消耗的计算机资源资源进行估进行估算算,对数值型算法还需分析算法的对数值型算法还需分析算法的稳定性稳定性和和误差误差

9、等等问题问题.计算机资源中最重要的是计算机资源中最重要的是时间和空间时间和空间资源资源,执行一个算法程序需要的时间和占用的内存空执行一个算法程序需要的时间和占用的内存空间分别称为间分别称为算法的时间复杂度和空间复杂性算法的时间复杂度和空间复杂性 .算法设计与分析算法设计与分析 算法概述算法概述13 描述算法的方式一般有三种描述算法的方式一般有三种:自然语言自然语言,流程图流程图,伪代码语言。伪代码语言。伪代码描述介于自然语言与程序伪代码描述介于自然语言与程序设计语言之间。设计语言之间。3.3.算法的描述算法的描述 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述144.算法结构算

10、法结构 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述任何算法都可由顺序结构、选择结构、循环结构这任何算法都可由顺序结构、选择结构、循环结构这三块三块“积木积木”通过组合和嵌套表达出来，遵循这种方通过组合和嵌套表达出来，遵循这种方法的程序设计，即为结构化程序设计法的程序设计，即为结构化程序设计。15数值型算法数值型算法:算法中的基本运算为算术运算算法中的基本运算为算术运算.非数值型算法非数值型算法:算法中的基本运算为逻辑运算算法中的基本运算为逻辑运算.串行算法串行算法:串行计算机上执行的算法串行计算机上执行的算法.并行算法并行算法:并行计算机上执行的算法并行计算机上执行的算法.

11、从处理方式上从处理方式上5.算法分类算法分类从解法上从解法上 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述本课程主要介绍非数值型的串行算法本课程主要介绍非数值型的串行算法.16l算法的复杂性算法的复杂性:指执行算法所消耗或占用的资指执行算法所消耗或占用的资源的数量源的数量l一个算法所需资源越多一个算法所需资源越多,我们就说它的复杂性我们就说它的复杂性越高越高,反之则低反之则低.算法复杂性分析算法复杂性分析 时间复杂性时间复杂性空间复杂性空间复杂性算法的复杂性算法的复杂性1.2 算法的复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述17考虑考虑空间复杂

12、性空间复杂性的理由的理由在多用户系统中运行时，需指明分给该程序在多用户系统中运行时，需指明分给该程序的内存大小；的内存大小；需预先知道计算机系统是否有足够的内存来需预先知道计算机系统是否有足够的内存来运行该程序；运行该程序；一个问题可能有若干个不同的内存解决方案一个问题可能有若干个不同的内存解决方案，从中择取，从中择取；用空间复杂性估计一个程序可能解决的问题用空间复杂性估计一个程序可能解决的问题的最大规模的最大规模。算法设计与分析算法设计与分析 算法概述算法概述18 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述考虑考虑时间复杂性时间复杂性的理由的

13、理由某些计算机用户需要提供程序运行时间的上限某些计算机用户需要提供程序运行时间的上限（用户可接受的）；（用户可接受的）；所开发的程序需要提供一个满意的实时反应。所开发的程序需要提供一个满意的实时反应。19 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述算法分析:(渐进算法分析):对执行算法所消对执行算法所消耗或占用的资源进行估算耗或占用的资源进行估算,给出算法耗费的给出算法耗费的限界函数限界函数.需解决两个问题需解决两个问题:如何度量复杂性如何度量复杂性?如何分析复杂性如何分析复杂性?20 算法的复杂性算法的复杂性:算法运行所需的时间和空间的数量算

14、法运行所需的时间和空间的数量.它与算法求解问题的问题的规模规模n n,算法的输入数输入数I 及算法本身算法本身有关.例如例如 在数组中找分量在数组中找分量c,n:数组中分量的个数数组中分量的个数 两个矩阵相乘两个矩阵相乘,n:矩阵的维数矩阵的维数 表中排序表中排序,n:数组中分量的个数数组中分量的个数 遍历一棵树遍历一棵树,n:树中节点数树中节点数1.复杂性的计量 算法复杂性分析算法复杂性分析问题的规模问题的规模n:指问题的输入数据或初始数据的量指问题的输入数据或初始数据的量.在不同的问题中在不同的问题中,n有不同的表现形式：有不同的表现形式：复杂性的计量复杂性的计量 算法概述算法概述算法设计

15、与分析算法设计与分析 算法概述算法概述21算法设计与分析算法设计与分析 算法概述算法概述 算法效率与计算机的性能有关，但此因素对所有算法算法效率与计算机的性能有关，但此因素对所有算法的影响相同。的影响相同。5*5的矩阵相乘与的矩阵相乘与10*10矩阵的矩阵相乘所需时间矩阵的矩阵相乘所需时间空间均不相同空间均不相同；找找c在数组在数组A中的位置中的位置,c=A(1),与与c=A(100),所需时间所需时间显然也显然也不同不同 顺序查找还是折半查找速度也是不一样的顺序查找还是折半查找速度也是不一样的.算法设计与分析算法设计与分析 算法概述算法概述22令令 n:n:问题规模问题规模 I:I:输入数据

16、输入数据 A:A:算法本身算法本身 C:C:算法的复算法的复杂性杂性,则则 C=f(n,I,A)C=f(n,I,A)将时间复杂性和空间复杂性分别考虑将时间复杂性和空间复杂性分别考虑,并用并用T T和和S S表示表示.则有则有:T=T(n,I,A)S=S(n,I,A)T=T(n,I,A)S=S(n,I,A)将算法将算法A A 隐含在函数名中隐含在函数名中,不同函数名代表不同算法不同函数名代表不同算法,则简化为则简化为 T=T(n,I)S=S(n,I)T=T(n,I)S=S(n,I)算法设计与分析算法设计与分析 算法概述算法概述23k1I)(n,etiii设一台抽象计算机提供的元运算有设一台抽象计

17、算机提供的元运算有k种种,记作记作 O1,Ok;设这些元运算每执行一次所需时间分别为设这些元运算每执行一次所需时间分别为 t1,tk;设在算法设在算法A中用到中用到Oi的次数为的次数为 ei,i=1,k,则则 ei=ei (n,I)T=T(n,I)=T=T(n,I)=当问题的规模当问题的规模 n和算法确定后和算法确定后,T是输入变元是输入变元 i 的函数的函数.仅以时间复杂性为例将复杂性函数具体化仅以时间复杂性为例将复杂性函数具体化.算法复杂性分析算法复杂性分析 复杂性的计量复杂性的计量 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述24说明：说明：我们不可能对规模为我们不可能

18、对规模为n的每一种合法输的每一种合法输入入I都计算都计算ei次，次，因为输入可能是无穷集合因为输入可能是无穷集合,我们只能对规模为我们只能对规模为n的问题的的问题的某类具有代表某类具有代表性性的合法输入统计相应的的合法输入统计相应的ei.算法复杂性分析算法复杂性分析 复杂性的计量复杂性的计量 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述25最好情况最好情况:T Tminmin(n)=T(n,I)=(n)=T(n,I)=kiiiInet1,)(kiiiInet1,)(kiiiInet1,)()(InT,kiiiInet1,)(nDImaxkiiiInet1*,)(NDIIPI)

19、T(n,)()(*,InTnDIIP)(nDImin最坏情况最坏情况:T:Tmaxmax(n)=T(n,I)=(n)=T(n,I)=平均情况平均情况:T:Tavgavg(n)=(n)=其中 Dn:规模为n的所有合法输入的集合D Dn n中达到中达到T Tmin min(n)(n)的一个输入的一个输入.D Dn n中达到中达到Tmax(n)Tmax(n)的一个输入的一个输入.P(I):P(I):出现输入为出现输入为I I的概率的概率nDImaxnDImin 算法复杂性分析算法复杂性分析 复杂性的计量复杂性的计量 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述26 算法复杂性分析算

20、法复杂性分析渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述当一个问题的输入规模很大时,算法的结构又很复杂时,采用前面介绍的精确分析就显得过于繁琐,为降低算法分析的代价,同时又保证估算的精确度,引入一个简化的计算模型来评估算法的开销.称为渐进分析称为渐进分析.渐进分析是对问题的规模充分大的算法问题的规模充分大的算法开销的估算。1.1.T(n)的渐进复杂性的渐进复杂性(渐进表达式渐进表达式):):(T(n)-)/T(n)0，n 时时2.2.渐进阶渐进阶:O,O,)(nT T)(nT T272.复杂性的渐进性态如果存在一个函数如果存在一个函数 使得当使得当n ,有有

21、 (T(n)-)/T(n)0称称 是是T(n)当当 n 时的时的渐进性态渐进性态 或或 渐进复杂性渐进复杂性 算法复杂性分析算法复杂性分析1.1.渐进性态渐进性态)(nT T)(nT T)(nT T渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述设设T(n)为算法为算法A的时间复杂性函数的时间复杂性函数(输入值固定输入值固定.如如Tmax,Tmin,Tavg),则它是则它是n 的单增函数。的单增函数。28当当n充分大时用充分大时用 代替代替T(n)作为算法复杂性的度量作为算法复杂性的度量,以以简化分析简化分析 例如例如 T(n)=3n2+4nlogn+7,则则

22、可以是可以是3n2 算法复杂性分析算法复杂性分析渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述在数学上在数学上,T(T(n)与与 有相同的最高阶项有相同的最高阶项.可取可取 为为略去略去T(T(n)的的低阶项后剩余的主项低阶项后剩余的主项.)(T n 比较两个算法时，如果他们的阶不同，就可分出效率高比较两个算法时，如果他们的阶不同，就可分出效率高低。故此时只需关心低。故此时只需关心 最高限的阶即可。可忽略最高最高限的阶即可。可忽略最高项系数或低阶项。项系数或低阶项。)(nT T)(nT T)(nT T)(T n 292.2.渐进性态的阶例如例如3n=O(n),

23、n+1024=O(n),n2=O(n3)?n3=O(n2)?2n2+11n-10=O(n2)若若 正常数正常数c c和和 自然数自然数NN0 0 使得当使得当 n n NN0 0 时时,有有f(f(n n)cg cg(n n)则称函数则称函数 f(f(n n)在在n n充分大时有充分大时有上界上界,且且 g g(n n)是它一个上界是它一个上界.记为记为 f(f(n n)=O()=O(g g(n n),),也称也称 f(f(n n)的的阶阶不高于不高于g g(n n)的的阶阶.设设f(n)和和 g(n)是定义在正整数集上的正函数是定义在正整数集上的正函数,(1)大大O O表示法表示法(算法运行

24、时间的上限)算法复杂性分析算法复杂性分析渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述30 算法复杂性分析算法复杂性分析渐进性态渐进性态三点注意三点注意:1 用来作比较的函数用来作比较的函数 g(n)应该尽量接近应该尽量接近 f(n).例如 3n+2=O(n2)松散的界限；3n+2=O(n)较好的界限2 不要产生错误界限。不要产生错误界限。例如 n2+100n+6，当 n3 时，n2+100n+6 算法复杂性分析算法复杂性分析渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述31 1.O(1.O(f f)+O(g)=O(max()

25、+O(g)=O(max(f f,g),g)2.O(2.O(f f)+O(g)=O()+O(g)=O(f f+g)+g)3.O(3.O(f f)O(g)=O()O(g)=O(f fg)g)4.4.如果如果 g(n)=O(g(n)=O(f f(n),(n),则则 O(O(f f)+O(g)=O()+O(g)=O(f f)5.5.f f=O(=O(f f)6.O(c 6.O(c f f(n)=O(n)=O(f f(n)(n)渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述运算规则运算规则32证明证明:O(:O(f f)+O(g)=O(max()+O(g)=O(max(

26、f f,g),g)算法设计与分析算法设计与分析 算法概述算法概述设设F(N)=O(f).根据O的定义,存在正常数C1和自然数N1,使得对所有NN1,有F(N)C1f(N).类似G(N)=O(g).根据O的定义,存在正常数C2和自然数N2,使得对所有NN2,有G(N)C2g(N).令令C3=maxC1,C2,N3=maxN1,N2,h(N)=maxf,g,则对所则对所有有NN3,有有 F(N)C1f(N)C1h(N)C3h(N).类似类似 G(N)C2g(N)C2h(N)C3h(N).O(O(f f)+O(g)=)+O(g)=F(N)+G(N)C3h(N)+C3h(N)=2C3h(N)=O(h)

27、=O(max(O(max(f f,g),g)33 例例 估计如下二重循环的估计如下二重循环的 T Tmaxmax(n)(n)的阶的阶.分析分析:内循环体只需内循环体只需O O(1)(1)时间时间,故故for i:=1 to n do for j:=1 to i do s1,s2,s3,s 4 ;s1,s2,s3,s4为单一赋值语句为单一赋值语句ij 1O(1)O()1O(1iij外循环共需外循环共需)O(n)2)1(O()O()O(21n1nniinii内循环共需内循环共需 渐进性态渐进性态 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述2.O(2.O(f f)+O(g)=O(

28、)+O(g)=O(f f+g)+g)34(2)(2)大大 表示法表示法 (算法运行时间的下限）算法运行时间的下限）若若 正常数正常数c和和自然数自然数N0使得当使得当 n N0 时时,有有f(n)c g(n)则称函数则称函数f(n)在在n充分大时有充分大时有下限下限,且且 g(n)是它的一个下是它的一个下限限,记为记为f(n)=(g(n)也称也称f(n)的阶不低于的阶不低于 g(n)的阶的阶渐进性态渐进性态 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述例例 T(n)=c1n2+c2n,则则 T(n)=(n2),),35 f f(n)=(n)=(g

29、 g(n)(n)等价于等价于 f f(n)=O(n)=O(g g(n)(n)且且 f f(n)=(n)=(g g(n)(n)称函数称函数f(n)f(n)与与g g(n)(n)同阶同阶.(3)3)表示法表示法例例 T(n)=c1n2+c2n,则则 T(n)=(n2)算法设计与分析算法设计与分析 算法概述算法概述36多项式阶算法多项式阶算法(有效算法):若算法的最坏情形时间复杂度若算法的最坏情形时间复杂度 T(n)=O(n(nk k););指数阶算法指数阶算法:若算法的最坏情形时间复杂度若算法的最坏情形时间复杂度T(n)=(a(an n),a1.,a1.这类算法可认为计算上不可行的算法这类算法可认

30、为计算上不可行的算法.渐进性态渐进性态 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述算法复杂性分类算法复杂性分类:最优算法最优算法:时间复杂性达到其下界的算法时间复杂性达到其下界的算法.O(1)O(1)O(logn)O(logn)O(n)O(n)O(nlogn)O(nlogn)O(nO(n2 2)O(nO(n3 3)O(2O(2n n)O(n!)O(n!)渐进性态渐进性态 算法复杂性分析算法复杂性分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述两点说明两点说明:时间复杂度并不是表示一个程序解决问题需要花多少时时间复杂度并不是表

31、示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的间，而是当问题规模扩大后，程序需要的时间长度增长时间长度增长得有多快得有多快。3838 算法复杂性分析算法复杂性分析 渐进分析渐进分析 算法概述算法概述算法设计与分析算法设计与分析 算法概述算法概述1.31.3 NPNP完全性理论完全性理论 确定性算法：设确定性算法：设A是求解问题的一个算法是求解问题的一个算法,如果在如果在算法的整个执行过程中算法的整个执行过程中,每一步只有一个确定的选每一步只有一个确定的选择择,并且对于同一输入实例运行算法并且对于同一输入实例运行算法,所得的结果严所得的结果严格一致格一致.P类问题类问题:对于

32、某个判定问题对于某个判定问题II，对于规模为对于规模为n的输的输入，能够在入，能够在O(nk)时间内运行一个确定性算法求解时间内运行一个确定性算法求解得到得到yes或或no的答案，其中的答案，其中k为某一确定常数。为某一确定常数。仅回答仅回答yes或或no的问题的问题算法设计与分析算法设计与分析 算法概述算法概述非确定性算法：设非确定性算法：设A是求解问题的一个算法是求解问题的一个算法,如果算法以如如果算法以如下猜测并验证的方式工作下猜测并验证的方式工作,算法算法A是非确定算法是非确定算法.(1)猜测阶段猜测阶段:对问题的输入实例产程一个任意字符串对问题的输入实例产程一个任意字符串y,在算法的

33、每一次执行在算法的每一次执行y的值可能不同的值可能不同,猜测以一种非确定猜测以一种非确定性的形式工作性的形式工作;(2)验证阶段验证阶段:用一个确定性算法验证用一个确定性算法验证:a)检查在猜测阶段产生的串检查在猜测阶段产生的串y是否是合适的形式，如是否是合适的形式，如果不是，算法停止得到果不是，算法停止得到no；b)如果如果y是合适的形式，再验证它是否是问题的解，是合适的形式，再验证它是否是问题的解，如果是算法停止得到如果是算法停止得到yes，否则算法停止得到，否则算法停止得到no。算法设计与分析算法设计与分析 算法概述算法概述NP类问题类问题:对于某个判定问题对于某个判定问题II，对于规模

34、为，对于规模为n的输入，的输入，能够在能够在O(nk)时间内运行一个非确定性算法求解得到时间内运行一个非确定性算法求解得到yes或或no,其中其中k为某一确定常数，该判定问题为某一确定常数，该判定问题II是一个是一个NP类类问题。问题。NP完全问题：令完全问题：令II是个判定问题，如果问题是个判定问题，如果问题II属于属于NP类问题，并且对类问题，并且对NP类问题中的每个问题类问题中的每个问题II，都有，都有(规约规约),则称判定问题则称判定问题II是个是个NP完全问题。完全问题。IIIIp输入转换输入转换IO输出转换输出转换OI算法算法A问题问题II问题问题II算法设计与分析算法设计与分析

35、算法概述算法概述NP类问题类问题NP完全问题完全问题P类问题类问题:能在多项式时间内解决的问题。能在多项式时间内解决的问题。NP类问题类问题:在多项式的时间里验证一个解的问题。在多项式的时间里验证一个解的问题。NPC问题问题:它是一个它是一个NP问题；所有的问题；所有的NP问题都可以约化问题都可以约化到它。到它。参考：参考：http:/ 算法概述算法概述“NP完全完全”问题至今为止既没有人找出求问题至今为止既没有人找出求解解NP完全问题的完全问题的多项式时间算法多项式时间算法，也没，也没有人能够证明对这类问题不存在多项时有人能够证明对这类问题不存在多项时间算法。间算法。如果任何如果任何NP完全

36、问题可以在多项式时间内解决完全问题可以在多项式时间内解决，那么所有，那么所有NP问题都有一个多项式时间算法。问题都有一个多项式时间算法。43算法设计与分析算法设计与分析 算法概述算法概述 旅行商问题，旅行商问题，旅行推销员问题、货郎担问题，简称为旅行推销员问题、货郎担问题，简称为TSP问题问题 设有设有n n个城市，个城市，已知任意两城市之间距离，现有一推销员想从某已知任意两城市之间距离，现有一推销员想从某一城市出发经过每一城市（且只经过一次）最后又回到出发点，一城市出发经过每一城市（且只经过一次）最后又回到出发点，问如何找一条最短路径。问如何找一条最短路径。设城市集合设城市集合v=v1,v2

37、,vm,c=(cij)为代价矩阵为代价矩阵,要求找要求找一条周游路径使路径长度最小一条周游路径使路径长度最小.城市集合城市集合v=v1,v2,vm,c=(cij)代价矩阵代价矩阵,对给定限界对给定限界b,问问:是否存在周游路线是否存在周游路线,其路径长度其路径长度 算法概述算法概述背包问题背包问题 给定一组物品，每种物品都有自己的重量和价给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择才能使得物品的总价格格，在限定的总重量内，如何选择才能使得物品的总价格最高。最高。布尔可满足性（简称布尔可满足性（简称SAT）问题）问题是用来解决给定的布尔是用来解决给定的布尔方程式，是否存在一组变量赋值，使问题为可满足。例如：方程式，是否存在一组变量赋值，使问题为可满足。例如：一个表达式：一个表达式：xyz=1？如果能，？如果能，x,y,z分别等于什么，分别等于什么，表达式被满足。表达式被满足。图着色问题图着色问题给定一个无向图给定一个无向图G（V,E），其中），其中V为顶点为顶点集合，集合，E为边集合，图着色问题即为将为边集合，图着色问题即为将V分为分为K个颜色组，个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的版本是希望获得最小的K值。值。