最小基数箱子覆盖问题及其启发式算法

研究了一个新颖的装箱问题，即最小基数箱子覆盖问题(Minimum Cardinality Bin Covering Problem)，证明了该问题是强NP-完备的；在物件大小满足一定的条件下，给出了一个时间复杂度为O(n)的启发式算。     

一维装箱问题的一个衍生问题——最小基数箱子覆盖问题

文章介绍一维装箱问题的一个衍生问题:最小基数箱子覆盖问题和它的一个启发式算法。     

最小费用箱子覆盖问题及其算法

提出了一种有实际背景的最小费用箱子覆盖问题──每个物品有长度和费用2个参数.针对局外最小费用箱子覆盖问题,给出了一个求解该问题的最坏情况渐近性能比为1/2算法C-FF1.同时给出了一个求解该问题的局内算法C-FF2,其绝对性能比为1/2,并证明了不存在绝对性能比大于1的算法.     

应用基因概率学习算法求解最小码覆盖问题

概述最小码覆盖问题，以及现有的几种求解最小码覆盖问题的计算机搜索算法．在基因概率学习算法(PBIL)的基础上，建立码覆盖问题的目标函数，引进启发式算子HF0，针对局部陷阱设计跳出策略，从而获得一种新的快速求解码覆盖问题的算法．     

染色装箱问题及其启发式算法

研究了装箱问题的一个新颖的衍生问题:染色装箱问题,即在装箱问题中,给每个物件指定一个颜色,要求每个箱子中所装的物件颜色各不相同,使得所需要的箱子数目尽可能少.该问题是通常装箱问题的一种推广.笔者给出了染色装箱问题的一个启发式算法,同时研究了只有两种颜色的染色装箱问题:即2-色装箱问题,并给出了一个最优算法.     

求解装箱问题的一种变长度染色体遗传算法

针对装箱问题提出了一种变长度染色体的改进遗传算法,并分析了其实现的具体方法和实现步骤.     

有舍弃的装箱问题及其启发式算法

设计了一种启发式算法——RCF算法来解决有舍弃装箱问题.实验证明,该算法与RFF3算法相比,在物体个数比较少(<200)的情况下,由于数据的随机性会出现比RFF3算法较好;在物体个数大于200的情况下,RFF3算法具有绝对的优势.因此,提出的RCF算法在物体个数比较少的情况下,有一定的应用价值.     

在线A形装箱问题: 模型及算法研究

A形装箱问题是由生产实际引发的一个新的数学模型,它是经典一维装箱问题的一种变形--每样物品有高度和半径两个参数.把装箱问题的经典算法推广到在线A形装箱问题,并分别从最坏情形分析与数值模拟两方面对算法进行了比较,得到了不同而且有趣的结果. 证明了 First Fit算法的渐近竞争比为2, 而其它在线启发式算法如Next Fit, Worst Fit, Best Fit(BF), Almost Worst Fit, Harmonic的渐近竞争比皆为无界; 通过数值模拟,在平均意义下BF的性质最好.     

多种物品三维装箱问题的一种启发式算法

针对多种物品单箱三维装箱的问题,设计了一种新的启发式算法.该算法基于"平面"和"块"的概念,采取树搜索策略,允许货物在任何可行方向上旋转,在保证箱空间利用率足够高的同时,满足货物摆放稳定性的要求.实验结果表明,该算法是解决此类问题的一种有效的方法.     

求解最小覆盖问题的快速近似算法的进一步研究

分析了已有求覆盖平面上给定的若干个点的尽可能小的圆的问题的算法。给出了一个新的求解最小覆盖问题的算法，其计算时间复杂度为平面上给定的点数量的线性函数，该算法已编程实现，通过几万例随机算例的实际计算比较，表明算法所得结果的平均精度比已有的各种快速近似算法所得的精度要高，而且具体每例所需的计算时间均比已有快速近似算法对应的计算时间要短。     

染色的装箱问题及其近似算法

给出了染色装箱问题和染色覆盖问题的数学描述,得到了给定颜色限制的染色装箱问题和染色覆盖问题的两个近似算法.     

集合覆盖问题降阶算法

集合覆盖问题是运筹学与计算机科学中的一个NP难题.首先将该问题转化为一个等价的二分图,给出该问题的上下界算法;接着给出该问题的数学性质,这些数学性质能降低问题的规模,加快算法的求解速度;然后将数学性质和上下界方法结合起来形成一个降阶算法,并给出了算法的时间复杂度分析.该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.最后通过多个示例进一步说明算法的原理及应用情况.     

度、半径约束最小生成树问题及其算法

提出了度、半径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.进一步给出了快速启发式求解算法,并分析了该算法的时间复杂性.分析和实例实验表明该算法具有良好的效果.     

Input Data Dependency of a Genetic Algorithm to Solve the Set Covering Problem

A genetic algorithm to solve the set covering problem proposed in the literature had some improvements which gave better solutions, i.e., better chromosomes in the first starting population, taking full account of domain specific knowledge with sound programming skill. We have further investigated the input data dependency of their genetic algorithm, i.e., the dependency on costs and density. We have found that for input problem data sets with densities greater than or equal to 3%, our genetic algorithm is still practical both in computing time and approximation ratio.