【摘要】 本文针对一类强NP-Complete问题近似算法的设计问题,提出一种通用的设计策略DPBD,它通过一局部近似算法而获得一全局近似算法,并保证精度在一定范围内.最后,本文将DPBD应用于一著名的NP难度问题:平面Covering问题,对方法的有效性给予了证实.更多还原

【Abstract】 The paper devises a general designing method DPBD for the approximation algorithm of a kind of NP-complete problems. DPBD can get a global approximation algorithm from a local one and keep the precision to a definite range. At last, DPBD has been used to solve planar covering problem, thus the effectiveness of the method is Verified.更多还原