第十五章 近似算法输入数据本身就是近似的很多问题的最优解，允许有一定程度的近似采用近似算法可以在很短的时间内得到问题的解（特别是与指数时间相比较）15.1 近似算法的性能一、近似算法的基本要求对于规模为的问题， 1. 算法能以的多项式时间内完成；2. 算法的近似解满足一定的精度。二、近似比率1、近似算法的近似比率是最小化问题，是的一个实例，是解的一个近似算法， 是用算法对的实例求解时得到的近似值；是解的最优算法， 是算法对的实例求解时所得到准确值。则近似算法的近似比率为：如果是最大化问题，则为：2、与近似比率相关的问题1）对最小化问题，有：；对最大化问题，有：。2）近似算法的近似比率总大于或等于1。3）近似算法的近似比率越小，则算法的性能越好。三、相对误差1、相对误差的定义相对误差表示近似算法的精确度，相对误差定义为：2、相对误差的界若对输入规模为的问题，存在函数，使得：称函数为近似算法的相对误差的界。3、相对误差与近似比率的关系。四、优化问题的近似方案（app
