第10章近似算法
绝对近似算法
相对近似算法:常数近似比
相对近似算法:函数近似比
相对近似算法:任意近似比
近似算法
NP完全问题:很难在短时间内求出问题的精确解
折衷策略:在可接受的时间内求出问题的近似解
绝对近似算法
平面图着色问题
输入:一个平面图G = <V, E>
输出:对该图进行着色所需的最小色数k
a
b
c
d
e
f
绝对近似算法
平面图着色问题
算法:每次尽可能选取最小的颜色对当前顶点着色
a
b
c
d
e
f
不保证最优
绝对近似算法
平面图着色问题
算法:每次尽可能选取最小的颜色对当前顶点着色
k−k* ≤ 3
a
b
c
d
e
f
绝对近似算法
设最优化问题的最优目标函数值为y*,而近似算法得到的目标函数值y满足下式|y−y*| ≤ c,其中c为一个常数,则称该近似算法是一个误差不大于c的绝对近似算法
相对近似算法: 常数近似比
设最优(小)化问题的最优目标函数值为y*,而近似算法得到的目标函数值y满足y/y*≤ρ,则称算法的近似比为ρ
相对近似算法: 常数近似比
设最优(大)化问题的最优目标函数值为y*,而近似算法得到的目标函数值y满足y*/y≤ρ,则称算法的近似比为ρ
算法设计（第10章近似算法）[精] 来自淘豆网m.daumloan.com转载请标明出处.
