近似算法

IT商界

PALDIN

　　上期我们讲了有关NP完全问题的定义及判定方法。到目前为止，对于NP完全问题还没有找到多项式时间的算法。但在许多实际应用中，我们不可能都用穷举法去追求问题的最佳解决结果。例如对于作业调度问题，如果为了得到最优作业调度的时间消耗带来的经济损失已经超过了不用任何调度可能带来的最大损失，那么，即使是找到最优调度也是得不偿失，没有实际意义的。

　　日常生活中，有很多NP完全问题是经常会遇到的。那么，在解决这些实际问题的时候，我们应该如何来处理呢？答案就是使用近似算法。下面我们首先结合上期讲到的背包问题来简单介绍一下近似算法的选取和性能分析。

　　背包问题就是：给定n个尺寸为S1,S2......Sn的物体和容量为C的背包，其中S1,S2,......Sn和C均为正整数。问题是：在n个物体中选取一部分，尽可能多地填满容量为C的背包。

　　由于背包问题可以描述为在{S1,S2......Sn}的整数集中选取一个子集T，使∑Si(Si属于子集T)取最大值，且不大于C。我们考虑的近似算法是首先将输入的数据S1,S2,......Sn按非递增次序重新排序。然后，对于某个k≥0，我们对每个至多只有k个元素的子集T进行测试，如果∑Si

　　//背包问题的一种近似算法的描述

　　//入口参数：n──物体的个数 S──物体尺寸的整数集 C──背包的容量 MAXV──获得//的最大容量 SET──是{1,2,......n}的一个子集就是装入背包的物体的标号的集合

　　1.对于S按非递增次序重新排序得到S'(Si1,Si2,......Sin)

　　2. SET←φ;MAXV←0

　　3. FOR d=0 to k do

　　4. { 依次选取个数为d的子集T

　　5. { 首先获取子集T中物体的总重量SUM

　　6. For j=1 to n do //从余下的物体中依次选取能装的下的最大物体

　　7. { if j不属于子集T THEN

　　8. { if SUM+ Sj'≤C THEN

　　9. { SUM←SUM+ Sj'

　　10. T←T∪{ij}

　　11. if SUM=C THEN j←n //找到最优方案

　　12. }

　　13. }

　　14. }

　　15. if MAXV＜SUM THEN

　　16. { MAXV←SUM

　　17. SET←T

　　18. }

　　19. if MAXV=C THEN

　　20. { RETURN //找到最优方案

　　21. }

　　22. }

　　23. }

　　24. RETURN //找到的一个方案，但不能确定是否最优

　　可以证明上面的算法在最坏的情况下(如果在不考虑算法第1行排序的运算以及将算法的第6行的循环每执行一次记为一个运算单位)算法的总工作量最多时k+n次运算，这个算法是多项式界的。还可以证明这个算法得到的物体总重量应该是大于等于最优解的k/(k+1)，k取得越大，两者的误差越小。(由于篇幅问题，证略。感兴趣的朋友可以自己分析一下)。

　　总的来说，对于解决实际的NP完全问题的方法可以归纳成以下几条：1.只对特殊的实例求解。对于一些NP完全问题也许在最一般的意义下求解就可以了，在特殊情况下的NP完全问题常常是有高效的算法的。2.用动态规划法、回溯法等方法求解，在许多情况下，它们比穷举搜索法有效得多。3.用概率算法求解。如果能够通过概率分析证明某些实例是很难遇到的，就可以利用概率算法来解决这类NP完全问题。4.只求近似解。在实际问题中不一定总要求问题的精确解，只要求解在一定的误差范围里就可以了。5.用启发式方法求解。在用别的方法不能很好解决问题的时候，可以根据具体问题的启发式搜索策略来寻求问题的解。

　　对于使用近似算法解决NP完全问题的知识内容是丰富的，在这里无法一一详细讲解。我相信实践出真知，朋友们一定可以在日后的实践过程中积累到大量的知识和经验。