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

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

最小基数箱子覆盖问题

最小基数箱子覆盖问题,是在物件大小满足一定的条件下的装箱问题．给出了一个时间复杂度为O（n）的启发式算法．     

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

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

集合覆盖问题的一种启发式算法

给出了完备策略的概念，并提出了一个求解集合覆盖问题的启发式算法，对该算法的合理性、时间复杂性以及精度进行了分析。用该方法可以求解其它的NP困难问题。     

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

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

箱子装载问题的算法研究

1　引言　　设有ｎ件物品 ,每件物品的体积分别为ｓ1,ｓ2 ,… ,ｓｎ,且 0 <ｓｉ≤ 1(ｉ =1,2 ,… ,ｎ) .现有一批箱子 ,每只箱子的容量为一个单位 ,现在的问题是能够容纳这ｎ件物品的箱子至少需多少只 ?此问题为著名的ＮＰ复杂问题 ,迄今在多项式时间内尚无求解的办法 .但可用近似算法求解 ,使结果接近最优解 .对于此问题 ,有 4种流行的求解算法 :( 1)最先匹配法 (ＦｉｒｓｔＦｉｔ ,ＦＦ) ;( 2 )最优匹配法 (ＢｅｓｔＦｉｔ ,ＢＦ) ;( 3)最先匹配递减法 (ＦＦＤ) ;( 4 )最优匹配递减法 (ＢＦＤ) .这 4种算法的时间复杂度均为Ｏ(ｎ×ｌｏｇ(…     

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

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

基于MVD模式矩阵的多值依赖最小覆盖算法研究

给出了基于MVD模式矩阵的多值依赖公理系统及定理,根据这些定理,给出了基于MVD模式矩阵的多值依赖最小覆盖算法。     

单机总误工问题的分解启发式算法

为了解决单机总误工问题,提出了一种分解启发式算法。该算法是将解决这一问题最好的优化方法(Lawler分解算法)和非常有效的启发式算法(MDD)有机结合,在每一次迭代过程中均利用MDD算法估计Lawler分解算法中不同分解位置对应的误工,确定具有最大加工时间的工件在获得最小总误工的分解位置处加工。从理论上证明了该算法得到的排序结果优于MDD排序,仿真实验也表明该算法得到的结果99%以上为最优排序,而且可以求解多达1000个工件的问题。该算法以较短的时间获得了接近最优排序的结果,算法性能优良。     

一种噪声启发式聚类算法

启发式聚类算法的搜索空间中布满了局部极小值陷阱,从而使得算法容易过早收敛而无法获得高质量聚类结果.文章给出了一种噪声启发式聚类算法NHCA (Noising Heuristic Clustering Algorithm),该算法在搜索空间中增加一组由强至弱的噪声来扩大启发式搜索的局部范围,以保持搜索空间的多样性,达到避免局部极小值影响和提高聚类质量的目的.大量实验结果表明,噪声法对提高启发式聚类算法质量是十分有效的.     

覆盖平面上给定点集的最小凸多边形的算法

研究求覆盖平面上给定的若干个点的最小凸多边形的算法．给出了两种算法，讨论了算法的基本思想，描述了算法步骤，得出了算法的时间复杂度．结果表明，算法的平均计算时间复杂度为平面上给定点的数量的线性函数，即为Ο（ｎｍ），在最坏情况下可为Ο（ｍ２）     

带权PLA折叠问题及其启发式算法

本文将可编程逻辑阵列（ＰＬＡ）的折叠问题推广到行列折叠点间带权的一般情况，对这个ＮＰ－完全问题给出三个启发式算法，其中两个为贪心类算法，另一个是利用独立集的启发式算法，分析了各个算法的复杂性。     

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

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

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

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

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

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

基于神经网络的逻辑最小造价覆盖算法

提出一种基于神经网络求解逻辑综合中最小造价覆盖问题的优化算法。首先给出了最小造价覆盖问题与能量函数的映射关系，并以此构造了改进的两级Ｈｏｐｆｉｅｌｄ网络模型。然后利用该网络的动态特性，求出最小造价覆盖问题的最优解。最后对算法进行了分析和小结。     

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

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

求一般图的最小顶点覆盖集问题的混合贪婪算法

现有的求一般图的最小顶点覆盖集近似算法或者近似比较高,或者为降低复杂度限制了图的规模,或者算法搜索过程中盲目性大.根据顶点的度特点及贪婪法的思想,提出了邻接度数、覆盖边等主要概念,并在此概念的基础上设计了混合贪婪算法.该算法设计思路清晰,容易理解,易于编程实现,且在最坏情况下的时间复杂度为O(|V|2),执行效果较好,性能近似比不大于4/3,接近已知的可能的近似比下界1.166 6,低于2005年认为最低的近似比1.361,是图的最小顶点覆盖问题算法的一个较好的补充.     

Flow shop排序问题F2|prmu|∑ωjCj的一个启发式算法

给出Flowshop排序问题F2|prmu|∑ωjCj的一个启发式算法,其最坏情况的界为2,且是紧界.此外,还讨论了它的三种多项式可解的条件.