精选优质文档-倾情为你奉上近似算法和概率算法的特点与计算方法、分类及概率算法的计算过程与应用一 近似算法1近似算法的计算方法设D是一个最优化问题，A是一个算法，若把A用于D的任何一个实例 I，都能在|I|的多项式时间内得到I的可行解，则称算法A为问题D的一个近似算法，其中|I|表示实例I的规模或输入长度，进而，设实例I的最优值为OP（I），而算法A所得到实例I的可行解之值为A（I），则称算法A解实例I的性能比为RA（I）的性能比为RA（D），同时称D有RA近似解其中 A ( I) OP(I) ， 若D为最小化问题.R A ( I) = OP(I) ， 若D为最大化问题. A ( I)RA(D)=infr|RA(I)r，ID2近似算法的特点（1）解同一个问题的近似算法可能有多个（2）算法的时间复杂性：近似算法的时间复杂性必须是多项式阶的，这是设计近似算法的基本目标。（3）解的近似程度：近似最优解的近似程度也是设计近似算法的重要目标。近似程度可能
