算法设计与分析W10-近似算法

VIP免费
2025-01-13 0 0 1.31MB 90 页 5.9玖币
侵权投诉
近似算法
Approximation Algorithms
“In particular, when a problem is computationally hard (i.e.,
the only way we know to solve it is by making use of an
algorithm that runs in exponential time), it may be practically
unfeasible to try to compute the exact solution, because it might
require months or years of machine time, even with the help of
powerful parallel computers. In such cases, we may decide to
restrict ourselves to compute a solution that, though not being an
optimal one, nevertheless is close to the optimum and may be
determined in polynomial time.We call this type of solution an
approximate solution and the corresponding algorithm a
polynomial-time approximation algorithm.”
2
Ausiello, Crescenzi, Gambosi, etc. Complexity and Approximation: Combinatorial
Optimization Problems and Their Approximability Properties. 1999
参考书籍
[1] Ausiello, Crescenzi, Gambosi, etc. Complexity and Approximation:
Combinatorial Optimization Problems and Their Approximability Properties. 1999
[2] Hochbaum (Editor) . Approximation Algorithms for NP-Hard Problems. 1997
[3] Vijay V. Vazirani. Approximation Algorithms. 2001
[4] D.P. Williamson & D.B. Shmoys. The Design of Approximation Algorithms.
2010
[5] D.Z Du, K-I. Ko & X.D. Hu. Design and Analysis of Approximation
Algorithms. 2012 3
主要内容
u
优化问题的基本概念
u
近似算法的基本概念
u
近似算法的设计方法
u
近似类
u
近似保持的归约
u
解非线性方程的算法
4
优化问题的基本概念
u
优化问题
u
可行解与最优解
u
优化问题与对应的判定问题
u
优化问题的难度：
PO
类与
NPO
类
5
优化问题
u
一个优化问题
Q
可表示为四元组
:
( IP , SOLQ , mQ , goalQ )
其中，
–IQ
是问题
Q
的实例集合；
– SOLQ
是一个函数：对于每个实例
x
Î
IQ
，生成
x
的可行解集合
SOLQ(x)
；
–mQ
是一个评估函数：对于每个二元组
(x, y)
，其
中
x
Î
IQ , y
Î
SOLQP(x)
，
mQ(x, y)
为可行解
y
的值
–goalQ
Î
{MAX, MIN}
，表示
Q
是一个最大优化问
题或最小优化问题
6
举例：最小顶点覆盖问题
（
Minimum Vertex Cover
）
u
实例
:
无向图
G = (V, E)
u
可行解
(
顶点覆盖
):
图
G
的顶点子集
U
Í
V,
使得
"
(vi,vj)
Î
E, vi
Î
U
或者
vj
Î
U
7
V
是一个顶点覆盖
举例：最小顶点覆盖问题
（
Minimum Vertex Cover
）
u
实例
:
无向图
G = (V, E)
u
可行解
(
顶点覆盖
):
图
G
的顶点子集
U
Í
V,
使得
"
(vi,vj)
Î
E, vi
Î
U
或者
vj
Î
U
V
是一个顶点覆盖
{u, v, x, y, z}
是一个顶点覆盖
8
举例：最小顶点覆盖问题
（
Minimum Vertex Cover
）
u
实例
:
无向图
G = (V, E)
u
可行解
(
顶点覆盖
):
图
G
的顶点子集
U
Í
V,
使得
"
(vi,vj)
Î
E, vi
Î
U
或者
vj
Î
U
V
是一个顶点覆盖
{u, v, x, y, z}
是一个顶点覆盖
{u, v, y, z}
是一个顶点覆盖
9
举例：最小顶点覆盖问题
（
Minimum Vertex Cover
）
u
实例
:
无向图
G = (V, E)
u
可行解
(
顶点覆盖
):
图
G
的顶点子集
U
Í
V,
使得
"
(vi,vj)
Î
E, vi
Î
U
或者
vj
Î
U
V
是一个顶点覆盖
{u, v, x, y, z}
是一个顶点覆盖
{u, v, y, z}
是一个顶点覆盖
{u, v, x, y}
是一个顶点覆盖
?
10
摘要：

近似算法ApproximationAlgorithms“Inparticular,whenaproblemiscomputationallyhard(i.e.,theonlywayweknowtosolveitisbymakinguseofanalgorithmthatrunsinexponentialtime),itmaybepracticallyunfeasibletotrytocomputetheexactsolution,becauseitmightrequiremonthsoryearsofmachinetime,evenwiththehelpofpowerfulparallelco...

展开>> 收起<<
算法设计与分析W10-近似算法.pdf

共90页,预览18页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：计算机 价格：5.9玖币 属性：90 页 大小：1.31MB 格式：PDF 时间：2025-01-13

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 配电装置 动力学连接体 力的合成 高考理综 全宋诗作者索引 公务员考试
/ 90
评分 收藏
分享
立即下载 VIP免费下载
客服
关注