.算法设计与第11章近似算法.ppt

第十一章近似算法
1
2
3
4
概述
图问题中的近似算法
组合问题中的近似算法
小结
概述——设计思想
近似算法是解决难解问题的一种有效策略,其基本思想是放弃求最优解,用近似最优解代替最优解,以换取算法设计上的简化和时间复杂性的降低。
近似算法找到的可能不是一个最优解,但它总会为待求解的问题提供一个解。为了具有实用性,近似算法必须能够给出算法所产生的解与最优解之间的差别,以保证任意一个实例的近似最优解与最优解之间相差的程度。显然,这个差别越小,近似算法越具有实用性。
一个简单的例子—求π的近似值
【问题】请用正多边形逼近法求π的近似值。
【想法】 用圆内接正多边形的边长和半径之间的关系,不断将边数翻倍并求出边长,重复这一过程,正多边形的边长就逐渐逼近圆的周长,只要圆内接正多边形的边数足够多,就可以求得所需精度的π值。
一个简单的例子—求π的近似值
简单起见,设单位圆的半径是1,则单位圆的圆周长是2×π,设单位圆内接正i边形的边长为2b,边数加倍后正2i边形的边长为x,则:
问题描述:无向图G=(V, E)的顶点覆盖是顶点集V的一个子集V 'V,使得若(u, v)是G的一条边,则v∈V'或u∈V'。顶点覆盖问题是求出图G中的最小顶点覆盖,即含有顶点数最少的顶点覆盖。
图问题中的近似算法—顶点覆盖问题
采用策略:初始时边集E'=E,顶点集V'={ },每次从边集E'中任取一条边(u, v),把顶点u和v加入到顶点集V'中,再把与u和v顶点相邻接的所有边从边集E'中删除,重复上述过程,直到边集E'为空,最后得到的顶点集V'是无向图的一个顶点覆盖。由于每次把尽量多的相邻边从边集E'中删除,可以期望V'中的顶点数尽量少,但不能保证V'中的顶点数最少。
顶点覆盖问题是一个NP难问题,目前尚未找到一个多项式时间算法。虽然要找到图G的一个最小顶点覆盖很困难,但要找到图G的一个近似最小覆盖却很容易。
顶点覆盖问题——想法
顶点覆盖问题——实例
a
b
c
e
d
f
g
a
b
c
e
d
f
g
a
b
c
e
d
f
g
(a) 一个无向图(b) V '={a, b} (c) V '={a, b, c, f}
删除与a或b相关联的边删除与c或f相关联的边
a
b
c
e
d
f
g
a
b
c
e
d
f
g
a
b
c
e
d
f
g
(d) V '={a, b, c, f, d, e} (e) 近似最小顶点覆盖(f) 最小顶点覆盖
删除与d或e相关联的边 V '={a, b, c, f, d, e} V '={a, b, c, e}
顶点覆盖问题——算法
1. 初始化:x[n] = {0};
2. E' = E;
3. 循环直到E'为空
从E'中任取一条边(u, v);
将顶点u和v加入顶点覆盖中:x[u] = 1;
x[v] = 1;
从E'中删去与u和v相关联的所有边;
图问题中的近似算法—TSP问题
问题描述:TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。
TSP问题——想法
如果无向图G=(V, E)的顶点在一个平面上,边(i, j)∈E的代价cij均为非负整数,且两个顶点之间的距离为欧几里德距离,则对图G的任意3个顶点i, j, k∈V,显然满足如下三角不等式:cij+cjk≥cik