资源描述：
《算法设计与分析讲义-中科院-陈玉福ch9》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、175第九章NP-完全问题§1关于问题及算法的描述为了应用算法复杂性理论，首先要对问题、问题的一般描述、计算模型、算法、算法的复杂性给出严格的定义。但在给出精确定义之前，我们先回顾一下有关概念的粗略解释。所谓一个问题(problem)是指一个有待回答、通常含有几个取值还未确定的自由变量的一个一般性提问(question)。它由两部分构成：一是对其关于参数的一般性描述；二是对该问题的答案所应满足的某些特性的说明。而一个问题的某个实例则可通过指定问题中所有参数的具体取值来得到。以下用Π表示某个问题，用Ι表示其实例。旅行商问题的参数是由所需访问城市的
2、一个有限集合C={C,C,",C}和11mC中每对城市C,C之间的距离d(C,C)所组成。它的一个解是对所给城市的一ijij个排序CC,,,"Cππ(1)(2)π()m使得该排序极小化下面表达式（目标函数）的值m−1∑d(Cπ(i),Cπ(i+1))+d(Cπ(m),Cπ(1))i=1旅行商问题的一个实例是通过指定城市的数目，并指定每两个城市之间的具体距离而得到的。例如：d(C,C)=10,d(C,C)=5,d(C,C)=9,{}121314C=C,C,C,C，1234d(C,C)=6,d(C,C)=9,d(C,C)=3232434就是旅行商问
3、题的一个实例，这个实例的一个解是排序CCCC,,,，因为四个1342城市的这个排序所对应旅行路线是所有可能环游路线中长度最小的，其长度为27。目前广泛采用的描述问题的方法主要有两种：一是将任一问题转化为所谓的可行性检验问题(feasibilityproblem)；二是把问题转化为判定问题(decisionproblem)。实际中几乎所有问题都可直接或间接地转述为判定问题。判定问题是答案只有“是”与“非”两种可能的问题。一个判定问题Π可简单地由其所有例子的集合D与答案为是的例子所构成的子集Y⊂D来刻ΠΠΠ画。不过，为了反映实际问题所具有的特性，通
4、常所采用的描述方法由两部分组176成。第一部分用诸如集合、图、函数等各种描述分量来刻画判定问题的一般性例子，以下用“例”表示这一部分；第二部分则陈述基于一般性例子所提出的一个“是非”提问，以下简称“问”。因此，一个具体例子属于D当且仅当它可通过Π用具有特定性质的某些对象替代一般性例子的所有一般性描述分量而得到，而一个例子属于Y当且仅当限定于该例子时，它对所述提问的回答为“是”。Π例待访问城市的有限集合C={C,C,",C}、每对城市C,C∈C之间的12mij++距离d(C,C)∈Z以及一个界B∈Z。ij问在C中存在一个总长不超过B的、通过所有城
5、市的旅行路线吗？也就是说，存在C的一个排序CC,,,"C，使得ππ(1)(2)π()mm−1∑d(Cπ(i),Cπ(i+1))+d(Cπ(m),Cπ(1))≤Bi=1这是一个将优化问题转化成判定问题的例子。一般地，一个优化问题可以看作是其所有实例的集合，而每一个实例为一个元素对(F,c)，其中F是可行解集，c是目标函数。一个最优化问题可以提出下述三种模式：V最优化模式：求最优解；V求值模式：求出最优值；V判定模式：给定一个实例(F,c)和一个整数L，问是否存在一个可行解f∈F，使得c(f)≤L？显然，在求解最优值不太困难的假设下，上述三种模式的
6、每一种都不比前一种困难。一般而且比较现实的假设是：最优值是一个整数，且这个整数或其绝对值的对数被输入长度的一个多项式所界定。在这种情况下，用二分搜索(或叫折半搜索)技术证明，只要判定模式存在多项式时间算法，求值模式也存在多项式时间算法。所谓算法(algorithm)是指用来求解某一问题的、带有一般性的一步一步的过程。它是用来描述可在许多计算机上实现任一计算流程的抽象形式，其一般性可以超越任何具体实现时的细节。注意，复杂性理论中对算法的定义与我们通常理解的具体算法(即用某种计算机语言编写的、可在某一特定计算机上实现的计算机程序)有所不同。不过，将
7、算法想象为某个具体的计算机程序，在许多情况下可以帮助我们理解有关概念和理论。177附：一个算法的严格定义直到1936年才出现，丘奇(AlonzoChurch)和图灵(AlanTuring)分别在他们的文章中给出。丘奇使用称为λ−演算的记号系统来定义算法，图灵用机器(图灵机)来定义算法，后来证明两者是等价的。此前，希尔伯特的第10问题就是要设计一个算法来测试多元多项式是否有整数根。不过他不用算法，而是用一句短语：“通过有限次运算就可以决定的过程”.我们这里采用图灵的定义,即借用图灵机计算模型来给出算法的精确定义。到目前为止，关于算法的描述大致有三
8、种不同的程次：一是形式描述，即详尽的写出图灵机的状态、转移函数等等，这是最底的最详细的描述；二是实现描述，使用日常语言来描述图灵机的运行，如怎么移动读
