在量子计算机上求解0/1背包问题

在Ｇｒｏｖｅｒ算法和量子指数搜索算法的基础上，提出了一个量子算法去求解０／１背包问题。这个算法在没有使用任何可以提高搜索效率的经典策略的情况下，能够在Ｏ（ｃ＾２ｎ／２）步以至少１－１／２＾ｃ的概率求解问题规模为ｎ的０／１背包问题。  

调和装箱算法的平均性能分析

经典一维装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用 .该文系统地分析了在待处理的物品大小相互独立的情况下 ,L ee & L ee提出的调和近似装箱算法的平均性能 ;具体给出了在均匀分布下 ,调和算法平均性能比的值 ,并用实验验证了这些结果 .  

无线网状网容量分析与优化理论研究

首先对网状网容量估计与优化理论的技术难点进行分析,总结了其中的研究意义.根据国内外的研究现状,对干扰模型和调度模型进行总结与归纳,并对典型的优化模型进行了介绍.对目前容量优化算法常用的数学模型——规划模型、信息论模型、组合优化和随机过程模型进行了总结,提出了算法评价准则,对现有模型进行了点评.最后对未来的发展趋势提出了自己的观点.  

关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。  

0/1背包问题的量子算法

近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entan-glement),本文在量子环境下对0/1背包问题进行求解,介绍了量子算法的基本思想及相关概念。然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。  

基于图灵模型的P=？ NP问题分析

P=？NP问题是计算复杂性中的核心问题。2000年，美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型，对P=？NP问题的研究现状、P=NP／P≠NP 证明方法、NPC问题求解方法及研究进展进行阐述。  

PIM-SM组播中的RP动态重定位

构建共享组播树的首要问题是要决定共享根的位置,即中心选择问题,这是一个NPC问题。中心的定位及组成员的动态变化直接影响到组播树的结构,进而影响到组播的性能,故需要适时地调整中心的位置和重建组播树,即中心的迁移问题,如何在中心迁移过程中避免丢失数据和减少组播数据的冗余是需要解决的问题。在动态网络中,中心的选择与迁移是两个相互独立而又密不可分的问题,是重定位RP不可少的两个步骤,论文提出一种基于禁忌搜索的RP选择算法,继而提出一种新的RP迁移算法。仿真结果表明该算法在组播费用、端到端延迟和注册延迟方面都达到了较好的性能,且在迁移的过程中没有组播数据的丢失和冗余。