共查询到17条相似文献，搜索用时 62 毫秒
1.
作为经典装箱问题的推广,有色装箱问题在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景.本文提出了有色装箱问题的一种新的近似算法--交叉装箱算法（简称JCBP）,该算法首先对物品按长度进行排列,再从两头交叉进行装箱.实验证明,该算法较其他算法有较好的装箱效果,并且很多情况下能达到最优解. 相似文献
2.
装箱问题是组合最优化中的一个著名的问题。本文给出了装箱问题的一类衍生问题——染色装箱问题的一个近似算法,并讨论了算法的近似比。 相似文献
3.
4.
一维装箱问题(Bin-Packing)是一个著名的NP难的组合问题,具有极其广泛的应用背景,受到了深入细致的研究,取得了许多好的成果.2004年孙春玲等1对一维装箱问题给出一个新的近似算法,称作交叉算法,证明该算法达到一维装箱问题的最好的近似值3/2. 相似文献
5.
给定物品系列,要求将所有物品装入到不同类型的箱子中,以实现从第一个箱子到最后一个箱子被使用的箱子的总尺寸最小化。本文用最坏情况绝对性能研究在线算法,对于两种箱子规格和,我们给出了一种最坏绝对性能比最多是2.75的在线近似算法。 相似文献
6.
用最坏情况绝对性能研究尺寸可变的装箱问题的在线算法,对于两种箱子规格a和b,给出了一种最坏绝对性能比最多是2.75的在线近似算法. 相似文献
7.
研究了一维装箱问题的在线近似算法,给出了一种新的半在线算法：随机适应算法（简称RF算法）,说明了RF算法的时间复杂度是O（n^2）,一般情况下的性能比〈1.75。 相似文献
8.
本文利用二分搜索法和时间表理论中LPT算法求解装箱问题的近似最优解;给出了一个直观性算法,并研究这个算法的最坏情形,最后说明此算法在某些方面优于著名的FFD算法。 相似文献
9.
通过设计一种适应度函数,利用分组遗传算法结合BF算法和FFD算法来对此适应度函数进行优化,从而求得一个优化的装箱结果。用C++实现该算法并对装箱实例进行仿真实验与比较,结果表明:在遗传算子的交叉操作过程中采用FFD+GGA的混合分组遗传算法是一种解决装箱问题的有效方法,在大部分情况下用很短的时间都可求得最优解。 相似文献
10.
11.
雷晓强 《云南民族大学学报(自然科学版)》2004,13(3):172-176
假设有p台计算机,n张载有信息的网页,其各网页的长度都与计算机和时间有关,现在的问题是,求一个安排,使这p台计算机能在最短的时间内下载完这n张网页.对于任意的一个非负整数k,该问题没有nk-近似算法,除非NP=P.当任务t在时刻i在处理机j上被开始执行时的加工时间l(t,i,j)∈{k1,k2},我们给出了该问题的一个近似算法. 相似文献
12.
对最大团问题的HEWN(hierarchicaledge-weightnetwork)算法进行了复杂性分析.首先通过分析HEWN的结构特点和所需进行的操作,设计了一种实现HEWN算法的数据结构,指出了在HEWN算法中HEWN的存储宜采用邻接多重表和二叉链表相结合的链表表示法,然后从HEWN的存储结构入手,剖析了HEWN的构造过程,在剖析过程中,通过与MCST(maximumcompletesub-graphtree)比较,指出了当2j>n时潜在的、指数的生成和修改GM的次数存在于HEWN算法中.因而,HEWN算法的时间复杂度是指数的,而不是O(n8.5). 相似文献
13.
研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况．先把该问题归结为图的顶点覆盖问题，它是一个NP完全问题；接着讨论了在网络拓扑是树的特殊情形下带权和不带权顶点覆盖问题的解，并给出了树结构上带权顶点覆盖问题的线性时间算法；然后在已有的一个近似比为2的算法基础上。结合树结构上不带权顶点覆盖问题的算法给出了图的不带权顶点覆盖问题的一个改进算法，最后用实验验证了改进算法能使观察者数目减小20％左右． 相似文献
14.
15.
将紧凸集上的集值映射变分不等式解的存在定理推广到非空闭凸集上，利用它建立了广义集值映射互补问题解的存在定理，并用单纯逼近给出了集值映射互补问题解的存在定理的一种构造性证明。 相似文献
16.
17.
求解Hamming距离下的最短路改进问题的一个近似算法 总被引：1，自引：0，他引：1
研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法. 相似文献