经典一维装箱问题的适应近似算法的研究.doc

经典一维装箱问题的适应近似算法的研究经典一维装箱问题的适应近似算法的研究摘 要本文研究经典一维装箱问题（Bin Packing Problem）及其适应近似算法，给出了一个新的适应近似算法：交叉装填算法（简称CF算法），而且证明了当这些物件大小按非增性预先排序后，CF算法时间复杂度是线性的；通过具体例子说明交叉装填算法优于其它适应近似算法，并且推断CF算法达到装箱问题的最好近似值。关键词：一维装箱问题，近似算法，适应算法，交叉装填算法 ABSTRACT In this paper the Bin-Packing problems and any-fit approximation algorithm are studied. We give a new any-fit approximation algorithm (Cross Fit Approximation Algorithm) in steps. In addition, if the sizes of all objects decreasing according to their sizes, The any-fit approximation algorithm runs in steps. This paper proved the cross fit approximation algorithms capability excelled other any-fit approximation algorithms by some example,and extrapolate the new any-fit algorithm is a approximation algorithm. Key Words：Pin Packing Problem，Approximation Algorithm，Any-fit Algorithm， Cross Any-fit Algorithm.1 引言11 问题的提出装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品体积之和不超过箱子容量并使所用的箱子数目最少。其应用在实际生活中无处不在，货物装运，服装裁剪，以及计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。例如某国际物流公司有一批固体货物要装进集装箱用船从广州运到美国。每个集装箱的规格都一样（体积均为150立方米），而每件货物体积不一定相同但其长宽高都小于集装箱的。问怎样的装箱方案最省钱，即所用集装箱最少？研究装箱问题能够更好解决上述这些问题，有很大的经济效益。所以装箱问题有着广泛的应用背景，具有很大的研究价值。但是装箱问题是NP难解问题7，这意味着该问题不存在在多项式时间内求得精确解的算法（如果PNP）因此对装箱问题算法的研究指的是对其近似算法的研究，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。目前，已经提出了大量的近似算法，其中适应近似算法是目前时间复杂性比较低的一种近似算法。如下次适应（NF）算法、首次适应（FF）算法、最佳适应（BF）算法、降序首次适应(FFD)算法、降序最佳适应(BFD)算法等。装箱问题中最早被研究的是一维装箱问题。随着研究的深入，人们发现实际生活中更多存在的是一些带约束的装箱问题，因此也就抽象化出了，如二维装箱问题（条形装箱问题、剪裁问题）、三维装箱问题、变容装箱问题、有色装箱问题、对偶装箱问题等等一系列的带约束的装箱问题。但是由于这些问题的NP困难性，虽然已经有一些研究成果，但是还有很许多未解问题,甚至一些是一维装箱问题5。一维装箱问题是指要求把一些物品放入到具有固定容量的箱子中，并最小化所使用的箱子数目。本文所讨论的是一维装箱问题。12 相关知识在研究一维装箱问题的适应近似算法之前，我们先来了解一下一些相关的知识。 121近似算法的定义一个组合最优化问题是一个最小化或最大化的问题,由三部分组成:实例的集合;I,有一个有限的可行解集合;有一个目标函数,使得I及,赋予一个正有理数(I, ),称为的目标值.对于最小(大)化问题,称为I的最优值是指,恒有最优解的目标值成为I的最优值,记作,当这个问题明确时通常省略下标.定义1 称算法是的一个近似算法(Approximation Algorithm)是指: I,应用算法总可以找出I的一个可行解.对应的解的目标值记作,表示由算法A得到的I的目标值.若I,都有=，则称A是的最优算法(Optimization Algorithm)。122适应算法定义2 适应算法(Any Fit Algorithm)：适应算法是解装箱问题的一个近似算法。当处理当前物品，如果有已经打开的箱子中能够放下这个物品，则不打开新的箱子，符合该条件的算法被称为适应算法。其中下次适应算法、首次适应算法、最佳适应算法、最坏适应算法和几乎最坏适应算法是几个著名的适应算法。适应算法的最坏情况性能比被证明一定处于1.7,2范围内，即在最坏情况性能上不可能优于首次适应算法2。123经典一维装箱问题在经典一维装箱问题中，处理对象是n个输入物品的序列和一个无限多的等容量箱子序列；目标是把所有物品放入箱子中并最小化所使用的箱子数目。可以对其做如下定义：经典一维装箱问题：给定n个物品的序列Ln=（a1,a2,an），物品ai（1in）的大小s(ai) (0,1，要求将这些物品装入最小数量的单位容量的箱子中。例如，把ai（1in）分别放入箱子序列B1,B2,Bm中，使得每个箱子中的物品大小之和不超过1，即 s(ai)1，1jm，且使所用的箱子数目m最小。2 经典一维装箱问题的适应近似算法近似算法并不保证给出最优解,那么应当如何来评价近似算法的好坏呢?主要基于两个方面的考虑.首先是时间复杂性方面的要求,即要求有一个多项式时间界;其次是性能方面的要求,即希望所求得的近似解尽可能地“接近”最优解.可以从不同的角度来评价近似算法性能,大体可以分为三类:第一类是以算法在最坏情况下的行为标准，研究算法得到最优解的接近程度，越接近越好；第二类是以算法的平均行为为标准研究得到最优解的概率；第三类是局部搜索算法，寻找局部最优解，这种算法有时很好，有时很坏，只能通过实践加以评定。本文所讨论的是第一种类型。为了更好地从性能方面来讨论近似算法，我们给出度量近似算法性能的两个指标。设是一个最小（大）化问题，I是的实例。设A是的一个近似算法，由A得到的目标值为A（I），而I的最优目标值为OPT（I），记 （）, 定义3 的近似算法A的绝对性能比（absolute performance ratio）记为 ， 定义4 的近似算法A的渐近性能比（asymptotic performance ratio）记为 ，其中。 又称为近似算法A的近似值。 我们分析装箱问题的近似算法的性能包括两个主要内容2： （1）建立近似算法在最坏情况下所得目标值的一个界； （2）构造实例说明得到的界可以达到或渐近达到，从而说明这个界已经相当好了。首先我们用下面的经典结果说明一维装箱求解的困难程度。引理11 如果，那么对于任意给定的，不存在近似值为的近似算法来解决一维装箱问题。 因此这个近似值是我们对一维装箱问题的近似算法的最好期待，事实上，很多近似算法的近似值都是朝这个目标迈进3。本文给出的算法也是朝这个目标前进。21已知的常用适应近似算法234211 NF(Next Fit)近似算法该算法的做法是随到随装,装不下就封箱运走.将n个物品依次装箱,设已装入箱,且即不能装入箱,则箱虽未装满也装箱送走, 装入下一个箱子,这种装箱方法适合流水作业,其时间复杂性为O(n)。定理12 对装箱问题的何实例I，均有 （2.1）例1 设物品集，各物品得体积为 对这个实例I，易知OPT（I）m+1，而NF（I）2m，从而 由定理1和例1，我们有推论22 . (2.2)212 FF（First Fit）近似算法 这是一种较为直观的、容易想到的装箱方法，其基本思想是将n个物品顺次装箱，设装箱的次序是；对某一物，它总是被装到第一个能装下它的箱子中，也就是说物品被装到已装进的物品的体积不超过的下标最小的箱子中。这种装箱办法虽然不要求个物品全部到达后再装箱，但要求所有箱子都装好后一起送走，可以说适合半流水线作业。 由于每个物品装箱时都必须从开始顺次查看各个箱子是否能装下它，故FF算法的时间复杂性为。 关于FF算近似法的性能我们有如下结果： 定理33 对装箱问题的任何实例，均有 ， （2.3）并且，存在实例，使得充分大且满足 ， 从而。 公式（2.3给出了FF近似算法在最坏情况下所得到的目标值的界，反映了近似解“接近”最优解的程度。下面用FF算法计算一个例子所需的箱子数目。例2设物品集，物品的体积为 其中充分小。在这个实例I中，最优值，而，故，装箱方案如图1所示，左边第一个图是最优装箱方案，右边的三个图是FF近似算法的装箱方案 个 个 个 个 图1 例2的装箱方案213 FFD（First Fit Decreasing）近似算法该算法要求n个物品全部到达后才开始装箱（因为物品全部到达后才能将它们按体积从大到小排列），同时也要求所有箱子全部装好后一起送走。FFD近似算法比FF近似算法多了排序的计算量，因而它的时间复杂性仍然为4。定理42 对装箱问题的任何实例I，均有 ， 并且存在实例I，使得充分大且满足， （2.3）从而。 下面的例子表明（2.3）式的成立。例3 设物品集，各物品的体积为 其中充分小，该实例I的最优值为，而，故。装箱方案如图2所示，其中前面两个图为最优装箱方案 ，后三个图为FFD近似算法的装箱方案。6m个 3m个 6m个 2m个 3m个 图2 例3的装箱方案 上述三种一维装箱问题的适应算法虽然逐步逼近引理1的解决方案，平均性能比也达到了12,但离最优值还有一定距离，并且得到的装填方案有比较大的随机性，实际操作起来有一定难度，下面对上述一维装箱问题的适应近似算法加以改进，给出一种可操作性强的一种更优化的近似算法。如果对FF算法稍加修改：物品装进中要求留下的空隙最小，即 这就得到另一个近似算法BF（best fit）近似算法。但如果在装箱前先把物品按体积从大到小排列，再利用FF近似算法（或BF近似算法）就得到改进的近似算法FFD（或BFD）近似算法。在FFD（或BFD）近似算法的基础上利用交叉装填的思想，就得到一种新的经典一维装箱问题的适应近似算法交叉装填近似算法。22新的适应近似算法算法的主要意思是：先把物件按大小从大到小的顺序排列，然后首先把左端最大的一个物件放入箱子中，再从物件序列的最右端开始从右往左依次把物件放入箱子中，直到下一个物件不能放入该箱子，那么开启新的箱子，重复上述装填步骤，直到所有的物件都装入箱子中。 下面给出经典一维装箱问题的交叉装填算法：交叉装填算法（CF近似算法）输入：及每个物件的大小。输出：需要的箱子数目。步骤1：把物件按其大小进非增序排列，不妨设。步骤2：首先把放入箱子中，然后从最右端开始，依次把物件放入，直到下一个物件不能再装入箱子为止，此时开启新的箱子。步骤3：设在第步循环时，打开第个箱子，此时把物件放进箱子中，再从最右端开始从右往左把物件依次放入中。假设第步循环时第个箱子中最后一个放入的物件为，则在第步循环时最右端的物件为，那么当且时，把放入中，同时开启新的箱子。直到把所有物件都放进个箱子里。步骤4：得出交叉装填算法所需的箱子数目。 下面作者用新的一维装箱问题的适应近似算法求解例，在求解过程中比较该近似算法较上述几种算法性能。例1 设物品集，各物品得体积为 对这个实例I，易知OPT（I）m+1，而CF（I）m1，从而 .装箱方案如图3所示，其中前面两个图为最优装箱方案 ，后两个图为FFD近似算法的装箱方案。 1个 个 2个 个 图3 例1的装箱方案例2 设物品集，物品的体积为 其中充分小。在这个实例I中，最优值，而，故： 装箱方案如图4所示，其中左边第一个图是最优装箱方案，右边的三个图是FF近似算法的装箱方案。 个 个 个 个 图4 例2装箱方案例3 设物品集，各物品的体积为 其中充分小，该实例I的最优值为，而，故。装箱方案如图5所示，其中前面两个图为最优装箱方案 ，后三个图为FFD近似算法的装箱方案。 个 个 个 个 个图5 例3的装箱方案在用交叉装填近似算法（CF算法）对例1、例2和例3求解的过程中，我们得到例1、例2和例3的求解方案得到：说明1：观察例1和例1的求解方案，我们得到CF近似算法能够达到最优解，性能优于NF近似算法。说明2：观察例2和例2的求解方案，我们得到CF近似算法能够达到最优解，性能优于FF近似算法。说明3：观察例3和例3的求解方案，我们得到CF近似算法虽然未能达到最优解，但是，而且性能优于NF近似算法。说明4：交叉装填近似算法是一维装箱问题的适应近似算法中机械操作最强的一种算法，对所有一维装箱问题都有固定的装箱方案，对半流水线作业容易达到最优解。猜想5：交叉装填近似算法是目前经典一维装箱问题的适应近似算法中最优化的一种算法，交叉装填算法是一维装箱问题的近似算法,即。论断6：交叉装填近似算法的时间复杂性为。证明： 由于在初始化步骤（步骤1）中，由文献6得到排序所用的时间为。在迭代步骤中，第1次循环所用的时间为，第2次循环所用的时间为第次循环所用时间为而从而迭代步骤所需的时间为.故交叉装填算法的时间复杂性为。如果物件按非增性质先排列好序，则交叉装填算法的复杂性为。结论：本文对经典一维装箱问题给出了一个新的适应近似解法，它是多项式时间算法；用新旧适应近似算法求解具体例子，通过对新旧算法的性能比较，得出新算法求得的问题的解与“最优值” 更进一步地接近。由于本文给出的适应近似算法优于已有的适应近似算法，我们完全可以猜想经典一维装箱问题的交叉装填适应近似算法是一维装箱问题的近似算法。通过对一维装箱问题适应近似算法的研究，我们可以很容易得到具体装箱问题比较理想的解决方案，例如在引言里叙述的物流公司的集装箱问题，在只考虑体积和已知各物件的体积的情况下就可以利用交叉装填近似算法来装箱。读者不妨自己尝试设定各物件的体积，看看能不能算出该物流公司这次所需的集装箱个数，同时看能否找到比交叉装填近似算法更好的装箱方案。此外，现在人们更多的关注于由一维经典装箱问题所衍生出来的一些装箱问题，这些问题一方面与一维装箱问题有着密切联系，另一方面又有着更广泛的实际应用背景。我们未来的工作应继续关注研究经典一维装箱问题交叉装填适应近似算法的性能以及装箱问题衍生的各种问题，以其能对实际生活工作提供更大的帮助。参考文献1 孙春玲，陈智斌，李建平. 装箱问题的一种新的近似算法J.云南大学学报（自然科学版）. 2004，26（5）.3923962 谢政编著.网络算法与复杂性理论M.国防大学出版社.2003,12.223-2753 顾晓东，陈国良.装箱问题的并行近似算法J.计算机学报.2001，24（5）.5485524 冯晓慧，李菊娥，任春丽.装箱问题的一种新算法及其性能比的证明J.西安电子科技大学学报.1998，4（25卷2期）.2312385顾晓东，陈国良，顾钧等.调和装箱问题的平均性能分析J.计算机学报.2001,56（美）Papadimitriou，C.H，Steigtisz K. 组合最优化算法和复杂性M.清华大学出版社.1988,6.228-235 7 胡知能，徐玖平.运筹学线性系统优化M.科学出版社.2003,3.致 谢感谢我的论文指导老师刘岩副教授，她严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；她循循善诱的教导和不拘一格的思路给予我无尽的启迪。这篇论文的每个方法和每个例子，都离不开刘岩教授的析心指导；而她开朗的个性和宽容的态度，使我能够很愉快地完成了这篇论文。感谢我的爸爸妈妈，焉得谖草，言树之背，养育之恩，无以回报，你们永远健康快乐是我最大的心愿。 在论文即将完成之际，我的心情无法平静，从开始选题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无私的帮助，在这里请接受我诚挚的谢意！ 1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究2. 基于单片机的嵌入式Web服务器的研究 3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究 4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制 5. 基于MCS-51系列单片机的通用控制模块的研究 6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器7. 单片机控制的二级倒立摆系统的研究8. 基于增强型51系列单片机的TCP/IP协议栈的实现 9. 基于单片机的蓄电池自动监测系统 10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究11. 基于单片机的作物营养诊断专家系统的研究 12. 基于单片机的交流伺服电机运动控制系统研究与开发 13. 基于单片机的泵管内壁硬度测试仪的研制 14. 基于单片机的自动找平控制系统研究 15. 基于C8051F040单片机的嵌入式系统开发 16. 基于单片机的液压动力系统状态监测仪开发 17. 模糊Smith智能控制方法的研究及其单片机实现 18. 一种基于单片机的轴快流CO,2激光器的手持控制面板的研制 19. 基于双单片机冲床数控系统的研究 20. 基于CYGNAL单片机的在线间歇式浊度仪的研制 21. 基于单片机的喷油泵试验台控制器的研制 22. 基于单片机的软起动器的研究和设计 23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究 24. 基于单片机的机电产品控制系统开发 25. 基于PIC单片机的智能手机充电器 26. 基于单片机的实时内核设计及其应用研究 27. 基于单片机的远程抄表系统的设计与研究 28. 基于单片机的烟气二氧化硫浓度检测仪的研制 29. 基于微型光谱仪的单片机系统 30. 单片机系统软件构件开发的技术研究 31. 基于单片机的液体点滴速度自动检测仪的研制32. 基于单片机系统的多功能温度测量仪的研制 33. 基于PIC单片机的电能采集终端的设计和应用 34. 基于单片机的光纤光栅解调仪的研制 35. 气压式线性摩擦焊机单片机控制系统的研制 36. 基于单片机的数字磁通门传感器 37. 基于单片机的旋转变压器-数字转换器的研究 38. 基于单片机的光纤Bragg光栅解调系统的研究 39. 单片机控制的便携式多功能乳腺治疗仪的研制 40. 基于C8051F020单片机的多生理信号检测仪 41. 基于单片机的电机运动控制系统设计 42. Pico专用单片机核的可测性设计研究 43. 基于MCS-51单片机的热量计 44. 基于双单片机的智能遥测微型气象站 45. MCS-51单片机构建机器人的实践研究 46. 基于单片机的轮轨力检测 47. 基于单片机的GPS定位仪的研究与实现 48. 基于单片机的电液伺服控制系统 49. 用于单片机系统的MMC卡文件系统研制 50. 基于单片机的时控和计数系统性能优化的研究 51. 基于单片机和CPLD的粗光栅位移测量系统研究 52. 单片机控制的后备式方波UPS 53. 提升高职学生单片机应用能力的探究 54. 基于单片机控制的自动低频减载装置研究 55. 基于单片机控制的水下焊接电源的研究 56. 基于单片机的多通道数据采集系统 57. 基于uPSD3234单片机的氚表面污染测量仪的研制 58. 基于单片机的红外测油仪的研究 59. 96系列单片机仿真器研究与设计 60. 基于单片机的单晶金刚石刀具刃磨设备的数控改造 61. 基于单片机的温度智能控制系统的设计与实现 62. 基于MSP430单片机的电梯门机控制器的研制 63. 基于单片机的气体测漏仪的研究 64. 基于三菱M16C/6N系列单片机的CAN/USB协议转换器 65. 基于单片机和DSP的变压器油色谱在线监测技术研究 66. 基于单片机的膛壁温度报警系统设计 67. 基于AVR单片机的低压无功补偿控制器的设计 68. 基于单片机船舶电力推进电机监测系统 69. 基于单片机网络的振动信号的采集系统 70. 基于单片机的大容量数据存储技术的应用研究 71. 基于单片机的叠图机研究与教学方法实践 72. 基于单片机嵌入式Web服务器技术的研究及实现 73. 基于AT89S52单片机的通用数据采集系统 74. 基于单片机的多道脉冲幅度分析仪研究 75. 机器人旋转电弧传感角焊缝跟踪单片机控制系统 76. 基于单片机的控制系统在PLC虚拟教学实验中的应用研究77. 基于单片机系统的网络通信研究与应用 78. 基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究79. 基于单片机的模糊控制器在工业电阻炉上的应用研究 80. 基于双单片机冲床数控系统的研究与开发 81. 基于Cygnal单片机的C/OS-的研究82. 基于单片机的一体化智能差示扫描量热仪系统研究 83. 基于TCP/IP协议的单片机与Internet互联的研究与实现 84. 变频调速液压电梯单片机控制器的研究 85. 基于单片机-免疫计数器自动换样功能的研究与实现 86. 基于单片机的倒立摆控制系统设计与实现 87. 单片机嵌入式以太网防盗报警系统 88. 基于51单片机的嵌入式Internet系统的设计与实现 89. 单片机监测系统在挤压机上的应用 90. MSP430单片机在智能水表系统上的研究与应用 91. 基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用92. 单片机在高楼恒压供水系统中的应用 93. 基于ATmega16单片机的流量控制器的开发 94. 基于MSP430单片机的远程抄表系统及智能网络水表的设计95. 基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计 96. 基于单片机的氨分解率检测系统的研究与开发 97. 锅炉的单片机控制系统 98. 基于单片机控制的电磁振动式播种控制系统的设计 99. 基于单片机技术的WDR-01型聚氨酯导热系数测试仪的研制 100. 一种RISC结构8位单片机的设计与实现 101. 基于单片机的公寓用电智能管理系统设计 102. 基于单片机的温度测控系统在温室大棚中的设计与实现103. 基于MSP430单片机的数字化超声电源的研制 104. 基于ADC841单片机的防爆软起动综合控制器的研究105. 基于单片机控制的井下低爆综合保护系统的设计 106. 基于单片机的空调器故障诊断系统的设计研究 107. 单片机实现的寻呼机编码器 108. 单片机实现的鲁棒MRACS及其在液压系统中的应用研究 109. 自适应控制的单片机实现方法及基上隅角瓦斯积聚处理中的应用研究110. 基于单片机的锅炉智能控制器的设计与研究 111. 超精密机床床身隔振的单片机主动控制 112. PIC单片机在空调中的应用 113. 单片机控制力矩加载控制系统的研究 项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！单片机论文，毕业设计，毕业论文，单片机设计，硕士论文，研究生论文，单片机研究论文，单片机设计论文，优秀毕业论文，毕业论文设计，毕业过关论文，毕业设计，毕业设计说明，毕业论文，单片机论文，基于单片机论文，毕业论文终稿，毕业论文初稿，本文档支持完整下载，支持任意编辑！本文档全网独一无二，放心使用，下载这篇文档，定会成功！- 14 -