共查询到19条相似文献，搜索用时 117 毫秒
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.
求解Hamming距离下的最短路改进问题的一个近似算法 总被引：1，自引：0，他引：1
研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法. 相似文献
12.
提出一种新的求解旅行商问题的混合遗传算法。该混合遗传算法充分利用2-opt和3-opt局部搜索能力,有效地弥补了具有较强全局搜索能力的遗传算法在局部搜索方面表现出来的缺陷。实验结果表明,该混合算法性能显著优于遗传算法。 相似文献
13.
下模集函数最大值问题属于NP-难问题,难以得到有效的求解方法。针对这一情况,运用概率分布方法,给出了求解该问题的一种近似算法,并证明算法的性能保证为1／3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问题提供新的思路。 相似文献
14.
15.
基于非线性互补问题(NCP(F))的等价变形,构造非线性互补问题的一个光滑逼近函数,把非线性互补问题等价变形为非线性方程组问题加以求解,建立了求解非线性互补问题的一个光滑逼近算法,并在一定条件下证明该算法的全局收敛性. 相似文献
16.
大型复杂网络的可靠性分析都是NP难题。寻求计算简单、准确的近似算法更具应用价值。结合因子分解定理、网络简化规则、定界思想、二分决策思想,给出了一种计算网络两端可靠度的近似算法。通过实例分析表明,使用该算法进行可靠性分析是有效的。 相似文献
17.
给出了求解最小-最大圈划分问题的一种新的近似算法,该算法的近似比为305p-2,时间复杂性为O（n^4）． 相似文献
18.
次模集函数的最值问题在组合优化问题中有广泛应用,次模集函数的增减性对该问题的分析具有一定的简化作用．给出了求解非减次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证． 相似文献
19.
为长方体装箱问题的求解提出了拟人算法,旨在将几千年以来中国人的有关生活经验利用西方的数学工具加以形式化并且提高一步.本算法在当今可得的计算环境下,对于现实生活中常遇到的长方体packing问题能够得出合适的空间布局,其空间利用率在已公开发表的国际文献中属于领先的水平. 相似文献