第一章概述与组合优化概念续

1、第一章概述与组合优化概念续P,NP,NPC,NP-hard启发式算法算法基础问题、实例与输入规模问题、实例与输入规模问题复杂性概念：复杂性的研究是从区分“问题”和“实例”并定义实例的“输入规模”开始的。对于一个给定的组合优化问题，当问题中的参数赋予具体值时，称为问题的一个实例如表1。这些具体值称为数据，这些数据输入计算机所占的空间称为实例的输入长度或输入规模如表2。表1问题问题实例实例TSPTSP例题中各参数为：100个城市，城市间距离 已知背包问题背包例题中各参数为：4个物品，大小分别为4,3,2,2，价值分别为8,7,5,7，包的大小为6.整数线性规划整数规划例题中n，A,b，c已知。ij

2、d表2数据数据二进制编码二进制编码输入长度输入长度11121021010104641 000 0007k2log1k 一个实例完全由它的数据决定，给定一个问题的数据，即给定一个实例，我们可以用一种已知的计算机上的方法去求解。这种计算机上的求解方法称为算法。算法不仅仅局限于每一个实例，而是求解问题的统一程序。评价算法的一个主要指标是计算所耗用的时间。迄今为止，许多的组合优化问题都没有找到求最优解的多项式时间算法。比多项式问题类可能更广泛的一个问题类是非确定多项式时间（nondeterministic polynomial，NP）问题，NP的概念是由判断问题引入的。如果一个问题的每一个实例只有“是

3、”或“否”两种答案，则称这个问题为判断问题。称有肯定答案的实例为“是”实例，称答案为“否”的实例为“否”实例或非“是”实例。优化问题与判定问题优化问题与判定问题 在研究组合优化问题复杂性时，处理的方法是对给定的一类优化问题，将其转化为判定问题，使对每一个实例只有“是”或“否”的回答。下面给出几个优化问题对应的判定问题。将LP（目标函数为求最小）转化为LP判定问题P P类问题类问题 给定每个问题的实例，我们有多项式时间算法得出答案是是还是不是。NPNP问题问题 如果X是判定问题的一个答案为“是”的实例，则存在一个对X 的一个多项式时间为界验证，使得能在多项式时间内验证这个证明的真实性；定理： 即

4、P是NP的子集。多项式时间归纳法多项式时间归纳法（转换）两个判定问题 ，如果 多项式归结到 ，则当 有多项式算法时， 也有多项式时间算法。12,A A1A2A2A1A所有的P类问题都是属于NP问题.P是否等于NP?这个问题至今还未解决NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题.现在还不知道是否有P=NP或者PNP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信PNP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题NPNPCompleteComplete（NP完备类）常见的常见的NPNP完备问题完备问题有

5、成千上万个NP完备问题，如：整数线性规划、团、货郎担问题、适定性问题、点覆盖、独立集、哈密顿圈问题、01背包问题。事实上要证明一个问题是NP完备的转化为要证明： 1）该问题是NP的 2）有一个已知的NP完备问题可以多项式时间转化为该问题。NPNP困难问题困难问题PNPNPCNPH一个问题的最优算法求得该问题每个实例的最优解，启发式算法是对应最优算法提出的。定义为：一个基于直观和经验的短发，在可接受的花费下给出待解决组合最优化问题每一个实例的一个可行解，改可行解与最优解的偏离程度不一定事先可以预计。在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问题的难度事情计算时间随实例规模

6、的增加以指数速度增加。如TSP枚举算法。背包问题的贪婪算法Step1 对物品以 从大到小排列，不妨把排列记成1,2，,n, k=1.Step2 若 则 ，否则 k=k+1；当k=n+1时，停止；否则，重复 Step2 。 为贪婪算法的解，单位尺寸价值比越大越先装包。 iica11,kiikia xab1kx 0kx 12(,.,)kx xx 的比值计算需要n次运算， 从小到大排列需要 次运算。 （k=1,2，,n）对于每一个k需要一次加法和一次比较 ，共2n次运算，这个贪婪算法的计算量为 ，是一个多项式时间算法。iicaiica2( log)nn11,kiikia xab2( log)nn启发

7、式算法优点：1）数学模型本身是实际问题的简化，或多或少地忽略了一些因素；而且数据采集具有不确定性；参数估计估计具有不准确性；这些因素可能造成最优算法所得到的解比启发式算法更差。2）有些难的组合优化问题可能还没找到最优算法，由算法复杂性理论，它们的计算时间也是不可接受的。3）一些启发式算法可以用在最优算法中，比如分支定界算法中，可以用启发式算法估计上下界。4）简单易行，比较直观，易被使用者接受。5）速度快，这在实时管理中非常重要。6）多数情况下，程序简单，易于在计算机上实现和修改.启发式算法分类：1）简单直观的算法：如贪婪算法2）数学规划算法：拉格朗日松弛算法3）现代优化算法：遗传算法，蚁群算法启发式算法性能分析评价算法优劣常用的三个主要指标：算法复杂性、解的偏离程度、和算法的稳健性，即同一算法对不同实例、在不同时间、不同起点的计算效果的差异大小。评