共查询到20条相似文献,搜索用时 62 毫秒
1.
包括数学规划、对策论、经济学和力学等应用领域中的某些问题,都可以转化成如下的线性互补问题: 相似文献
2.
3.
最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1. 相似文献
4.
5.
6.
7.
8.
9.
指出FLP问题的一种新的单纯形算法[1]中主要结论成立的适用条件,并给出了该适用条件不成立时,一般条件下的推广. 相似文献
10.
求解运输问题的一种新算法 总被引:6,自引:2,他引:6
本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijk-stra算法扩展到可能出现负边权的运输问题。与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时)。 相似文献
11.
部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。 相似文献
12.
13.
14.
Mathematical Notes - We introduce and study a new type of greedy algorithm, namely, projection greedy algorithms with respect to a given dictionary in a Hilbert space. We prove that these... 相似文献
15.
Mathematical Notes - A weak conical greedy algorithm is introduced with respect to an arbitrary positive complete dictionary in a Hilbert space; this algorithm gives an approximation of an... 相似文献
16.
基于垂岸式自动化集装箱码头不同装船周期出口集装箱堆场多贝位混合堆存、场桥大车在贝位间频繁移动取箱装船特点,考虑装船发箱时场桥移动等操作时间及翻箱取箱次数对出口箱装船效率和连续性影响,建立多贝位出口箱装船堆场翻箱模型,提出两阶段贪婪禁忌搜索算法,将翻箱规则嵌入算法中,有效限制算法时间和解空间增长速度。通过算例,将提出的翻箱规则与现有常见翻箱规则进行对比,验证模型及算法的有效性与实用性。结果表明,提出的模型和算法可以在合理的求解时间内输出较优的翻箱方案,减少装船时场桥发箱作业时间,提高装船作业效率。 相似文献
17.
排序的贪婪算法的参数上界 总被引:4,自引:0,他引:4
本文研究平行机排序中最著名的贪婪算法─LPT算法的性质.经典排序中机器随时可以开始加工.本文研究机器不都是从开始就可以加工,而是需要一个准备时间,也就是说本文研究各台机器最早可以开工的时间可以不同的同型号平行机(ideaticalParallel)的排序问题,分析LPT算法得到的近似解的参数上界. 相似文献
18.
《Optimization》2012,61(2):241-249
We show that the convex hull of the set of feasible solutions of single-item capacitated lot-sizing problem (CLSP) is a base polyhedron of a polymatroid. We present a greedy algorithm to solve CLSP with linear objective function. The proposed algorithm is an effective implementation of the classical Edmonds' algorithm for maximizing linear function over a polymatroid. We consider some special cases of CLSP with nonlinear objective function that can be solved by the proposed greedy algorithm in O ( n ) time. 相似文献
20.
S.J. Dilworth N.J. Kalton Denka Kutzarova V.N. Temlyakov 《Constructive Approximation》2003,19(4):575-597
Some new conditions that arise naturally in the study of the Thresholding Greedy Algorithm are introduced for bases of Banach spaces. We relate these conditions to best n-term approximation and we study their duality theory. In particular, we obtain a complete duality theory for greedy bases. 相似文献