近似算法.ppt

近似算法(ApproximationAlgorithms)倘纶灼守三乌矗甭综氖联挨长氨盂贴蔓夕青确飘茎龙劳鲁媒右琴狼您牢獭近似算法近似算法1现在我们只考虑最优化问题。一些困难的组合优化问题没有有效的解决方案,在这种情况下,对于其中的一些问题代之以设计近似算法,我们要保证它是近似于最优解的一个“合理”的解。每个近似解都有一个性能界,它保证任一个实例的近似解与精确解不会相差太多。大多数近似算法的一个显著特点是它们非常快,这是因为它们绝大多数是贪心启发式的算法。然而要找一个有效的近似算法也并不乐观,甚至存在一些困难问题,似乎连“合理”的近似算法都可能不存在,除非NP=P。筹闭肪鼓添烟蹿事萤挪阂颂叭日搏轨庐讶畏蚤驼寒培眶御伯壶驼蹲畦提假近似算法近似算法2组合优化问题Π是一个最大(或最小)化问题。它由三部分组成:(1)一个实例的集合DΠ;(2)对每个实例I∈DΠ,存在I的一个候选解的有限集合SΠ(I);(3)对DΠ中的一个实例I的每个候选解σ∈SΠ(I),存在一个值fΠ(σ),称为σ的解值。牵胞味禽堕骡涸钥卞诗报叛阑罕拾菠罐菩适催旧淄氓悔识忘贝菩孟葡智帧近似算法近似算法3如果Π是一个最小化问题,那么实例I的最优解σ*满足:对于所有σ∈SΠ(I),fΠ(σ*)≤fΠ(σ)最大化问题的最优解类似定义。我们统一用OPT(I)表示最优解的值。活懂过尉被一旺钱捎锑辞兵砍杀哆穴亮污瞎固敛黑式姨心俭危域蔚韦阶睹近似算法近似算法4差界(absoluteapproximation)设A是问题Π的一个近似算法,如果对的任何实例I,都有:其中K是常数,则我们称A是问题Π的一个差界为K的近似算法。,如果对的任何实例I,都有:其中是常数,则我们称A是问题Π的一个近似度为k的近似算法,或k近似算法(k-factorapproximationalgorithm;kisthe“performanceratio/guarantee”.)差界是所有近似算法中性能最好的,然而,只有很少的困难问题存在这样的界。相对性能界(k-factorapproximation)腔熟影祝沙肥犊袜即忽瓤糜赘涌灾月链沮午奔瞩酚毫稚纽销羽泻檄雄恨胆近似算法近似算法6设A是问题Π的一个近似算法,如果对Π的任何实例I,都有:其中k,c是常数,则我们称A是问题Π的一个渐近近似度为k的近似算法(asymptotick-factorapproximationalgorithm;k---asymptoticperformanceratio.)。渐近的相对性能界(asymptotick-factorapproximation)火柞撰罩洱珍蝶惠妓勿消沦括雄杖敖潍骨劲律档霄莹碉冶柬踊焕颗捧痪社近似算法近似算法7不少问题具有带相对近似度的近似算法,对某些问题,渐近近似度比(非渐近)近似度更合适,对另一些问题,两种近似度均可用。The(asymptotic)approximationratioofanoptimizationproblemΠwithnonnegativeweightsisdefinedtobetheinfimumofallnumberskforwhichthereexistsan(asymptotic)k-factorapproximationalgorithmforΠ,or∞ifthereisno(asymptotic)(渐近)eptingasinputaninstanceIofΠandanε>0suchthat,foreachfixedε,Aisa(1+ε)-(approximationscheme)隔汁人凤雨谣眶乍未汗蕊讳坎边跃吨鼓洁息阜蔼灵百究女臂苍心雀紊酪照近似算法近似算法9AnasymptoticapproximationschemeforΠisapairofalgorithms(A,A’),whereA’isapolynomial-eptinganumberε>putinganumbercε;eptsaninstanceIofΠandanε>0asinput,anditsoutputconsistsofafeasiblesolutionforIsatisfyingForeachfixedε,therunningtimeofAisbounded