共查询到17条相似文献,搜索用时 656 毫秒
1.
本文给出了满足三角不等式的货郎担问题的并行启发式算法,在SIMD CREV PRAM并行机上该算法使用O(n^3/log^2n)台处理器需O熄log^2n)时间,这里n是给定城市的个数,因而该并行算法是最优的。 相似文献
2.
并行归并排序算法 总被引:3,自引:0,他引:3
来智勇 《计算机研究与发展》1995,32(6):46-49,54
构造效率为O(1)的并行算法是一个引人注目的问题。[1]和[2]分别提出了并行度为O(logn)和O(n^1/2)的、效率为O(1)的并行排序算法。本文提出一种新的并行排序算法,其效率为O(1),而并行步数小于[1]和[2]的算法的并行步数。经过改进后,在保持效率为O(1)的情况下,可进一步将并行度扩大到O(n^1/2log n)。 相似文献
3.
近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entan-glement),本文在量子环境下对0/1背包问题进行求解,介绍了量子算法的基本思想及相关概念。然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。 相似文献
4.
本文介绍了0-1背包问题的一种深度优先(DFS)算法,并用概率分析方法给出了算法的时间复杂度和空间复杂度,一般情况下,其时间复杂度在O(n)到O(1.5)之间。工程管理上的一类整数规划问题都可归结为0.1背包问题。 相似文献
5.
背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O(n2)。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O(√N/M)步完成对规模为n的背包问题求解(M是解的数目),而基于原始Grover算法的背包问题量子计算算法计算复杂度为O(√N/M),成功率是50%~100%。 相似文献
6.
几何算法求解货郎担问题 总被引:5,自引:1,他引:4
周培德 《计算机研究与发展》1995,32(10):63-65
本文提出求解货郎担问题的一种几何算法。它的时间复杂性为:O(n^3/m)次比较,O(n^2)次乘法,其中n,m分别是点集的点数和凸包顶点数。 相似文献
7.
本文介绍了采用氧瓶燃烧-离子选择性电极测 物中的碘含量,在由0.01molLKNO3-0.09mol/LVc混合溶液中,I^-的标准曲线在1.0*10^-2-1.5*10^-7mol/L范围内呈线性,电极斜率为56.32mV/pI(20℃)。Vc改善了I^-1在溶液中的稳定性并提高了方法的准确度。用于智力碘口嚼片中微量碘的分析,其相对标准偏差和回收率分别为2.24%(n=6)和97.2%,符合向量 相似文献
8.
0-1背包问题是组合优化中经典的NP难题,在蚁群算法的基础上结合量子计算提出一种求解0-1背包问题的量子蚁群算法。算法采用量子比特表示信息素,用量子旋转门来更新信息素。大量数据实例的比较测试表明,算法可有效提高蚂蚁算法的性能,减少搜索时间,具有更好的全局寻优能力。 相似文献
9.
本文介绍了量子算法的基本思想及相关概念。在量子环境下利用划分原理,不断地对态矢划分子空间,然后减小不满足条件态矢的概率幅,而增大满足条件的概率幅,最后将以大的概率得到所求的解。从而可以把时间复杂度由传统的指数时间求解的问题变成在量子计算机中能在多项式时间能求解的问题,在量子物理环境下它能在多项式时间内求出子集和问题(背包问题)的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。 相似文献
10.
11.
将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义. 相似文献
12.
背包问题无存储冲突的并行三表算法 总被引:4,自引:0,他引:4
背包问题属于经典的NP难问题,在信息密码学和数论等研究中具有极重要的应用,将求解背包问题著名的二表算法的设计思想应用于三表搜索中,利用分治策略和无存储冲突的最优归并算法,提出一种基于EREW-SIMD共享存储模型的并行三表算法,算法使用O(2^n/4)个处理机单元和O(2^3n/8)的共享存储空间,在O(2^3n/8)时间内求解n维背包问题.将提出的算法与已有文献结论进行的对比分析表明:文中算法明显改进了现有文献的研究结果,是一种可在小于O(2^n/2)的硬件资源上,以小于O(2n/2)的计算时问求解背包问题的无存储冲突并行算法。 相似文献
13.
14.
0-1背包问题是计算机科学中一个经典问题,0-1背包问题是一个最优化问题。因其结构简单,可扩展性强,可作为其他问题的子问题,因此通过对其研究可以解决更为复杂的优化问题。本文概述了两种求解0-1背包问题的算法设计方法,并对两种算法进行了分析和比较。 相似文献
15.
0/1背包问题是计算机科学中的一个经典问题。动态规划法,递归法,回溯法是求解该问题的三种典型方法,使用这三种方法求解0/1背包问题,并对各算法进行了理论分析。用不同规模的0/1背包问题对三种算法进行测试,比较它们的运行时间,发现测试结果与其理论分析结果相符.最后指出就求解不同规模的0/1背包问题而言各算法的优劣。 相似文献
16.
17.
用动态规划算法求解0-1背包问题的时空复杂度为O(nC)。这个空间复杂度在求解大规模问题上是不可接受的。从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法。为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题。该新混合算法的时间复杂度为O(nC);它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O(「n/d?+C),其中d为计算机字长。实验结果表明,混合算法的工作效率与理论分析相同。 相似文献