近似算法.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