共查询到20条相似文献,搜索用时 406 毫秒
1.
2.
利用一种称为平衡技术的新方法解答划分问题。证明若划分问题存在满足条件的子集,则该子集一定是平衡集,仅对平衡集进行枚举即可解答划分问题。若划分问题给定集合中每个元素的长度都被一个常数M所界定,结合动态规划技术且仅考虑平衡集,解答划分问题的时间复杂度为O(nM),此算法在时间效率上对现有算法有较大改进。 相似文献
3.
4.
软硬件划分是嵌入式系统设计过程中一个关键环节,已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛,且找到的全局最优解的质量不佳等问题,提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的0-1背包问题,在求解背包问题的算法基础上用贪心算法构造出初始划分解;然后,对代价函数的解空间进行合理的区域划分,并基于划分的区间设计新的代价函数,采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明,与目前已有的类似改进算法相比,新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右,具有高效性和实用性。 相似文献
5.
给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。 相似文献
6.
软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。 相似文献
7.
有限差分法是求解静态场边值问题的一个非常有效的数值解法,它是将求解区域划分为有限个网格点,用一组差分方程代替原来一组微分方程.该方法求得的是近似解而不是精确解.求解区域内网格划分大小关系着计算的精确度,网格尺寸划分越小,计算精确度越高;反之,精确度越低.本文运用MATLAB语言使得有限差分法求解区域内电势分布的解法变得简单、易行,摆脱了传统方法使用C语言较复杂的缺陷.通过仿真验证了算法和程序的有效性. 相似文献
8.
基于遗传算法的集合划分问题求解 总被引:1,自引:0,他引:1
集合划分问题是组合优化领域中有着广泛应用基础的著名问题,属于NP难问题.通过引入精英策略提出对遗传算法的改进,并为了能把遗传算法应用到集合划分问题,对数学模型进行了等价变换.针对集合划分问题,设计出一种高效的基因表示,避免了组合优化中处理约束条件的麻烦.解决了传统二进制基因编码无法精确适应离散优化问题,首次提出一种离散编码解决方案.最后,使用Visual C 6编程实现,取得较好的结果. 相似文献
9.
10.
本文介绍了量子算法的基本思想及相关概念。在量子环境下利用划分原理,不断地对态矢划分子空间,然后减小不满足条件态矢的概率幅,而增大满足条件的概率幅,最后将以大的概率得到所求的解。从而可以把时间复杂度由传统的指数时间求解的问题变成在量子计算机中能在多项式时间能求解的问题,在量子物理环境下它能在多项式时间内求出子集和问题(背包问题)的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。 相似文献
11.
广义Hanoi塔问题的动态规划算法 总被引:2,自引:0,他引:2
基于动态规划算法思想,深入分析了广义Hanoi塔问题动态规划分割点的特征,给出动态规划分割点的简单计算公式,使得动态规划算法转化为一个非常简单的递归算法,由此可以迅速产生广义Hanoi塔问题的最优移动序列,从而彻底解决了广义Hanoi塔问题的最优移动序列问题. 相似文献
12.
This paper describes a vectorized algorithm for the partition problem, a famous NP-complete problem. A set of partition problems that required 518 seconds to be solved on a VAX/8550 computer would require only 2 seconds on the Cyber 205 under the vector mode. A partition problem with n equal to 1000 was solved in only 6.34 seconds. 相似文献
13.
14.
数据不规则问题并行计算的负载平衡策略的研究 总被引:2,自引:0,他引:2
讨论以边缘通信为特征的数据不规则问题并行计算的静态负载平衡策略。从图论的角度讨论了静态负载平衡问题,给出三个优化目标,即点集等分,最短通路和通信量最小。对于以边缘通信为特征的一般数值计算问题,论述了二维问题正方形划分总通信量最小、并行效率最高,三维问题立方体划分总通信量最小、并行效率最高的结论。基于以上结论和实际课题特点,提出一种一维优先的规则分块算法和基于自动重分块的不规则分块算法相结合的方法。实验证明,该方法实现简单,能够处理不同规模的数据不规则问题,达到较优的负载平衡和较高的通信效率,提高并行程序的整体效率. 相似文献
15.
16.
霍红卫 《计算机工程与科学》2000,22(4):40-42
关系最粗粒度的划分问题PCPP在并发系统的验证方面起着重要的作用。本文提出了RCPP问题的一种有效的并行算法,其中假设标号转移系统中有m个转移和n个状态,利用m/n^∈个CREW处理器算法所需的运行时间为O(n^1+∈)(对于任意固定的∈〈1)。 相似文献
17.
针对离散事件系统, 本文主要研究计算最优拟同余关系时减少时间复杂度的算法. 基于Paige & Tarjan提出且Fernandez修改的、可有效计算最粗粒度划分问题的算法, 本文给出一种时间复杂度为O(mlog n)的计算最优拟同余关系的算法. 该算法适用于离散事件系统比较复杂, 尤其是可观事件很少的情况. 与Ramadge和Wonham提出的时间复杂度为O(mn)的算法相比, 该算法计算过程耗时较短. 本文还讨论了计算拟同余关系的边界情况的改进方法. 仿真结果表明所提出算法的有效性. 相似文献
18.
基于划分的蚁群算法求解货物权重车辆路径问题 总被引:2,自引:1,他引:1
考虑单产品分销网络中的车辆路径问题(VRP:vehicle routing problem).与以往诸多研究不同的是,建立了一种带货物载重量的VRP模型(weighted VRP),即车辆在两个顾客之间行驶时的载重量也作为影响运输费用的一个因素考虑.因此,需求量较大的顾客拥有较高的车辆运输优先权.在分析了问题性质的基础上,提出一种基于划分策略的蚁群算法PMMAS求解货物权重车辆路径问题,并与其他常用的启发式算法进行比较分析,表明了算法的有效性. 相似文献
19.
Solving the minimum bisection problem using a biologically inspired computational model 总被引:1,自引:0,他引:1
The traditional trend of DNA computing aims at solving computationally intractable problems. The minimum bisection problem (MBP) is a well-known NP-hard problem, which is intended to partition the vertices of a given graph into two equal halves so as to minimize the number of those edges with exactly one end in each half. Based on a biologically inspired computational model, this paper describes a novel algorithm for the minimum bisection problem, which requires a time cost and a DNA strand length that are linearly proportional to the instance size. 相似文献
20.
通过引入虚拟的质量保证协议(SLA)服务条款,提出网络中形式化的设备位置问题,并根据网络特点改进了现有的静态局部优化算法,证明了在常见的分区低服务质量敏感类型的k median问题和低服务质量敏感类型的UFL问题中的近似度上界。测试结果表明改进后的算法在较小增加现有静态算法近似度的情况下运算速度有较大的提高。 相似文献