近似算法的特点与计算方法、分类及概率算法的计算过程与应用.docx

近似算法和概率算法的特点与计算方法分类及概率算法的计算过 程与应用 一 近似算法 1 近似算法的计算方法 设D是一个最优化问题A是一个算法若把A用于D的任何一个实 例 I都能在|I|的多项式时间内得到I的可行解则称算法A为问题D 的一个近似算法其中|I|表示实例I的规模或输入长度进而设实 例I的最优值为OPI而算法A所得到实例I的可行解之值为AI 则称算法A解实例I的性能比为RAI的性能比为RA