近似算法.doc

第十五章近似算法输入数据本身就是近似的很多问题的最优解,允许有一定程度的近似采用近似算法可以在很短的时间内得到问题的解(特别是与指数时间相比较)、近似算法的基本要求对于规模为的问题,;。二、近似比率1、近似算法的近似比率是最小化问题,是的一个实例,是解的一个近似算法,是用算法对的实例求解时得到的近似值;是解的最优算法,是算法对的实例求解时所得到准确值。则近似算法的近似比率为:如果是最大化问题,则为: 2、与近似比率相关的问题1)对最小化问题,有:;对最大化问题,有:。2)近似算法的近似比率总大于或等于1。3)近似算法的近似比率越小,则算法的性能越好。三、相对误差1、相对误差的定义相对误差表示近似算法的精确度,相对误差定义为:2、相对误差的界若对输入规模为的问题,存在函数,使得:称函数为近似算法的相对误差的界。3、相对误差与近似比率的关系。四、优化问题的近似方案(approximationscheme)1、很多难解的问题,可以增加近似算法的计算量,来改善近似算法的性能。2、优化问题的近似方案把满足的一类近似算法,称为优化问题的近似方案算法的性能比率会聚于1。3、多项式近似方案(polynomialapproximationschemePAS)近似方案中的每一个算法,以输入实例的规模的多项式时间运行,称该近似方案为多项式近似方案。算法的计算时间,不随的减少而增长太快。4、完全多项式近似方案(fullypolynomialapproximationschemeFPAS)减少常数倍,近似方案中算法的计算时间的增长不超过个常数倍。、装箱问题(BINPACKING)给定个物体,体积分别为,容量为的箱子,满足,。要求物体不能分割,把所有物体装进箱子,使所装入的箱子尽可能少。二、装箱问题的四种算法1、FirstFit(首次适宜FF)算法:把箱子按下标标记,所有的箱子初始化为空;按物体顺序装入箱子。装入过程如下:把第一个物体装入第一个箱子,如果还容纳得下第二个物体,继续把第二个物体装入;否则,把装入。一般地,为了装入物体,先找出能容纳得下的下标最小的箱子,再把物体装入箱子,重复这些步骤,直到把所有物体装入箱子为止。2、BestFit(最适宜BF)算法:与FF算法类似,不同点:为了装入物体,首先检索能容纳得下、剩余容量最小的箱子,再把物体装入箱子,重复这些步骤,直到把所有物体装入箱子为止。3、FirstFitDecreasing(首次适宜降序FFD)算法:首先把物体按体积大小递减的顺序排序,然后用FF算法装入物体。4、BestFitDecreasing(最适宜降序BFD)算法:首先把物体按体积大小递减的顺序排序,然后用BF算法装入物体。、FF算法的描述::n个物体的体积s[],箱子的容量C输出:装入箱子的个数k,每个箱子中装入的物体累计体积b[](floats[],intn,floatC,floatb[],int&k)2.{,j;=0; /*装入物体的箱子下标*/(i=0;i<n;i++) /*箱子初始化为空*/[i]=0;(i=0;i<n;i++){ /*按物体顺序装入*/=0;((C-b[j])<s[i]))/*检索能容纳物体i的下标最小的箱子j*/++;[j]+=s[i];=max(k,j); /*已装入物体的箱子最大下标*/13.}++; /*箱子的最大下标转换为箱子的个数*/15.}二、FF算法的分析1、时间复杂性:时间。2、算法性能估计:假定,为一个单位体积,,。令表示在实例下,使用算法FF装入物体时,所使用的箱子数目;令为最优装入时所使用的箱子数目。至多有一个非空的箱子所装的物体体积小于。否则,如果有两个以上的箱子所装的物体体积小于,假设这两个箱子是及,并且,装入及中物体的体积均小于。按照算法的装入规则,必然把中的物体继续装入,而不会装入另外的箱子。:,为箱子中装入的物体体积。有:及,对第个箱子,或者是,或者是。对后一情况,有:,,所以:。对这两种情况都有:所以,在最优化装入时,所有的箱子恰好装入全部物体,即:FF算法的性能比率为:FF算法的性能比率小于2。实际上,经过复杂而冗长的证明,可以得到:,FF算法的性能为:、最适宜算法1、算法描述: