刘建华组合优化问题简介.doc

《刘建华组合优化问题简介.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路(VLSI)设计、代码设计、图象处理和电子工程等科技领域中，存在着大量组合优化问题。其中许多问题如货郎担问题、图着色问题、设备布局问题以及布线问题等，至今没有找到有效的多项式时间算法。这些问题巳被证明是NP完全问题[1]。用最优算法如线性规划求NP完全间题的最优解，需要问题规模的指数阶时间，在问题规模增大时，往往由于计算时间的限制而丧失可行性。用近似算法如贪心法求解NP完全问题，在多项式界的时间里，只能给出近似最优解。本章介绍组合优化问题和计算复杂性理论的基本概念，并结合几个组合优化的NP完全问题实例

2、，介绍其近似算法。最后，在引人邻域结构概念的基础上，介绍一种通用的近似算法—局部搜索算法。§1组合优化问题组合优化问题的目标是从组合问题的可行解集中求出最优解。本书研究那些可以用数学语言精确描述的组合优化问题，并假定其可行解集是有限的或可数无限的，同时解的质量可以量化，因而可以比较不同解间的质量差异。1.1组合优化问题的基本概念优化问题有三个基本要素:变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。货郎担问题(TSP)是组合优化中最为著名的问题，它易于陈述而难于求解。自1932年K.

3、Menger提出以来，已引起许多数学家的兴趣，但至今尚未找到有效的求解方法。由于货郎担问题综合了一大类组合优化问题的典型特征，下面以它为例说明组合优化间题的基本概念。例1.1货郎担问题(TSP)给定n个城市和每两个城市间的距离。一个货郎自某一城市出发巡回售货，问这个货郎应该如何选择路线，使每个城市经过一次且仅一次，并且路径长度最短。设是距离矩阵，其元素表示城市间的距离。则对变量D的约束是：(1)每个元素是非负整数，即;(2)对角线上的元素为0，即;(3)是对称矩阵，即;(4)任愈三个元素满足三角不等式，即;TSP的一个解可表述为一个循环排列，它也可表示为.的一条

4、路径，是该路径中第i个经过的城市。显然，满足，若的解才是可行解。所有可行解的集合构成解空间S，即S={n个城市的所有循环排列},解空间的规模为。路径长度（约定）是货郎担问题的目标函数。TSP的目标是使路径长度最短，即使目标函数最小。下面给出组合优化问题的定义。定义1.1组合优化问题是在给定的约束条件下，求目标函数最优值(最小值或最大值)的问题。组合优化问题的一个实例可以表示为一个对偶(S,f)，其中解空间S为可行解集，目标函数f是一个映射，定义为.求目标函数最小值的问题称为最小化向题，记为；（1.1.1）求目标函数最大值的同题称为最大化间题，记为(1.1.2)显

5、然，只要改变目标函数的符号，最小化问题与最大化问题就可以等价转换。使目标函数取最优值的解称为最优解(整体最优解)，定义为:定义1.2设(S,f)是组合优化问题的一个实例，。称为最小化问题的最优解，若，对所有成立.在组合优化间题的近似算法中，还要涉及邻域和局部最优解的概念，我们将在§3中定义。1.2几个组合优化问题的数学描述例1.20一1背包问题一个旅行者要从n种物品中选取b公斤重的物品，每种物品至多选一件。问这个旅行者应该怎样选取，使所选物品的总价值最大。设第种物品的重量为，价值为，。则问题是,,，s.t右边的式子是约束条件(下同)。例1.3最大截问题设G一(V

6、,E)是一个无向图，现把顶点集V分划为两个子集和,使G中那些端点分别在与中的边集有最大的权和。设是一个分划，表示边的权，则问题是，。例1.4图着色问题设G是一个无环图，对G的每个顶点着色，使任意两个相邻的顶点都有不同的颜色，要求所用颜色数最少。图G=(V,E)中着同一种颜色的顶点集是G的一个独立集。若G的顶点集V可划分为k个独立集，则G是k可着色的。因此图着色问题等价于找一个映射。设△是G的最大度数，X(G)是G的色数(使G最优着色的颜色数)，则问题是，。§2计算复杂性与NP完全问题算法可解问题在实践中不一定是可解的，因为求解该问题的算法可能需要极长的运行时间与

7、极大的存贮空间，以至根本不可能在现有计算机上实现。算法对时间和空间的需要量称为算法的时间复杂性和空间复杂性。问题的时间复杂性是指求解该问题的所有算法中时间复杂性最小的算法的时间复杂性。类似地，可以定义问题的空间复杂性。按照计算复杂性理论研究问题求解的难易性，可把问题分为P类、NP类和NP完全类[2]。2.1计算盆杂性的甚本概念算法或问题的复杂性一般是问题规模n的函数，时间复杂性记为T(n)，空间复杂性记为S(n)。货郎担问题中的城市数、0-1背包问题中的物品数以及最大截问题和图着色问题中图的顶点数或边数都是刻划问题规模的特征数。在算法分析和设计中，沿用实用性的复

8、杂性概念，即把求解问题的