算法设计与分析学习提纲,第十五章近似算法
- 格式：doc
- 大小：1.07 MB
- 文档页数：19
第十五章 近似算法
输入数据本身就是近似的
很多问题的最优解，允许有一定程度的近似
采用近似算法可以在很短的时间内得到问题的解（特别是与指数时间相比较）
15.1 近似算法的性能
一、近似算法的基本要求
对于规模为n的问题，
1. 算法能以n的多项式时间内完成；
2. 算法的近似解满足一定的精度。
二、近似比率
1、近似算法的近似比率
是最小化问题，I是的一个实例，A是解的一个近似算法， )(IA是用算法A对的实例I求解时得到的近似值；OPTA是解的最优算法， )(IOPTA是算法OPTA对的实例I求解时所得到准确值。则近似算法A的近似比率)(I为：
)()()(IOPTAIAI
如果是最大化问题，则)(I为：
)()()(IAIOPTAI
2、与近似比率相关的问题
1）对最小化问题，有：)()(IOPTAIA；
对最大化问题，有：)()(IOPTAIA。
2）近似算法A的近似比率)(I总大于或等于1。
3）近似算法的近似比率越小，则算法的性能越好。
三、相对误差
1、相对误差的定义
相对误差表示近似算法的精确度，相对误差定义为：
)()()(IOPTAIAIOPTA
2、相对误差的界 若对输入规模为n的问题，存在函数)(n，使得：
)()()()(nIOPTAIAIOPTA
称函数)(n为近似算法A的相对误差的界。
3、相对误差)(n与近似比率)(n的关系
1)()(nn。
四、优化问题的近似方案（approximation scheme）
1、很多难解的问题，可以增加近似算法的计算量，来改善近似算法的性能。
2、优化问题的近似方案
把满足1),(IA的一类近似算法}0|{A，称为优化问题的近似方案
算法的性能比率会聚于1。
3、多项式近似方案（polynomial approximation scheme PAS）
近似方案中的每一个算法A，以输入实例的规模的多项式时间运行，称该近似方案为多项式近似方案。
算法的计算时间，不随的减少而增长太快。
4、完全多项式近似方案（fully polynomial approximation scheme FPAS）
减少常数倍，近似方案中算法的计算时间的增长不超过个常数倍。
近似方案中算法的计算时间是/1和n的多项式
15.2 装箱问题
一、装箱问题（BIN PACKING）
给定n个物体nuuu,,,21，体积分别为nsss,,,21，容量为C的箱子,,,,21kbbb，满足Csi，ni,,2,1。要求物体不能分割，把所有物体装进箱子，使所装入的箱子尽可能少。
二、装箱问题的四种算法
1、 First Fit（首次适宜FF）算法：
把箱子按下标,,,2,1k标记，所有的箱子初始化为空；
按物体nuuu,,,21顺序装入箱子。
装入过程如下：
把第一个物体1u装入第一个箱子1b，
如果1b还容纳得下第二个物体，继续把第二个物体2u装入1b；
否则，把2u装入2b。
一般地，为了装入物体iu，先找出能容纳得下is的下标最小的箱子kb，
再把物体iu装入箱子kb，
重复这些步骤，直到把所有物体装入箱子为止。 2、Best Fit（最适宜BF）算法：
与FF算法类似，
不同点：为了装入物体iu，首先检索能容纳得下is、剩余容量最小的箱子kb，
再把物体iu装入箱子kb，
重复这些步骤，直到把所有物体装入箱子为止。
3、First Fit Decreasing（首次适宜降序FFD）算法：
首先把物体按体积大小递减的顺序排序，
然后用FF算法装入物体。
4、Best Fit Decreasing（最适宜降序BFD）算法：
首先把物体按体积大小递减的顺序排序，
然后用BF算法装入物体。
15.2.1 首次适宜算法
一、FF算法的描述：
算法15.1 装箱问题的首次适宜算法
输入：n个物体的体积s[],箱子的容量C
输出：装入箱子的个数k,每个箱子中装入的物体累计体积b[]
1. void first_fit(float s[],int n,float C,float b[],int &k)
2. {
3. int i,j;
4. k = 0; /* 装入物体的箱子下标 */
5. for (i=0;i
6. b[i] = 0;
7. for (i=0;i
8. j = 0;
9. while ((C-b[j])
10. j++;
11. b[j] += s[i];
12. k = max(k,j); /* 已装入物体的箱子最大下标 */
13. }
14. k++; /* 箱子的最大下标转换为箱子的个数 */
15. }
二、FF算法的分析
1、时间复杂性： )(2nO时间。
2、算法性能估计： 假定，C为一个单位体积，1is，ni,,2,1。
令)(IFF表示在实例I下，使用算法FF装入物体时，所使用的箱子数目；
令)(IOPT为最优装入时所使用的箱子数目。
至多有一个非空的箱子所装的物体体积小于2/1。
否则，如果有两个以上的箱子所装的物体体积小于2/1，
假设这两个箱子是ib及jb，并且ji，
装入ib及jb中物体的体积均小于2/1。
按照算法的装入规则，必然把jb中的物体继续装入ib，而不会装入另外的箱子。
则装入箱子的物体如图15.1 所示：
1 2 1k k
┅┅
1 2 1k k
图15.1 FF算法的箱子装入情况
i为箱子中的空余体积，i为箱子中装入的物体体积。有：
niikiis11 及 ii，12,1ki
对第k个箱子，或者是kk，或者是kk。
对后一情况，有：kk1，1kk，所以：kkkk11。
对这两种情况都有：
niikiikiis111
所以，
niikiikiisIFF1112)(
在最优化装入时，所有的箱子恰好装入全部物体，即：
niisIOPT1)(
FF算法的性能比率)(IFF为：
2)()()(IOPTIFFIFF FF算法的性能比率小于2。
实际上，经过复杂而冗长的证明，可以得到：
定理15.1 对装箱物体的所有实例I，FF算法的性能为：
2)(1017)(IOPTIFF
15.2.2 最适宜算法及其它算法
一、最适宜算法
1、算法描述：
算法15.2 装箱问题的最适宜算法
输入：n个物体的体积s[],箱子的容量C
输出：装入箱子的个数k,每个箱子中装入的物体累计体积b[]
1. void best_fit(float s[],int n,float C,float b[],int &k)
2. {
3. int i,j,m;
4. float min,temp;
5. k = 0; /* 装入物体的箱子下标 */
6. for (i=0;i
7. b[i] = 0;
8. for (i=0;i
9. min = C; m = k + 1;
10. for (j=0;j<=k;j++) { /* 检索能容纳物体i且剩余容量最小的箱子j*/
11. temp = C – b[j] – s[i];
12. if ((temp>=0)&&(temp
14. min = temp; m = j;
15. }
16. }
17. b[m] += s[i];
18. k = max(k,m); /* 已装入物体的箱子最大下标 */
19. }
20. k++; /* 箱子的最大下标转换为箱子的个数 */
21. }
2、时间复杂性也：)(2nO时间。
3、性能比率：与首次适宜算法FF的性能比率相同。
二、首次适宜降序算法FFD及最适宜降序算法： 1、算法描述：
算法15.3 装箱问题的首次适宜降序算法
输入：n个物体的体积s[],箱子的容量C
输出：装入箱子的个数k,每个箱子中装入的物体累计体积b[]
1. void first_fit_dec(float s[],int n,float C,float b[],int &k)
2. {
3. mergsort(s,n); /* 把物体按体积大小的递减顺序排序 */
4. first_fit(s,n,C,b,k); /* 按首次适宜算法把排序过的问题装入箱子 */
5. }
算法15.4 装箱问题的最适宜降序算法
输入：n个物体的体积s[],箱子的容量C
输出：装入箱子的个数k,每个箱子中装入的物体累计体积b[]
1. void best_fit_dec(float s[],int n,float C,float b[],int &k)
2. {
3. mergsort(s,n); /* 把物体按体积大小递减的顺序排序 */
4. best_fit_dec(s,n,C,b,k); /* 按最适宜算法把排序过的问题装入箱子 */
5. }
2、时间复杂性
两个算法的第3行，对物体按其体积大小的递减顺序排序，需)log(nnO时间。
第4行分别调用首次适宜算法和最适宜算法把物体装入箱子，需)(2nO时间。
因此，这两个算法的时间复杂性也是)(2nO时间。
2、性能比率
两个算法的性能比率相同，都好于首次适宜算法和最适宜算法。
有下面的定理：
定理15.2 对装箱物体的所有实例I，FFD算法的性能为：
4)(911)(IOPTIFFD
15.3 顶点覆盖问题
一、顶点覆盖的优化问题
无向图),(EVG，G的顶点覆盖C是顶点集V的子集，VC，使得Evu),(，有Cu，或者Cv。顶点覆盖的优化问题，是找出图G中的最小顶点覆盖
二、数据结构
假定，顶点用1,,1,0n编号；用的邻接表存放顶点与顶点之间的关联边。
