文档介绍：第一章引论
在管理科学,计算机科学,分子物理学和生物学以及超大规椿
集成电路CVLSI设计、代码设计、国象处理和电子工程等科技领
域中,存在砻大量组合优化闰题。
,至今没有找到有效的多
项式时间算法,这些闰题已被证朋是NP容全问题..
用最优算法如线佐规划求NP完全问题的最优解,需要问愚
规模的指数阶时间,在问题规模增大时,往往由于计算时间的除制
而丧失可行性。用近似算法如货心法求解NP完全问题,在多项
式界的时间里,只能给出近似最优解.
本章介绍组合优化问题和计算复杂佐理论的基本概念,并结
合几个纬合优化的NP完全问题实例,介绍其近似算法。最后,
在引入邻域结构概念的基础上,介绍一种通用的近似算法一一局
部搜索算法
$1组合优化问题
组合优化问题的日标是从组合问题的可行解枝中汪出最优
解,本书研究那些可以用数学语言精确掩述的组合优化问题,并
铁定其可行解集是有限的或可数无限的,同时解的质量可以量化,
医而可以比较不同解间的质量銮异.
优化问题有三个基本嫦索变量、约束和一标函数。在求解
过程中选定的基本参数称为变量,对变量取值的种种限制称为约
根,袁示可行方案衡量标准的函数称为目标函数.
货郎抱问题CTSP是组从优化中最为羟名的问题,它易于
陈述而准于求解。自1932年K,Menger提出以来,巳引起许多
数学家的兴超,但至今崴木找到有效的欢解方法,田于质郎担合
颐综合了一大类组合优化问题的典型特征,下面以它为例说阮绍
合优化问题的基本概念.
给定n个城市和每两个姚市佐的贸离。一个质郑自栋一坡市
出发巡团售货,问这个货郎应试如何选择路线,使每个垣市经过一
次且仅一次,押昆路径长度最短。
设九一dy是阶离矩阵,其元宋di表示绕市i问的贸
离。则对变量卫的约束是
1每个元紧是非负整数,即
d乐0,【医视忠户
2对角线上的元素为0,即
d一0工余医所
3是对称短阵,即
牵一d工医许怀吊
47任感三个元索满足三角不等式,即
a十的t交d工医门江命n
TSP的一个解可表述为一个循环排列
一口Comoomoor
它习可裘示为
英
的一条路径,r1二;二是该路径中第i个经过的垣市。盂
然,漪足
动氙a萱王
的解才是司行解。所有可行解的林合构或解空间5,即
5一fr个城市的所有循环排列}
fCm一童nix约定roui心口
1
是货郎担问题的目标函数、TSP的日标是使路径长度最短,即仰
目标颊数fCz最小。
下面给出组合优化问题的定义
,求目标函教
最优值最小值或最大值的问题,组合优化问题的一个实例可以
表示为一个对假8,行,其中解空间S为可行解集,目标园数}
是一个晁艇,定义为
才5一、
求目标函数鬓小与的问题称为最小化问题,记为
minf日,83ClL0
求目标丽数最大惠的问题称为最大化问题,记为
maxf门,165。CLL2
明然,只如改变目标函数的符号,最小化问题与最大化问题就
可以等价转捣.
使目标函数取最优值的解秘为最优解整体最优解,定义
为
,行是级合优化问题的一个实例,in65.
称i为最小化问题
miaf门,i65
的最优解,若
fCioo二闯,对所有565吴立.
在组合优化问题的近似算法中,沐要渥及邹域和局部最优需
的概念,我们将在53中定义.
!背包问题
一个旅行者要从n种物品中选取8公斤重的物品,每种物启
,使所选物品的总价值暨
0沥沥
大.
设第;种物品的雨最为w,价值为c;1,2,n则
闭题是
mars一文c
吊刀w
一口英第1租物品木选上
一u香则.
例13最大戴间题
设G一CV,8是一个无向国,现把顶点集7分划为两个子
集V和7一7NVe,使G中那些端点分别在P与I中的边
集有最大的权和.
设Vo,,wCtw,o}表示边t0的权,
则问题是
maxiVayD一。一t
fn
st8CVo7心{史E五1EP人5E
设C是一个无环图,对G的每个顶点着色,使任意两个相邹的
顶点都有不同的颜色,要求所用颜色数最少.
图G一Y,E中着同一种额色的顶点集是G的一个狱立
,V7,...,Yu则G
是人可着色的。医此图着色问题等价于找一个映射扎P一{1,
2,...,吊。设A是G的最大度数,XCG是G的色数使G最伐
获色的额色数则问题是
min无,双G余叶心乃十
tY5一P史一丁二多扬的的才07
5浩
$2计算复杂性与NP完全问题
算法