组合优化（1）

《组合优化（1）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、近代数学选讲（２）：ＮＰ－难组合优化问题近似算法导论王卫Email:wang_weiw@163.comCellphone:13359292807理科楼327本课程主要内容一些经典的NP-难组合优化问题及它们的近似算法设计。设计近似算法的常用技巧和方法。近似算法在无线传感起网络中的应用。主要参考文献：D.S.Hochbaum(eds),ApproximationAlgorithmsforNP-hardProblems,世界图书出版社（影印），1995V.V.Vazirani，ApproximationAlgorithm

2、s,Springer,2002.D.Z.Du,Ker.I.Ko,X.D.Hu,DesignandAnalysisofApproximationAlgorithms,Lecturenotes.越民义，组合优化导论，浙江科学技术出版社。引言什么是组合最优化（CombinatorialOptimization)？什么是“好的”算法？有“好算法”的组合优化的例子。什么是P，NP？什么是NPC，NP-hard？什么是近似算法？几个经典的近似算法例子。引言“芝麻”开门：阿里巴巴来到一个装满宝石的山洞里，每个宝石都有标有一定价值和

3、体积，但他随身只带着一个口袋,问他如何装才能使得带走的宝石价值最大？背包问题（Knapsack）：给定ｎ件物品　　　　　　，其体积与价值各为　　和　，背包的体积为Ｓ。引入０－１变量数学描述：组合优化的例子公路连接问题：某地区有若干主要城市，现在要修建一些高速公路将它们连起来，使得从任一城市可经过高速公路直接或间接地到达另一城市。假定已经知道任两城市间修建成本，那么如何修建高速公路网，才能使得总的成本最小？最短路问题（shortestpathproblem）：一名货运司机要把货物从甲地运往加乙地，从甲地到乙地公路从横交

4、错，那么如何选择行走路线，才能最快将货物运到目的地呢？指派问题（AssignmentProblem）：一个公司有N个职员，有N项工作需要去做，每人做一项工作。假定每个员工i做每项工作j产生的效益wij，那么如何安排，才能使得公司产生的总的效益最大？j1j2j3j5j4p2p1p5p3p4旅行商问题（TravelingSalesmanProblem,TSP):一名销售员要到若干个城市去洽谈业务，已知任两个城市之间的距离，请为其设计一个旅行线路，使得他从某一城市出发恰好经过每个城市一次，最后回到出发城市。要求所走的路线最

5、短。顶点覆盖问题（vertexcover）：给定图G=（V，E），找顶点数最少的V的子集C，使得E中每条边至少与C中一个顶点相邻。组合优化问题的共同特点它们的研究的对象是离散的，研究目标一般都是从有限个可能的方案中寻求某种最优安排或方案。。除了背包问题外，其余都可用图来描述。与图有关的组合优化问题，一般称为网络优化。由于所有可能的方案都有限，当然可以用枚举方法。但当问题规模较大时，枚举法需要的计算量太大。因此，我们需要设计“好”的算法。优化问题/具体实例一个优化问题的实例（instance）：是一个pair（F，c）

6、，其中F是可行点组成的任何集合；c是费用函数我们的问题是找到一个使得组合优化问题：由所有实例组成的集合。通俗地讲，实例是某一个输入数据，譬如对于背包问题，是背包的容量，以及所有宝石的价值和体积。背包问题就是要求对所有的输入实例给出其一个统一的算法；而不是对于一组特定的输入数据，计算出一个结果。什么是算法及好算法如何为各种组合优化问题设计好的算法是最优化领域需要研究的核心问题。算法：对于优化问题的任一个实例I，经过一个计算过程A（I）得到问题的最优解，OPT.算法好坏的衡量标准：计算时间（时间复杂性），占用内存（空间复

7、杂性）时间复杂性输入问题的规模,通常用二进制位数表示。背包问题中宝石数n；高速公路连接问题中的城市数；最短路问题、旅行商问题中输入图的阶。时间复杂性：由于计算机运行速度不一致，用表示对于输入规模为n的一个实例，算法A需要进行的基本操作步数。以来衡量时间复杂性。不同的计算时间比较时间303003000234606907630398,10710243628800假定计算机每秒运算1百万次。多项式时间算法如果算法A，对于任一规模为n的实例，其基本操作步骤被一个多项式所界定，即则称算法A是一个多项式时间算法。和都是多项式时间

8、算法。可以看出，计算时间按多项式时间增长的算法是“好”算法。在实践中，的值不超过3，则算法对大规模问题（n超过10000）有效的。在多项式时间可解的组合优化问题最小生成树问题（MinimumSpanningTree）给定一个图G=（V，E）每条边有权值求G的一个总权重最小的生成树。Kruskal算法：该算法时间复杂性为：O（mn）=O（n^3)