概述与组合优化概念续.ppt

-张宗祥 电子商务教研室P,NP,NPC,NP-hard 启发式算法 算法基础 问题、实例与输入规模 问题复杂性概念：复杂性的研究是从区分“问题”和“ 实例”并定义实例的“输入规模”开始的。 对于一个给定的组合优化问题，当问题中的参数赋 予具体值时，称为问题的一个实例如表1。这些具 体值称为数据，这些数据输入计算机所占的空间称 为实例的输入长度或输入规模如表2。 表1 问题实例 TSPTSP例题中各参数为：100个城市，城市间距离 已知 背包问题 背包例题中各参数为：4个物品，大小分别为4,3,2,2，价值分 别为8,7,5,7，包的大小为6. 整数线性规划 整数规划例题中n，A,b，c已知。 表2 数据二进制编码输入长度 111 2102 1010104 641 000 0007 k2 一个实例完全由它的数据决定，给定一个问题的数 据，即给定一个实例，我们可以用一种已知的计算 机上的方法去求解。这种计算机上的求解方法称为 算法。算法不仅仅局限于每一个实例，而是求解问 题的统一程序。评价算法的一个主要指标是计算所 耗用的时间。 迄今为止，许多的组合优化问题都没有找到求最优 解的多项式时间算法。 比多项式问题类可能更广泛的一个问题类是非确定 多项式时间（nondeterministic polynomial，NP ）问题，NP的概念是由判断问题引入的。 如果一个问题的每一个实例只有“是”或“否”两种答 案，则称这个问题为判断问题。称有肯定答案的实 例为“是”实例，称答案为“否”的实例为“否”实例或非 “是”实例。 优化问题与判定问题 在研究组合优化问题复杂性时，处理的方法是对 给定的一类优化问题，将其转化为判定问题，使 对每一个实例只有“是”或“否”的回答。下面给出几 个优化问题对应的判定问题。 将LP（目标函数为求最小）转化为LP判定问题 P类问题 给定每个问题的实例，我们有多项式时间算法得 出答案是是还是不是。 NP问题 如果X是判定问题的一个答案为“是”的实例，则 存在一个对X 的一个多项式时间为界验证，使得 能在多项式时间内验证这个证明的真实性； 定理： 即P是NP的子集。 多项式时间归纳法（转换） 两个判定问题 ，如果 多项式归结到 ，则 当 有多项式算法时， 也有多项式时间算法。 所有的P类问题都是属于NP问题. P是否等于NP?这个问题至今还未解决 NP问题不一定都是难解的问题，比如简单的数组排 序问题是P类问题，但是P属于NP，所以也是NP问 题. 现在还不知道是否有P=NP或者PNP，只不过现在还无 法证明。这类特殊的NP问题就是NP完全问题 NPComplete（NP完备类） 常见的NP完备问题 有成千上万个NP完备问题，如：整数线性规划、 团、货郎担问题、适定性问题、点覆盖、独立集、 哈密顿圈问题、01背包问题。事实上要证明一个 问题是NP完备的转化为要证明： 1）该问题是NP的 2）有一个已知的NP完备问题可以多项式时间转 化为该问题。 NP困难问题 P NP NPC NPH 一个问题的最优算法求得该问题每个实例的最优解 ，启发式算法是对应最优算法提出的。定义为：一 个基于直观和经验的短发，在可接受的花费下给出 待解决组合最优化问题每一个实例的一个可行解， 改可行解与最优解的偏离程度不一定事先可以预计 。 在某些情况下，特别是实际问题中，最优算法的计 算时间使人无法忍受或因问题的难度事情计算时间 随实例规模的增加以指数速度增加。如TSP枚举算 法。 背包问题的贪婪算法 Step1 对物品以 从大到小排列，不妨把排列记成 1,2，,n, k=1. Step2 若 则 ，否则 k=k+1；当k=n+1时，停止；否则，重复 Step2 。 为贪婪算法的解，单位尺寸价值比越大越 先装包。 的比值计算需要n次运算， 从小到大排列需 要 次运算。 （k=1,2，,n）对 于每一个k需要一次加法和一次比较 ，共2n次运算 ，这个贪婪算法的计算量为 ，是一个多项 式时间算法。 启发式算法优点： 1）数学模型本身是实际问题的简化，或多或少地忽略 了一些因素；而且数据采集具有不确定性；参数估计估 计具有不准确性；这些因素可能造成最优算法所得到的 解比启发式算法更差。 2）有些难的组合优化问题可能还没找到最优算法，由 算法复杂性理论，它们的计算时间也是不可接受的。 3）一些启发式算法可以用在最优算法中，比如分支定 界算法中，可以用启发式算法估计上下界。 4）简单易行，比较直观，易被使用者接受。 5）速度快，这在实时管理中非常重要。 6）多数情况下，程序简单，易于在计算机上实现和修 改. 启发式算法缺点 1）不能保证求得最优解 2）表现不稳定，启发式算法在同一问题的不同实 例计算机中会有不同的效果，有些很好，有些很差 。在实际应用中，这种不稳定性造成计算结果不可 信，可能造成管理困难。 3）算法的好坏依赖于实际问题，算法设计者的经 验和技术，这一点很难总结规律，同时使不同算法 之间难于比较。 启发式算法分类： 1）简单直观的算法：如贪婪算法 2）数学规划算法：拉格朗日松弛算法 3）现代优化算法：遗传算法，蚁群算法 启发式算法性能分析 评价算法优劣常用的三个主要指标：算法复杂性、 解的偏离程度、和算法的稳健性，即同一算法对不 同实例、在不同时间、不同起点的计算效果的差异 大小。 评价