共查询到18条相似文献,搜索用时 140 毫秒
1.
基于0-1背包问题的讨论 总被引:12,自引:0,他引:12
简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0-1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间,发现模拟退火算法是相对最优的算法。 相似文献
2.
林鑫 《计算机技术与发展》2005,15(10)
简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0-1背包问题,给出了具体的算法描述和求解过程.对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间,发现模拟退火算法是相对最优的算法. 相似文献
3.
4.
物化视图是数据仓库中提高查询效率的有效方法,物化视图选择问题是数据仓库设计时期最重要的决定之一。通过研究和实验,提出了一种结合迭代改进算法和模拟退火算法的两阶段优化算法,用于解决物化视图的选择。理论分析和实验结果表明,该算法有效地解决了传统模拟退火算法收敛过慢的缺点,并且其解的质量逼近经典贪婪算法。 相似文献
5.
6.
一种改进的贪婪式覆盖算法 总被引:1,自引:1,他引:1
文中对覆盖算法进行了介绍和分析,提出了一种基于贪婪算法思想的改进的覆盖算法,称之为贪婪覆盖算法。通过对覆盖初始中心选择方式的改进,减少覆盖数量。通过实验,对比目前已有的几种实现方法,覆盖数量有了较大的下降,明显提高了分类识别的速度。 相似文献
7.
针对基本类电磁机制算法不能够有效解决离散型的背包问题,提出了一种贪婪离散类电磁机制算法。首先,提出一种交叉操作;然后,利用提出的交叉操作对基本类电磁机制算法中的合力计算公式和粒子移动方法进行修改,使其能够适用于离散型问题;最后,引入贪婪算法的机制来处理经过类电磁机制算法迭代得到的解,使这些解满足背包问题的约束条件。通过对3个经典的背包测试问题进行的测试结果表明:该算法可以解决离散型的背包问题,并且具有较优的求解性能。 相似文献
8.
迭代贪婪算法是一种具有较强局部搜索能力的元启发式算法,但由于传统迭代贪婪算法搜索范围过大,搜索效率有限,为了进一步提升传统迭代贪婪算法的搜索能力,考虑到阈值接受算法具有能缩小搜索范围的特点,提出了一种改进的迭代贪婪算法解决流水车间预制生产的订单接受与调度问题。该改进算法是在破坏原调度序列后加入一种基于构造启发式规则的重建策略,并结合阈值接受算法的自适应接受准则用以跳出局部最优。经大量仿真实验结果显示,与传统迭代贪婪算法、禁忌搜索算法以及遗传算法对比,改进的迭代贪婪算法具有更好的求解质量和鲁棒性。 相似文献
9.
单人负责多台机器的单一工序作业车间场景中,工人由于重复操作机器而产生学习效应.针对考虑依赖工件位置学习效应的单人单工序作业车间最小化最大完工时间的调度问题,建立一种混合整数规划模型.为解决该问题,设计一个考虑学习效应的贪婪算子,利用该算子构造两种贪婪算法,并提出一种基于贪婪的模拟退火算法.为衡量混合整数规划模型、贪婪算法和基于贪婪的模拟退火算法的性能,设计两种规模问题的数据实验.通过实验得出:现代混合整数规划模型求解器可以解决机器数量和工件总数量乘积小于75的小规模问题;基于贪婪的模拟退火算法求解此问题具有有效性,适用于各种规模的问题;间隔插入贪婪算法解决此问题速度较快,效果良好,可以应用于需要快速求解的场景. 相似文献
10.
本文简述无线传感器网络近代发展的情况。详细介绍了以地理位置信息为基础的贪婪路由算法。分析了现有的贪婪算法存在的不足,着重讨论了贪婪路由算法中通信空洞现象各种不同的解决方法。基于以上分析对地理位置信息在无线传感器网络路由协议的发展提出看法。 相似文献
11.
12.
Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches. 相似文献
13.
针对多背包问题最优解的求解,设计了一种新的价值密度;在此基础上结合传统的贪心算法,提出了一种求解多背包问题的混合遗传算法。该算法采用整数编码,并采用轮盘赌选择方法,对背包资源利用不足的可行解进行修正处理,对不可行解进行修复处理。并在大量的数值实验的基础上,将该方法与传统方法及简单遗传算法进行比较,实验结果表明,该混合遗传算法提高了问题求解的速度和精度,有一定的优越性。 相似文献
14.
15.
杨智应 《计算机应用与软件》2009,26(3)
Franco等给出一个基于平均度数的最小3-击中集问题的贪心算法,并给出算法返回击中集规模的上界.首先将其算法推广成为求解最小k-击中集问题的贪心算法HGREEDY1(A,C),并类似地给出算法返回击中集规模的上界;然后给出基于最大度数的贪心算法HGREEDY2(A,C),并证明算法HGREEDY2(A,C)在给定条件下返回的击中集规模上界优于算法HGREEDY1(A,C);另外设计了用于求解最小k-击中集的随机算法RH(A,C),并对其性能进行平均分析;在此基础上设计一个求解最小k-击中集的随机近似算法并讨论其性质. 相似文献
16.
Recently, iterated greedy algorithms have been successfully applied to solve a variety of combinatorial optimization problems. This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. Main contributions of this paper can be summed up as follows. We propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We employ and adopt well-known speed-up methods from the literature for both insertion and swap neighborhood structures. In addition, an iteration jumping probability is proposed to change the neighborhood structure from insertion neighborhood to swap neighborhood. Generally speaking, the insertion neighborhood is much more effective than the swap neighborhood for the permutation flowshop scheduling problems. Instead of considering the use of these neighborhood structures in a framework of the variable neighborhood search algorithm, two powerful local search algorithms are designed in such a way that the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By doing so, it is shown that some additional enhancements can be achieved by employing the swap neighborhood structure with a speed-up method without jeopardizing the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the proposed iterated greedy algorithms are tuned through a design of experiments on randomly generated benchmark instances. Extensive computational results on Taillard’s well-known benchmark suite show that the iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Ultimately, 85 out of 120 problem instances are further improved with substantial margins. 相似文献
17.
18.
目前最小测试集的最佳近似比是贪心算法的2 ln n+o(1).这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.72 ln n,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数. 相似文献