组合优化及算法.ppt

1、组合优化,Combinatorial Optimization,组合优化是运筹学的后继课程，同时也是运筹学的一个重要独立分支，是一类重要的优化问题,最优化(数学规划) 连续优化(数学规划)： 数学规划（线性规划、非线性规划）、非光滑优化、全局优化、锥优化等 离散优化：网络优化、组合优化、整数规划等 不确定规划：随机规划、模糊规划等,所谓组合(最)优化(Combinatorial Optimization)又称离散优化（Discrete Optimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等. 这类问题可用数学模型描述为：,优化问题三要素: (Min,f,F)或

2、(Max,f,F),其中D表示有限个点组成的集合(定义域) , f为目标函数,F=x|xD, g(x)0为可行域,组合优化 定义,组合优化 例,例 0-1背包问题(knapsack problem) 给定n个容积分别为ai，价值分别为ci的物品.设有一个容积为b的背包，如何以最大的价值装包？用数学规划模型表示为：,D= 0,1n,例 装箱问题(Bin Packing) 以尺寸为1的箱子装进给定的n个尺寸不超过1的物品，如何使所用的箱子个数最少?,组合优化 例,整数线性规划(Integer Linear Programming),(IP) .,我们假设线性整数规划的参数（约束矩阵和右端项系数）都

3、是整数(或有理数). 许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁,组合优化问题 定义,定义：组合优化问题 是一个极小化问题，或者是一个极大化问题，它由下述三部分组成： （1）实例集合； （2）对每一个实例I，有一个有穷的可行解集合S(I). （3）目标函数 ，对每一个实例I和每一个可行解 ，赋以一个有理数 .如果 是极小化（极大化）问题，则实例I 的最优解为这样一个可行解 ，它使得对于所有 ，它都有,算法 定义,定义：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述.,定型算法，即算法从前一步到后一步的运行是由当时状态唯一确定的.,如果存在一

4、个算法，他它对问题任意一个给定实例，在有限步之后，一定能得到该实例的答案，那么我们称算法能解决该问题.,近似算法、最优算法,近似算法：对于一个优化问题，如果给定任意一个实例I,算法A总能找到一个可行解，那么这个算法称为该问题的近似算法.,最优算法：如果进一步，如果这个可行解的目标值 总等于最优解值，则称A为最优算法.,典型组合优化问题,背包问题 装箱问题 平行机排序问题 图与网络优化问题 最小支撑树、最短路、最大流、最小费用流、最大基数匹配问题 指派问题 旅行售货商问题 斯坦纳最小树问题,本课程的主要目的讲授这些问题的数学描述和相应算法.,背包问题,给定n个容积分别为ai，价值分别为ci的物品

5、.设有一个容积为b的背包，如何以最大的价值装包？,平行机排序问题,M个完全相同的机器，n个相互独立的工件，加工时间互不相同，每个工件只需在任一台机器上不中断建工一次，如果安排加工方案，才能使预定的加工时间最短？,计算复杂性的概念,多项式时间算法,对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解. 那么如何衡量算法的优劣、有效与无效呢？,完全枚举法可以求得最优解,但枚举时间有时不可能接受,ATSP: (n-1)!枚举(TOUR,周游或环游) 设计算机每秒进行100亿次枚举,需 30! / 10e+10 2.65e+22 (秒) 即 2.65e+22

6、 / (365*24*60*60) 8.4e+13 (年),计算复杂性的概念,多项式时间算法,构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例,问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数. 问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件.,问题中的参数赋予了具体值的例子称为实例(instance).,衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量. 计算模型,C(I) =

7、 f(d(I) : 该函数关系称为算法的计算复杂性（度）,计算复杂性的概念,多项式时间算法,例 构造算法将n个自然数从小到大排列起来,算法 输入自然数a(1),a(2),a(n). for (i=1;ia(j) k=a(i);a(i)=a(j);a(j)=k; ,即该算法的计算复杂性（度）为O(n2),基本运算的总次数(最坏情形）：2n(n-1)=O(n2),计算复杂性的概念,定义1.4 假设问题和解决该问题的一个算法已经给定，若存在g(x)为多项式函数且对该问题任意的一个实例I，使得计算时间,成立，则称该算法为解决该问题的多项式(时间)算法(Polynomial time algorithm

8、). 当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法, 或指数(时间)算法(Exponential time algorithm),输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.,多项式时间算法,注：上面定义中，要求对该问题的任意一个实例均成立 ， 这种分析方法称为最坏性能分析（Worst-Case Analysis）,1.4 计算复杂性的概念,1.4.2 多项式时间算法,计算复杂性的概念,多项式时间算法,算法复杂性研究中:常将算法的计算时间表示为： 问题中的简单而典型的参数(如网络优化中n,m), 以及 问题中出现的数值(如弧上的权)的最大值(按

9、绝对值)K等自变量的函数关系,如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.,实际问题的输入规模/长度一定是m,n和logK的一个多项式函数. 所以： 多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.,特别地, 如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）, 则称相应的算法为强多项式(Strongly Polynomial)时间算法.,一般来说，伪多项式算法并不是多项式算法.,计算复杂性的概念,TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存

10、在,定义 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).,同样道理, 可以定义强多项式问题,伪多项式问题等.,TSP是否存在多项式时间算法? - 这是21世纪数学和计算机科学的挑战性问题之一,多项式问题,问题、实例与输入规模,评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入规模的关系：,比多项式问题类可能更广泛的一个问题类是非确定多项式 (Nondeterministic Polynomial，简记 NP ) 问题类,存在多项式算法的问题集合：多项式问题类（P）

11、,存在多项式函数 g(x) 满足上式时，算法为多项式算法,NP 类是通过判定问题引入的。,对任何一个优化问题， 可以考虑其三种形式： 最优化形式（原形：最优解） 计值形式（最优值） 判定形式（上界）,定义 如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题(Decision / recognition / feasibility problem). 称有肯定答案的实例为“是”实例(yes-instance). 称答案为“否”的实例为“否”实例或非“是”实例(no-instance).,判定问题 - 定义,例 线性规划问题(LP)的判定形式LP判定问题： 给定一个实数值z

12、，(LP)是否有可行解使其目标值不超过z？ 即：给定z，是否有 ?,难度降低,就有效算法的存在性而言，通常认为三种形式等价！,文字集,例 适定性问题(Satisfiability problem) 在逻辑运算中，布尔变量x的取值只有两个：“真”(1)和“假”(0)，逻辑运算有“或（+）”，“与（）”和“非（）.,判定问题 - 例,存在真值分配的表达式称为适定的(可满足的),文字集的任意一个子集中各元素（布尔变量）的“或”运算组成一个句子,多个句子的“与”运算组成一个表达式，如,适定性问题：给定布尔表达式 ， （SAT）是适定的吗？,判定问题 - 例,例 三精确覆盖(3-Exact Coveri

13、ng：X3C) 已知 的n个子集构成的子集族 ， 其中每个子集包含S中三个元素，F中是否存在m个子集 ， 使得 ？ 若m个子集满足上式，则称这m个子集精确覆盖S.,定义 若存在一个多项式函数g(x)和一个验证算法H，对一类判定问题A的任何一个“是” 实例I，都存在一个字符串S是I的可行解，满足其输入长度d(S)不超过g(d(I)，其中d(I)为I的输入长度，且算法H验证S为实例I的可行解的计算时间f(H)不超过g(d(I)，则称判定问题A是非确定多项式的。,考虑将求解判定问题的算法分为两个阶段： （1）猜测阶段：求出或猜测该问题的一个解 （2）检查或验证阶段：一旦解已经选定，将猜测的解作为输入

14、，验证此解是否为该实例“是”的回答. 我们称实例“是”回答的解为实例的可行解，否则称为不可行解.,所有非确定多项式问题的集合用NP表示.,非确定多项式问题类(NP) 定义,构造字符串（解）的过程及验证算法H一起构成一个算法，称为非确定多项式（时间）算法。,F中m个元素 是S的一个精确三覆盖的充分必要条件为： 相应的m个向量满足,集合S中共有3m个元素，子集族F中的每个子集合对应一个3m维向量：向量的3m个分量对应3m个元素，元素包含在对应子集中的分量为1，余下的为0. 例如： S= ，F中的一个元素 ，对应向量为 = (1,1,0,0,0,1)，表示为一个字符串(110001).,非确定多项式

15、问题类(NP) 例,按字符串向量问题，精确三覆盖 “是”实例的任何一个解可以用长度为3m2 的字符表示. 验证是否可行解的算法最多需3m2 个加法和3m个比较，算法的计算时间为3m2 +3m.,例 三精确覆盖属于NP,三精确覆盖问题任何一个实例的输入长度d(I)3m.,选g(x)= x2 /3+x ，则定义条件满足，所以三精确覆盖属于NP.,非确定多项式问题类(NP) ,问题A2的难度不低于问题A1,定义 给定问题A1和A2，若存在一个多项式算法满足： 对A1的任何一个实例I1，算法将实例I1的输入转换为A2的一个实例I2的输入； 这种转换过程使得实例I1和I2的解一一对应，即将实例I1的一个

16、解x1的输入转换为实例I2的一个解x2的输入，且x1为I1的“是”答案 x2是I2的一个“是”答案； 则称A1问题多项式转换为A2问题，算法称为问题A1到问题A2的一个多项式转换（算法）(Transformation).,常用的研究方法 - 多项式转换(变换)、多项式归约(归结),若A1多项式转换为A2，且A2P，则A1P 若A1多项式转换为A2，且A2NP，则A1NP,多项式转换(定义),NP完全问题类(NPC) -,定义 已知判定问题A1和A2，若存在多项式函数 和 ，使得对A1的任何实例I，在多项式时间内构造A2的一个实例，其输入长度不超过 ，并对A2的任何一个算法H2，都存在问题A1的

17、一个算法H1，使得H1算法调用H2算法且使得计算时间 ， 其中fH1(x)和fH2(x)分别表示算法H1和H2的计算时间与实例输入长度x之间的关系，则称问题A1多项式归约为问题A2.,根据A2的算法H2， 构造A1的算法H1的过程，即映射 ：H2 H1 称为从A1到A2的一个多项式归约(reduction).,多项式归约(定义),问题A2的难度不低于问题A1,若A1多项式归约为A2，且A2P，则A1P 若A1多项式归约为A2，且A2NP，则A1NP,若A1多项式归约为A2，则当把H1对H2的一次调用当成一次基本运算时， H1是A1的多项式算法。,NP完全问题类(NPC) - 多项式归约,多项式

18、转换是多项式归约的特例,归约映射可以如下构造： H1：STEP1 用多项式转换将A1的实例转换为A2的实例 STEP2 用H2算法求解A2的实例,即多项式转换可以认为是只允许调用一次H2的多项式归约,NP完全问题类(NPC) - 多项式归约 （例）,例1.22 适定问题多项式归约为三精确覆盖问题,定义（1）对于判定问题A，若ANP且NP中的任何一个问题可在多项式时间内归约为A，则称A为NP完全问题(NP-Complete或NPC).可以表示为ANPC.,NPC和NP-hard两者的区别是: 验证一个问题A是否为NP-hard无须判断A是否属于NP. 根据定义可知NPCNPH.,当已知一个问题属

19、于NPC或NPH时，如果再遇到一个新问题： （1）若已知问题多项式归约为新问题，则新问题属于NPH;,NP完全问题类(NPC) 定义,（2）对于判定问题A，若NP中的任何一个问题可在多项式时间归约为判定问题A，则称A为NP困难问题(NP-hard 或NPH) .可以表示为ANPH.,（2）若还可以验证新问题属于NP，则新问题属于NPC.,NP完全问题类(NPC),定理：如果问题A是P问题，且B可以在多项式时间内归约为A，则B也为P问题.,定理：P=NP当且仅当存在一个NPC问题有多项式时间算法.,定理：如果问题A是NPC问题，且B可以在多项式时间内归约为A，则B也为NPC问题.,定理：如果问题

20、A是NPH问题，且B可以在多项式时间内归约为A，则B也为NPH问题.,NP完全问题类(NPC),定理：除非P=NP，否则NPH问题没有多项式时间算法.,Cook定理：SAT为NP问题.,Cook计算复杂性理论的奠基性工作之一：第一个被证明的NPC问题！是证明许多其他NPC问题的出发点.,NP完全问题类(NPC) 证明（例）,例 三精确覆盖（X3C）属于NPC.,SAT多项式归约为X3C,X3CNP （例1.19）,X3C NPC,例 （特殊）（0-1）背包判定问题属于NPC.,X3C多项式变换为背包判定问题,背包判定问题NP,背包判定问题 NPC,NP完全问题类(NPC) 补充说明:,算法复杂性研究