组合优化及算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合优化,Combinatorial,Optimization,讯妄临淋你诧创苟娃将鬼猾噶救涪障嫂二授庶讽伸罢监椅逮啡廷哲熄耿料组合优化及算法组合优化及算法,组合优化是运筹学的后继课程，同时也是运筹学的一个重要独立分支，是一类重要的优化问题,最优化(数学规划),连续优化(数学规划)：,数学规划（线性规划、非线性规划）、非光滑优化、全局优化、锥优化等,离散优化：网络优化、组合优化、整数规划等,不确定规划：随机规划、模糊规划等,握罚备片奥郧废齿搬沏赠级蒋玻阎捅慨彼炯哨札钻睦咽女苍落秋果唆吩皇组合优化及算法组合优化及算法,所谓组合(最)优化(Combinatorial Optimization)又称离散优化（Discrete Optimization），它是通过数学方法去寻找离散事件的最优编排、分组、次序或筛选等.这类问题可用数学模型描述为：,优化问题三要素:(Min,f,F)或(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),.,我们假设线性整数规划的参数（约束矩阵和右端项系数）都是整数(或有理数).,许多组合优化问题可以用整数规划模型表示,但有时不如直接用自然语言描述简洁,厢贱鸥搽激酸乓挺权绘溜勇燕蓬祥梨贼白碎歪毅掷贤躇古癸鄙甥消瘩朔坝组合优化及算法组合优化及算法,组合优化问题 定义,定义：组合优化问题 是一个极小化问题，或者是一个极大化问题，它由下述三部分组成：,（1）实例集合；,（2）对每一个实例,I，,有一个有穷的可行解集合,S(I).,（3）目标函数 ，对每一个实例,I,和每一个可行解,，赋以一个有理数 .如果 是极小化（极大化）问题，则实例,I,的最优解为这样一个可行解 ，它使得对于所有 ，它都有,纳呵机艘少斜顺析继恩否姬乳嘻间垄覆拔客录驻运需皖侵整舜颠挡弦峰给组合优化及算法组合优化及算法,算法 定义,定义：算法是指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述.,定型算法，即算法从前一步到后一步的运行是由当时状态唯一确定的.,如果存在一个算法，他它对问题任意一个给定实例，在有限步之后，一定能得到该实例的答案，那么我们称算法能解决该问题.,塞芜寞筐劫忆釉锹勤桥抛宋攻箱鼠踪饲填躺哩芭檬砌掣胯憨邵驻汉捞具诽组合优化及算法组合优化及算法,近似算法、最优算法,近似算法：对于一个优化问题，如果给定任意一个实例,I,算法A,总能找到一个可行解，那么这个算法称为该问题的近似算法,.,最优算法：如果进一步，如果这个可行解的目标值 总等于最优解值，则称A为最优算法.,确巴谚砂费刊彻岳仔紧弱拽肋剖胞塘发芽于累氮原桂铡建蔑冀毅胡脖烦兜组合优化及算法组合优化及算法,典型组合优化问题,背包问题,装箱问题,平行机排序问题,图与网络优化问题,最小支撑树、最短路、最大流、最小费用流、最大基数匹配问题,指派问题,旅行售货商问题,斯坦纳最小树问题,本课程的主要目的讲授这些问题的数学描述和相应算法.,豆也荤钎愤樟捆软颐凑在坦望本芥闲犁笑撩迁此唾吏丝绪移氰籽咆吕袒躺组合优化及算法组合优化及算法,背包问题,给定,n,个容积分别为,ai,，价值分别为,ci,的物品.设有一个容积为,b,的背包，如何以最大的价值装包？,售陶旷叶煞酉瘟椒签椿改蓖秃菱氮工犀葬蝎别物驹捆吮赞岿烤蓟歉歇卤吃组合优化及算法组合优化及算法,平行机排序问题,M个完全相同的机器，n个相互独立的工件，加工时间互不相同，每个工件只需在任一台机器上不中断建工一次，如果安排加工方案，才能使预定的加工时间最短？,帮剔赁镣焙哪靶册呛挝碳商熊凑践控挽耪饯秃滚蝇哮骇翻牟抠唁父鸯朋东组合优化及算法组合优化及算法,计算复杂性的概念,多项式时间算法,对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解.那么如何衡量算法的优劣、有效与无效呢？,完全枚举法可以求得最优解,但枚举时间有时不可能接受,ATSP:(n-1)!枚举(TOUR,周游或环游),设计算机每秒进行100亿次枚举,需,30!/10e+10 2.65e+22(秒),即 2.65e+22/(365*24*60*60),8.4e+13(年),肖吱临撩典窝嘴阎陶厨抿棒冬躇贫励蔗即域歧色速帕唐次萝吹往皑跃南婿组合优化及算法组合优化及算法,计算复杂性的概念,多项式时间算法,构造算法的目的是能够解决问题（或至少是问题某个子类）的所有实例而不单单是某一个实例,问题（Problem）是需要回答的一般性提问，通常含有若干个满足一定条件的参数.问题通过下面的描述给定：（1）描述所有参数的特性，（2）描述答案所满足的条件.,问题中的参数赋予了具体值的例子称为实例(instance).,衡量一个算法的好坏通常是用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系来度量.计算模型,C(I)=f(d(I):该函数关系称为算法的计算复杂性（度）,伙平炮笋卓幻度筋类效侮绣置讽止巩茧笺先倚匈疏漳钨通责绥敌帮桨莉渝组合优化及算法组合优化及算法,计算复杂性的概念,多项式时间算法,例 构造算法将n个自然数从小到大排列起来,算法 输入自然数a(1),a(2),a(n).,for(i=1;in;i+),for(j=i+1;ja(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).,当不存在多项式函数g(x)使得上式成立时，称相应的算法是非多项式时间算法,或指数(时间)算法(Exponential time algorithm),输入规模增大时，多项式时间算法的基本计算总次数的增加速度相对较慢.,多项式时间算法,注：上面定义中，要求对该问题的任意一个实例均成立 ，,这种分析方法称为最坏性能分析（Worst-Case Analysis）,咕麓浚捍贷焉惊测伶约春夺迄踌什辐蚌挡冒啤妹填儿矩陇也粉苞峨侍胀器组合优化及算法组合优化及算法,1.4 计算复杂性的概念,1.4.2 多项式时间算法,近似值,n,10,100,1000,n,log,n,33,664,9966,n,2,100,10,4,10,6,n,3,1000,10,6,10,9,10,8,n,4,10,12,10,16,10,20,2,n,1024,1.27e3,1.05e30,10,n,10,10,10,100,10,1000,n,log,n,2079,1.93e1,7.89e29,n!,3628800,10,158,4e2567,霄浪煮负扶需评内俏节件团圆扁莫玻嘘惫啮勺沿盎懈款护犹爹汝筏抨蜒唯组合优化及算法组合优化及算法,计算复杂性的概念,多项式时间算法,算法复杂性研究中:常将算法的计算时间表示为：,问题中的简单而典型的参数(如网络优化中n,m),以及,问题中出现的数值(如弧上的权)的最大值(按绝对值)K等自变量的函数关系,如果算法运行时间的上界是m,n和K的多项式函数，则称相应的算法为伪多项式（Pseudopolynomial）（时间）算法，或拟多项式（时间）算法.,实际问题的输入规模/长度一定是m,n和logK的一个多项式函数.所以：,多项式算法等价于其运行时间的上界是m,n和logK的多项式函数.,特别地,如果运行时间的上界是m,n的多项式函数（即该多项式函数不包含logK）,则称相应的算法为强多项式(Strongly Polynomial)时间算法.,一般来说，伪多项式算法并不是多项式算法.,谊蛛桓赤议襄咨妻铣捞肛域豆澄抉途痒昆回牛执嚷扼箱卖宗辰液莹娶囤肌组合优化及算法组合优化及算法,计算复杂性的概念,TSP等许多问题至今没有找到多项式时间算法,但尚未证明其不存在,定义 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial).,同样道理,可以定义强多项式问题,伪多项式问题等.,TSP是否存在多项式时间算法?-这是21世纪数学和计算机科学的挑战性问题之一,多项式问题,蓖鸳毖敬逝摹钟探妹巴舀敢伯洞忠依于监奏塌拈走像剂究澎瑞蝶耗磅警弓组合优化及算法组合优化及算法,问题、实例与输入规模,评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入规模的关系：,问题,实例,TSP,问题中各参数:100个城市，城市间距离 已知.,背包问题,问题中各参数:4个物品，大小分别为4,3,2,2.价值分别为8,7,5,7.包的大小为6.,整数线性规划,问题中的,n,A,b,c,已知.,比多项式问题类可能更广泛的一个问题类是非确定多项式(Nondeterministic Polynomial，简记 NP)问题类,存在多项式算法的问题集合：多项式问题类（P）,存在多项式函数 g(x)满足上式时，算法为多项式算法,NP 类是通过判定问题引入的。,疟绰弗艰衰摘承统杨演抓庭昧蕾岁敲篷囤往纯祖丛婴予身币假滴力芋慑馋组合优化及算法组合优化及算法,对任何一个优化问题，可以考虑其三种形式：,最优化形式（原形：最优解）,计值形式（最优值）,判定形式（上界）,定义 如果一个问题的每一个实例只有“是”或“否”两种答案，则称这个问题为判定问题(Decision/recognition/feasibility problem).称有肯定答案的实例为“是”实例(yes-instance).称答案为“否”的实例为“否”实例或非“是”实例(no-instance).,判定问题-定义,例,线性规划问题,(LP),的判定形式,LP,判定问题：,给定一个实数值,z,，(LP)是否有可行解使其目标值不超过,z,？即：给定,z,，是否有,?,难度降低,就有效算法的存在性而言，通常认为三种形式等价！,轮贫浆迈桃食詹端幂煮艇缠提粪卜撕坛晨螺酪井嘘怔鸥匀魁伪杜妮呸贞烟组合优化及算法组合优化及算法,文字集,例 适定性问题(Satisfiability problem),在逻辑运算中，布尔变量x的取值只有两个：“真”(1)和“假”(0)，逻辑运算有“或（+）”，“与（）”和“非（）.,判定问题-例,存在真值分配的表达式称为适定的(可满足的),+,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,0,1,0,1,0,0,1,1,1,0,1,1,0,文字集的任意一个子集中各元素（布尔变量）的“或”运算组成一个句子,多个句子的“与”运算组成一个表达式，如,适定性问题：,给定布尔表达式 ，,（SAT）是适定的吗？,涯面愁纂股呢购卒调屋砚脑变许撮亲悸罩码定林卫守捣书蘑俺僧峪堂氨趟组合优化及算法组合优化及算法,判定问题-例,例 三精确覆盖(3-Exact Coveri