《组合优化（1.1）》由会员分享，可在线阅读，更多相关《组合优化（1.1）（44页珍藏版）》请在金锄头文库上搜索。
1、近代数学选讲（）：难近代数学选讲（）：难 组合优化问题近似算法导论组合优化问题近似算法导论王卫Email: wang_Cell phone: 13359292807 理科楼327本课程主要内容本课程主要内容一些经典的NP-难组合优化问题及它们的近似算 法设计。设计近似算法的常用技巧和方法。近似算法在无线传感起网络中的应用。主要参考文献：主要参考文献：D. S. Hochbaum (eds) , Approximation Algorithms for NP-hard Problems, 世界图书 出版社（影印），1995V. V. Vazirani，Approximation Algorith
2、ms, Springer, 2002.D.Z. Du, Ker.I. Ko, X.D. Hu, Design and Analysis of Approximation Algorithms, Lecture notes.越民义，组合优化导论，浙江科学技术出版社。引言引言什么是组合最优化（Combinatorial Optimization) ？什么是“好的”算法？有“好算法”的组合优化的例子。什么是P， NP？什么是NPC，NP-hard？什么是近似算法？ 几个经典的近似算法例子。引言引言“芝麻”开门：阿里巴巴来到一个装满宝石的山洞 里，每个宝石都有标有一定价值和体积，但他随 身只带着一个口
3、袋,问他如何装才能使得带走的宝 石价值最大？背包问题（Knapsack ）：给定件物品 ，其体积与价值各为 和 ，背包的体积为 。引入变量数学描述：组合优化的例子组合优化的例子公路连接问题：某地区有若干主要城市，现在要 修建一些高速公路将它们连起来，使得从任一城 市可经过高速公路直接或间接地到达另一城市。假定已经知道任两城市间修建成本，那么如何修 建高速公路网，才能使得总的成本最小？最短路问题（shortest path problem）：一名货运司机要把货物从甲地运往加乙地，从甲 地到乙地公路从横交错，那么如何选择行走路线 ，才能最快将货物运到目的地呢？指派问题（Assignment Pro
4、blem）：一个公司 有N个职员，有N 项工作需要去做，每人做一项 工作。假定每个员工i做每项工作j产生的效益wij ，那么如何安排，才能使得公司产生的总的效益 最大？旅行商问题（Traveling Salesman Problem, TSP) :一名销售员要到若干个城市去洽谈业务，已知任两个城市之间的距离，请为其设计一个旅 行线路，使得他从某一城市出发恰好经过每个城 市一次，最后回到出发城市。要求所走的路线最 短。 顶点覆盖问题（vertex cover）：给定图G=（ V，E），找顶点数最少的V的子集C， 使得E中 每条边至少与C中一个顶点相邻。组合优化问题的共同特点组合优化问题的共同特点
5、它们的研究的对象是离散的，研究目标一般都是 从有限个可能的方案中寻求某种最优安排或方案 。除了背包问题外，其余都可用图来描述。与图有 关的组合优化问题，一般称为网络优化。由于所有可能的方案都有限，当然可以用枚举方 法。但当问题规模较大时，枚举法需要的计算量 太大。因此，我们需要设计“好”的算法。优化问题优化问题/ /具体实例具体实例一个优化问题的实例（instance）：是一个pair（F，c），其中F是可行点组成的任何集合；c是 费用函数我们的问题是找到一个 使得组合优化问题： 由所有实例组成的集合。通俗地讲，实例是某一个输入数据，譬如对于背 包问题，是背包的容量，以及所有宝石的价值和 体积
6、。背包问题就是要求对所有的输入实例给出其一个 统一的算法；而不是对于一组特定的输入数据， 计算出一个结果。 什么是算法及好算法什么是算法及好算法如何为各种组合优化问题设计好的算法是最优化 领域需要研究的核心问题。算法： 对于优化问题的任一个实例I， 经过一个 计算过程A（I）得到问题的最优解，OPT.算法好坏的衡量标准： 计算时间（时间复杂性） ， 占用内存（空间复杂性）时间复杂性时间复杂性输入问题的规模。背包问题中宝石数n；高速公 路连接问题中的城市数； 最短路问题、旅行商问 题中输入图的阶。时间复杂性：由于计算机运行速度不一致，用表示对于输入规模为n 的一个实例，算法A 需要 进行的基本操
7、作步数。以 来衡量时间复杂性。不同不同 的计算时间比较的计算时间比较时间303003000234606907630398,10710243628800多项式时间算法多项式时间算法如果算法A， 对于任一规模为n的实例，其基本 操作步骤 被一个多项式所界定，即则称算法A是一个多项式时间算法。 和 都是多项式时间算法。可以看出，计算时间按多项式时间增长的算法是“ 好”算法。在实践中， 的值不超过3，则算法对大规模问 题（n超过10000）有效的。在多项式时间可解的组合优化问题在多项式时间可解的组合优化问题最小生成树问题（Minimum Spanning Tree）给定一个图G=（V，E）每条边有权值
8、求G的一个总权重最小的生成树。Kruskal算法：该算法时间复杂性为：O（mn）=O（n3)高速公路连接问题本质上就是求最小生成树。求最小生成树的例子求最小生成树的例子其他多项式时间可解的问题其他多项式时间可解的问题(P(P问题问题) )一个图中任意两点距离的 Dijkstra算法；指派问题（赋权匹配问题）Kuhn算法；最大流-最小割（Max flow-Min cut), Ford and Fulkerson算法TSP, Knapsack及Vertex-Cover 是P问题吗?七个千禧难题七个千禧难题Riemann Hypothesis ;Poincares Conjecture;（已由Per
9、elman解决）P vs NP;Navier- Stokes Equation;Yang-Mills Theory;Hodge Conjecture;Birch and Swinnerton-Dyer (BSD ) Conjecture上述问题是21 世纪最具挑战性的问题7个问题之 一,美国Clay Mathematics Institute为每个问 题的第一个正确解决者奖励1，000，000美元。NP,NP, NPC,NP-NPC,NP-难问题难问题 P 代表多项式时间可解得问题,那么,NP代表什么 呢?NP,NP, NPC,NP-NPC,NP-难问题难问题NP不是非多项式时间可解,其准确含
10、义是可在一 种假想的机器非确定型Turing机上在多项式时 件可以检验的问题. 通俗地将讲,有这么一大类问题,譬如给你个方程, 你要求解它很困难,但有人告诉你,他得到了方程 的解, 则通常你很容易验证他的对错.NP问题是在 多项式时间可以检验的问题.NP,NP, NPC,NP-NPC,NP-难问题难问题显然 ,但 吗?1970年左右,Cook发现了一些组合优化问题可在 多项式时间内相互转化,如果其中一个是P问题,那 么其他问题也属于P问题,反之亦然. 这其中就包括TSP, Knapsack问题,目前已证明 有几千个组合优化问题包含在其中。 人们无法为这些问题找到好的算法，从而证明其 属于P；又
11、无法证明其不属于。这些NP问题统 称为完全问题。难问题虽不属于， 但其至少与 问题一样难解！一些经典的一些经典的NPCNPC问题问题TSP；Knapsack；顶点覆盖；集合覆盖；Hamilton 回路；最小控制集问题（Dominating Set）；最大独立集（maximum independent set)；最大团（maximum clique）；着色数；整数规划；NP-NP-难问题的近似算法难问题的近似算法如果 不利因素是，则现代社会依赖的网上银行、网上 交易等密码系统随即崩溃；积极的方面是，大量的组合优化问题可找到好的 算法，对人们生产、生活的影响将不可估量。数 学定理的证明也将可由计算
12、机来完成。尽管人们目前尚不能证明 ，但人们普遍 倾向于认为认为这是成立的。那么既然 ，那么退而求其次的话，如何为 NP-难组合优化问题设计多项式时间 的近似算法 （Approximation Algorithms）就成为当前组 合优化及理论计算机领域研究的一个重要课题。近似比近似比近似算法的好坏通常由近似比（performance ratio， performance guarantee，worst- case ratio）来衡量。对于最小值问题，近似比定义为：其中上确界对所有实例来取。若近似比为则 对任何实例I都成立 。 总是大于 或等于1，越接近于1，近似效果越好。 对于最大值问题，近似比
13、定义为对任何实例，总有近似算法按近似比的分类近似算法按近似比的分类常数倍近似算法：存在一个常数c，使得对任意 实例I，有多项式时间近似方案（Polynomial Time Approximation Scheme, PTAS):对于 ，存在一个多项式时间近似算法 ，使得对任意 实例I，有全多项式时间近似方案（FPTAS）：如果进一步 ，如果在上式中多项式时间仅依赖于输入的大小 和 ，则称其为FPTAS。几个经典问题的近似算法设计几个经典问题的近似算法设计背包问题的近似算法；顶点覆盖（vertex cover）的近似算法。带度量的TSP的近似算法；背包问题的贪婪算法背包问题的贪婪算法注：注：1
14、1。最上面第一个不等式，。最上面第一个不等式，trivialtrivial；2 2。最上面第二个不等式可以这样考虑：假定宝石可以。最上面第二个不等式可以这样考虑：假定宝石可以 切割，则最优策略显然是先装入前面切割，则最优策略显然是先装入前面k k个宝石，再个宝石，再 将第将第 k+1k+1个宝石切一部分装入；因此，不允许切割个宝石切一部分装入；因此，不允许切割 得得 到到 的的 最优解不超过不等式最右端。最优解不超过不等式最右端。顶点覆盖问题近似算法顶点覆盖问题近似算法定义：G的边子集M成为一个匹配（matching） ，如果其中任两条边无公共顶点； 称为极大匹配 ，如果加入E-M中任一边点，
15、其变得不再是匹配 。找图G的一个极大匹配M， 令C为M中边的顶点 组成的集合，则C是G的一个顶点覆盖，且算法分析算法分析首先说明C是G的顶点覆盖。若否，则存在G的一 条边e=uv没有被C覆盖，则u，v都不属于C。这 样e与M中的边都是独立的，M添加进e 后仍是匹 配，矛盾！令最优解为 ，由于M中任一边的两个端点中 至少有一个属于 为最优解，因此，我们有：满足三角不等式的满足三角不等式的TSPTSP假定图G中任两点距离满足三角不等式：则用最小生成树（MST)可给出TSP的2-近似算 法。A AA A算法分析算法分析令MST，OPT分别表示最小生成树及最优TSP的 长度。则另外，近似算法得到的近似解A不超过中 所有边的倍（三角不等式）。因此的近似比的近似比Christofids (1976)得到了.5近似算法。Christofids (1976)得到了.5近似算法。A AA A算法分析算法分析算法分析算法分析ChristofideChristofide算法
