经典一维装箱问题的适应近似算法的研究大学论文

经典一维装箱问题的适应近似算法的讨论摘 要本文讨论经典一维装箱问题（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 algorithm’s capability excelled other any-fit approximation algorithm’s 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． 引言1．1 问题的提出装箱问题也就是把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品体积之和不超过箱子容量并使所用的箱子数目最少。其应用在实际生活中无处不在，货物装运，服装裁剪，以及计算机科学中的存储分配、共享资源调度、文件存储都是装箱问题在实际应用中的体现。例如某国际物流公司有一批固体货物要装进集装箱用船从广州运到美国。每个集装箱的规格都一样（体积均为 150 立方米），而每件货物体积不一定相同但其长宽高都小于集装箱的。问怎样的装箱方案最省钱，即所用集装箱最少？讨论装箱问题能够更好解决上述这些问题，有很大的经济效益。所以装箱问题有着广泛的应用背景，具有很大的讨论价值。但是装箱问题是 NP 难解问题[7]，这意味着该问题不存在在多项式时间内求得精确解的算法（假如 P≠NP）因此对装箱问题算法的讨论指的是对其近似算法的讨论，所谓近似算法即该算法可以求得与精确解接近的结果但不一定得到精确解。目前，已经提出了大量的近似算法，其中适应近似算法是目前时间复杂性比较低的一种近似算法。如下次适...