摘要：本文证明了为任意模板集设计存储访问无冲突非线性存储方案的问题是一个 np完全问题 .另外设计同时满足存储访问无冲突和互联网络无冲突的存储方案设计问题也是一个 np完全问题 .

摘要：np完全问题在科学研究和实际应用中广泛存在,仅仅指出它们的难解性是不够的,更重要的是正面寻求解决方法,其中的关键是算法的设计与分析。

摘要：简要回顾了网络编码的理论研究,阐述了网络编码优化问题研究的重要意义.在介绍网络信息流模型的基础上,针对优化问题的陈述、特点和解法,结合最新的研究成果进行了综述.根据优化目标的不同,优化问题可分成4类:最小花费组播,无向网络的最大吞吐率,最小编码节点、编码边,基于网络编码的网络拓扑设计.归纳了问题的求解性质,对其中的(线性或凸)规划问题总结了求解的一般方法,对np完全问题讨论了最新的启发式算法及其设计难点.同时,展望了未来的发展方向.

摘要：随着DNA计算机研究的不断深入,如何克服DNA生物计算中穷举法的极限已成为DNA计算研究的重要内容之一.为设计可扩展的子集和问题DNA计算机算法,文中将Aldeman-Lipton模型的操作与粘贴模型的解空间结合,引入荧光标记和凝胶电泳技术,通过设计DNA并行搜索器,提出一种求解子集和问题的DNA计算机模型和算法.与已有文献结论的对比分析表明:文中算法在保持多项式生物操作复杂性的条件下,将穷举算法中的DNA分子链数从O(2n)减少至O(1.414n),其中n为子集和问题的维数.因此,文中算法理论上在试管级生化反应条件下能将可破解子集和公钥的维数从60提高到120.

摘要：讨论了如何将邻域搜索与遗传算法相结合求解流水车间调度问题 ,提出了一种邻域结构 ,使之更适合求解流水车间问题 ;设计了一种基于扩展采样空间的混合式遗传算法的框架 。

摘要：二维不规则形状物体的自动最优布局是属于np完全的组合优化问题 ,使用传统的方法很难得到满意解答 .文章针对该问题提出了一个基于进化计算的算法 ,并以服装计算机辅助设计为例表明基于进化计算的算法卓有成效地应用到自动布局问题 .为了得到关于问题的自然和有效的编码 ,将问题变换为一种与之等价的关于多边形的运动规划问题 ,根据问题的特性设计了算法的 3个重要算子 .在解的解码和评价过程中则综合地利用了已有的最优算法 .

摘要：３－ＳＡＴ问题有一个非常奇妙的相变现象．对于固定的变量数Ｎ，合取范式的可满足概率随着子句个数Ｋ的变化而发生剧烈的变化；当Ｋ≈４．３＊Ｎ时，可满足概率急剧地从１变为０．相变现象决定了问题的难易分布，对于快速求解算法的设计有着非常重要的意义．文章着重讨论了ＳＡＴ问题的更一般形式，即２－３－ＳＡＴ问题的相变现象．研究了相变点处的２－子句和３－子句个数的关系，发现了２－子句和３－子句在约束能力意义下的当量关系。

摘要：针对诸多优化下料方法片面追求高原材料利用率,而对实际切割加工成本考虑不足的现状,提出一种既维持高原材料利用率又使下料方案可制造性好的一维优化下料方法.下料方案的可制造性从切割方式种类数和每种切割方式中套裁零件种类数两方面来衡量,基于此提出了非定长优化和定长优化相结合的两阶段一维优化下料方法,并采用两阶段列生成算法实现.最后通过实例验证了文中方法的实用性和有效性.

摘要：Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现:模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n^2n,求解成功率由0.5n0增加至0.5n^0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.

摘要：Tile自组装模型凭借其自组装、可编程等特性在解决np问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型,该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息,其次通过Tile分子自组装操作生成最大匹配问题解空间,最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析,并通过实验模拟论证了模型的有效性和正确性.