np完全理论-南阳理工学院.pdfVIP

参考文献253 第九章 NP 完全理论 教学目标 理解易解问题和难解问题 理解 P 类与 NP 类的概念 理解 NP 完全问题的概念 理解近似算法的性能比及相对误差的概念 通过实例理解 NP 完全问题的近似算法 NP-complete(NP-完全)一词是 70 年代初才开始出现的一个新术语.在短短的几十年间， 它在数学、计算机科学和运筹学等领域广为流传，其蔓延之势至今有增无减。今天， NP-complete 一词已经成为算法设计者在求解规模大而又复杂困难的问题时所面临的某种难 以逾越的深渊的象征。这是一个耗费了很多时间和精力也没有解决的终极问题，好比物理学 中的大统一和数学中的歌德巴赫猜想等。 2000 年初，美国克雷数学研究所的科学顾问委员会选定了七个 “千年大奖问题”，该 研究所的董事会决定建立七百万美元的大奖基金，每个 “千年大奖问题”的解决都可获得百 万美元的奖励。克雷数学研究所 “千年大奖问题”的选定，其目的不是为了形成新世纪数学 发展的新方向，而是集中在数学家们梦寐以求而期待解决的重大难题上。NP 完全问题排在 百万美元大奖的首位，足见它的显赫地位和无穷魅力。 现在，人们已经认识到，在科学和很多工程技术领域里，常常遇到的许多有重要意义而 又没有得到很好解决的难题是 NP 完全问题。另外，由于人们的新发现，这类问题的数目不 断增加。 因此，熟悉和了解NP 完全问题的概念以及相关理论，对于所有关心上述各个领域中可 计算性方面的人们和算法设计者来讲，是一件具有重要意义的事情。 9.1 易解问题和难解问题 无论是计算机专业人士还是计算机科学家，在研究问题的计算复杂性时，它们首先考虑 的都是一个给定的问题是不是能够用某些算法在多项式时间内求解，即算法的时间复杂性是 k 不是 O(n ) ，其中，n 是问题规模，k 是一个非负整数。Ednonds 于 1965 年指出只有多项式 时间算法才称得上是“好”算法，他还认为有的问题可能不存在求解它们的这种 “好”算法。 99 8 100 其实，多项式时间复杂性并不一定就意味着较低的时间要求，例如：10 n 和 n 都是 多项式函数，但它们的值却大得惊人。既然如此，为什么科学家还要用它作标准去定义问题 呢？原因可能有以下几条： （1） 这样做可以为有过多时间要求的那类问题提供一个很好的标准。 （2 ） 多项式函数在加、乘运算下是自封闭的，并且在那些可以作为有用的分析算法 复杂性的函数类中，多项式函数是具有这种性质的最小函数类。 （3 ） 多项式时间复杂性的分析结果，对于常用的各种计算机形式模型，具有不变性。 应该说明，对于能找到多项式时间算法的实际问题，它们的多项式时间复杂性函数，一 般都不含有特大系数或较高幂指数的项。 Print t