概述与组合优化概念续

1、概述与组合优化概念续第1页，共24页，2022年，5月20日，6点14分，星期四P,NP,NPC,NP-hard启发式算法算法基础第2页，共24页，2022年，5月20日，6点14分，星期四第3页，共24页，2022年，5月20日，6点14分，星期四问题、实例与输入规模问题复杂性概念：复杂性的研究是从区分“问题”和“实例”并定义实例的“输入规模”开始的。第4页，共24页，2022年，5月20日，6点14分，星期四对于一个给定的组合优化问题，当问题中的参数赋予具体值时，称为问题的一个实例如表1。这些具体值称为数据，这些数据输入计算机所占的空间称为实例的输入长度或输入规模如表2。表1问题实例TSP

2、TSP例题中各参数为：100个城市，城市间距离 已知背包问题背包例题中各参数为：4个物品，大小分别为4,3,2,2，价值分别为8,7,5,7，包的大小为6.整数线性规划整数规划例题中n，A,b，c已知。第5页，共24页，2022年，5月20日，6点14分，星期四表2数据二进制编码输入长度11121021010104641 000 0007k2第6页，共24页，2022年，5月20日，6点14分，星期四一个实例完全由它的数据决定，给定一个问题的数据，即给定一个实例，我们可以用一种已知的计算机上的方法去求解。这种计算机上的求解方法称为算法。算法不仅仅局限于每一个实例，而是求解问题的统一程序。评价算

3、法的一个主要指标是计算所耗用的时间。第7页，共24页，2022年，5月20日，6点14分，星期四迄今为止，许多的组合优化问题都没有找到求最优解的多项式时间算法。比多项式问题类可能更广泛的一个问题类是非确定多项式时间（nondeterministic polynomial，NP）问题，NP的概念是由判断问题引入的。如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判断问题。称有肯定答案的实例为“是”实例，称答案为“否”的实例为“否”实例或非“是”实例。第8页，共24页，2022年，5月20日，6点14分，星期四优化问题与判定问题 在研究组合优化问题复杂性时，处理的方法是对给定的一

4、类优化问题，将其转化为判定问题，使对每一个实例只有“是”或“否”的回答。下面给出几个优化问题对应的判定问题。第9页，共24页，2022年，5月20日，6点14分，星期四将LP（目标函数为求最小）转化为LP判定问题第10页，共24页，2022年，5月20日，6点14分，星期四P类问题 给定每个问题的实例，我们有多项式时间算法得出答案是是还是不是。NP问题 如果X是判定问题的一个答案为“是”的实例，则存在一个对X 的一个多项式时间为界验证，使得能在多项式时间内验证这个证明的真实性；第11页，共24页，2022年，5月20日，6点14分，星期四定理： 即P是NP的子集。多项式时间归纳法（转换）两个判

5、定问题 ，如果 多项式归结到 ，则当 有多项式算法时， 也有多项式时间算法。第12页，共24页，2022年，5月20日，6点14分，星期四所有的P类问题都是属于NP问题.P是否等于NP?这个问题至今还未解决NP问题不一定都是难解的问题，比如简单的数组排序问题是P类问题，但是P属于NP，所以也是NP问题.现在还不知道是否有P=NP或者PNP，但是后来人们发现还有一系列的特殊NP问题，这类问题的特殊性质使得很多人相信PNP，只不过现在还无法证明。这类特殊的NP问题就是NP完全问题第13页，共24页，2022年，5月20日，6点14分，星期四NPComplete（NP完备类）第14页，共24页，20

6、22年，5月20日，6点14分，星期四常见的NP完备问题有成千上万个NP完备问题，如：整数线性规划、团、货郎担问题、适定性问题、点覆盖、独立集、哈密顿圈问题、01背包问题。事实上要证明一个问题是NP完备的转化为要证明： 1）该问题是NP的 2）有一个已知的NP完备问题可以多项式时间转化为该问题。第15页，共24页，2022年，5月20日，6点14分，星期四NP困难问题第16页，共24页，2022年，5月20日，6点14分，星期四PNPNPCNPH第17页，共24页，2022年，5月20日，6点14分，星期四一个问题的最优算法求得该问题每个实例的最优解，启发式算法是对应最优算法提出的。定义为：一

7、个基于直观和经验的短发，在可接受的花费下给出待解决组合最优化问题每一个实例的一个可行解，改可行解与最优解的偏离程度不一定事先可以预计。在某些情况下，特别是实际问题中，最优算法的计算时间使人无法忍受或因问题的难度事情计算时间随实例规模的增加以指数速度增加。如TSP枚举算法。第18页，共24页，2022年，5月20日，6点14分，星期四背包问题的贪婪算法Step1 对物品以 从大到小排列，不妨把排列记成1,2，,n, k=1.Step2 若 则 ，否则 k=k+1；当k=n+1时，停止；否则，重复 Step2 。 为贪婪算法的解，单位尺寸价值比越大越先装包。 第19页，共24页，2022年，5月2

8、0日，6点14分，星期四 的比值计算需要n次运算， 从小到大排列需要 次运算。 （k=1,2，,n）对于每一个k需要一次加法和一次比较 ，共2n次运算，这个贪婪算法的计算量为 ，是一个多项式时间算法。第20页，共24页，2022年，5月20日，6点14分，星期四启发式算法优点：1）数学模型本身是实际问题的简化，或多或少地忽略了一些因素；而且数据采集具有不确定性；参数估计估计具有不准确性；这些因素可能造成最优算法所得到的解比启发式算法更差。2）有些难的组合优化问题可能还没找到最优算法，由算法复杂性理论，它们的计算时间也是不可接受的。3）一些启发式算法可以用在最优算法中，比如分支定界算法中，可以用

9、启发式算法估计上下界。4）简单易行，比较直观，易被使用者接受。5）速度快，这在实时管理中非常重要。6）多数情况下，程序简单，易于在计算机上实现和修改.第21页，共24页，2022年，5月20日，6点14分，星期四启发式算法缺点1）不能保证求得最优解2）表现不稳定，启发式算法在同一问题的不同实例计算机中会有不同的效果，有些很好，有些很差。在实际应用中，这种不稳定性造成计算结果不可信，可能造成管理困难。3）算法的好坏依赖于实际问题，算法设计者的经验和技术，这一点很难总结规律，同时使不同算法之间难于比较。第22页，共24页，2022年，5月20日，6点14分，星期四启发式算法分类：1）简单直观的算法：如贪婪算法2）数学规划算法：拉格朗日松弛算法3）现代优化算法：遗传算法，蚁群算法第23页，共24页，2022年，5月20日，6点14分，星期四启发式算法性能分析评价算法优劣常用的三个主要指标：算法复杂性、解的偏离程度、和算法的稳健性，即同一算法对不同实例、在不同时间、不同起点的计算效果的差异