首页 | 官方网站   微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
背包问题属于著名的NP完全问题,在信息密码学领域和数论研究中具有极重要的应用。分枝限界算法对于某些背包实例的求解表现了较好的性能,但其在最坏情形下的时间复杂性为O(2^n)。Horowitz和Sahni利用分治方法,提出了著名的二表算法,算法的时间和空间复杂性被分别降至O(n2^n/2)和O(2^n/2)。虽然二表算法是迄今为止串行求解背包问题最有效的算法,但对于实践应用中维数稍大的问题实例,该算法仍难在合理的时间内对其求解。  相似文献   

2.
背包问题无存储冲突的并行三表算法   总被引: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)的计算时问求解背包问题的无存储冲突并行算法。  相似文献   

3.
将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.  相似文献   

4.
针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用 个处理机、 的时间、 的空间求解背包问题 ,根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。  相似文献   

5.
背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O(n2)。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O(√N/M)步完成对规模为n的背包问题求解(M是解的数目),而基于原始Grover算法的背包问题量子计算算法计算复杂度为O(√N/M),成功率是50%~100%。  相似文献   

6.
背包问题是计算机算法研究中NP完备类的一个困难问题.使用传统的优化方法在求解较大规模的背包问题时.都存在计算量大、迭代时间长的缺陷。为了克服传统优化方法的不足,提高求解的速度和精度,将人类繁育方式引入遗传算法中,形成一种求解背包问题的改进遗传算法(IGA)。介绍算法的基本思想以及使用该算法求解背包问题的方法.并通过实例证明该方法的可行性和有效性。  相似文献   

7.
基于分治的背包问题DNA计算机算法   总被引:9,自引:2,他引:9  
如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2q/2),其中q为背包问题的维数.与最近文献结论进行的对比分析表明:算法将求解背包问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.  相似文献   

8.
李肯立  赵欢  李仁发  李庆华 《软件学报》2007,18(6):1319-1327
将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.  相似文献   

9.
高维空间球集的覆盖问题是指对高维空间中多个球构成的集合S,构造一个直径最小的球来覆盖S中所有已知球。本文提出了球集直径的概念,给出求解球集直径的1/3~(1/2)近似算法。基于此算法求解球集实例集合S的初始核心集,进而给出高维空间球集覆盖问题的1+ε近似算法,算法时间复杂度为O(nd/ε+d2/ε3/2(1/ε+d)lg1/ε)。算法保证核心集中球的个数为O(1/ε),与S中球的个数和空间维数无关。  相似文献   

10.
一种带修复函数的QGA及其在背包问题中的应用   总被引:1,自引:0,他引:1  
朱筱蓉  张兴华 《计算机应用》2007,27(5):1187-1190
提出了一种带修复函数的量子遗传算法来求解背包问题。该算法采用量子比特概率编码方式构造染色体,由量子旋转门操作实现种群进化。在求解背包问题时,采用修复函数来修正不可行编码。文中给出了该算法的具体实现方法和流程,并用几个典型背包问题实例对其进行测试,结果表明带修复函数的量子遗传算法在求解背包问题时,综合性能优于传统遗传算法。  相似文献   

11.
为了设计一种具有低成本、低功耗、易操作、功能强且可靠性高的煤矿井下安全分站,针对煤矿安全生产实际,文章提出了采用MCS-51系列单片机为核心、具有CAN总线通信接口的煤矿井下安全监控分站的设计方案;首先给出煤矿井下安全监控分站的整体构架设计,然后着重阐述模拟量输入信号处理系统的设计过程,最后说明单片机最小系统及其键盘、显示、报警、通信等各个组成部分的设计;为验证设计方案的可行性与有效性,使用Proteus软件对设计内容进行仿真验证,设计的煤矿井下安全监控分站具有瓦斯、温度等模拟量参数超标报警功能和电机开停、风门开闭等开关量指示功能;仿真结果表明:设计的煤矿井下安全监控分站具有一定的实际应用价值.  相似文献   

12.
In modern service-oriented architectures, database access is done by a special type of services, the so-called data access services (DAS). Though, particularly in data-intensive applications, using and developing DAS are very common today, the link between the DAS and their implementation, e.g. a layer of data access objects (DAOs) encapsulating the database queries, still is not sufficiently elaborated, yet. As a result, as the number of DAS grows, finding the desired DAS for reuse and/or associated documentation can become an impossible task. In this paper we focus on bridging this gap between the DAS and their implementation by presenting a view-based, model-driven data access architecture (VMDA) managing models of the DAS, DAOs and database queries in a queryable manner. Our models support tailored views of different stakeholders and are scalable with all types of DAS implementations. In this paper we show that our view-based and model driven architecture approach can enhance software development productivity and maintainability by improving DAS documentation. Moreover, our VMDA opens a wide range of applications such as evaluating DAS usage for DAS performance optimization. Furthermore, we provide tool support and illustrate the applicability of our VMDA in a large-scale case study. Finally, we quantitatively prove that our approach performs with acceptable response times.  相似文献   

13.
《Information & Management》2016,53(6):787-802
Discrepant technological events or situations that entail a problem, a misunderstanding or a difficulty with the Information Technology (IT) being employed, are common in the workplace, and can lead to frustration and avoidance behaviors. Little is known, however, about how individuals cope with these events. This paper examines these events by using a multi-method pragmatic approach informed by coping theory. The results of two studies – a critical incident study and an experiment – serve to build and test, respectively, a theoretical model that posits that individuals use a variety of strategies when dealing with these events: they experience negative emotions, make external attributions, and adopt engagement coping strategies directed at solving the event, eventually switching to a disengagement coping strategy when they feel they have no control over the situation. Furthermore, users’ efforts may result in ‘accidental’ learning as they try to overcome the discrepant IT events through engagement coping. The paper ends with a discussion of the results in light of existing literature, future opportunities for research, and implications for practice.  相似文献   

14.
Kim  K. H. 《Real-Time Systems》2004,26(1):9-28
Distributed real-time simulation is a young technology field but its practice is under increasing demands. In recent years the author and his collaborators have been establishing a new approach called the distributed time-triggered simulation (DTS) scheme which is conceptually simple and easy to use but widely applicable. The concept was initiated in the course of developing a new-generation object-oriented real-time programming scheme called the time-triggered message-triggered object (TMO) programming scheme. Some fundamental issues inherent in distributed real-time simulation that were learned during recent experimental studies are discussed along with some approaches for resolving the issues. An execution engine developed to support both the TMOs engaged in control computation and the TMOs engaged in DTS is also discussed along with its possible extensions that will enable significantly larger-scale DTSs.  相似文献   

15.
Zusammenfassung Mit zunehmender Größe der Softwaresysteme verschärfen sich die für die Software-Herstellung typischen Probleme: Beherrschen großer Objektmengen, Erhalten der Systemkonsistenz, Kontrolle der ständigen Änderungseinflüsse und Gewährleisten einer langen Lebensdauer. Die Disziplin Konfigurationsmanagement bildet den methodischen Ansatz, diese Probleme besser zu beherrschen. Software-Konfigurationsmanagement faßt die Herstellung von Softwaresystemen als eine Abfolge von kontrollierten Änderungen an gesicherten Zwischen- und Endergebnissen auf. Dargestellt werden die Objekte und Funktionen des Software-Konfigurationsmanagements sowie die hierfür in großen Software-Projekten benötigten Methoden, Instanzen und Hilfsmittel.  相似文献   

16.
正http://www.zju.edu.cn/jzus http://www.springerlink.com Aim The Journals of Zhejiang University-SCIENCE(A/B/C)are edited by the international board of distinguished Chinese and foreign scientists,and are aimed to present the latest developments and achievements in scientific research in China and  相似文献   

17.
正Brain-machine interfaces(BMIs)aim at building a direct communication pathway between the brain and an external device,and represent an area of research where significant progress has been made during the past decade.Based on BMIs,mind information can be read out by neural signals to control  相似文献   

18.
正http://www.zju.edu.cn/jzus http://www.springerlink.com Aim The Journals of Zhejiang University-SCIENCE(A/B/C)are edited by the international board of distinguished Chinese and foreign scientists,and are aimed to present the latest developments and achievements in scientific research in China and overseas to the world’s scientific circles,especially to stimulate  相似文献   

19.
20.
正http://www.zju.edu.cn/jzus http://www.springerlink.com Aim The Journals of Zhejiang University-SCIENCE(A/B/C)are edited by the international board of distinguished Chinese and foreign scientists,and are aimed to present the latest developments and achievements in scientific research in China and overseas to the world’s scientific circles,especially to stimulate  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号