排序方式: 共有45条查询结果,搜索用时 0 毫秒
1.
Abstract DNA computing was proposed for solving a class of intractable computational problems, of which the computing timewill grow exponentially with the problem size. Up to now, many achievements have been made to improve its performance and increase itsreliability. It has been shown many times that the surface-based DNA computing technique has very low error rate, but the technique hasnot been widely used in the DNA computing algorithms design. In this paper, a surface-based DNA computing algorithm for minimal ver-tex cover problem, a problem well-known for its exponential difficulty, is introduced. This work provides further evidence for the abilityof surface-based DNA computing in solving NP-complete problems. 相似文献
2.
研究了被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况.先把该问题归结为图的顶点覆盖问题,它是一个NP完全问题;接着讨论了在网络拓扑是树的特殊情形下带权和不带权顶点覆盖问题的解,并给出了树结构上带权顶点覆盖问题的线性时间算法;然后在已有的一个近似比为2的算法基础上。结合树结构上不带权顶点覆盖问题的算法给出了图的不带权顶点覆盖问题的一个改进算法,最后用实验验证了改进算法能使观察者数目减小20%左右. 相似文献
3.
根据图着色问题的特征,提出了求解图着色问题的双目标模型;设计的有效、简洁的杂交算子和变异算子,均直接产生可行的后代个体;理论分析表明算法以概率1收敛到问题的最优解集.对标准算例进行了仿真实验,结果表明,双目标进化算法可以获得问题高质量的解,即对图进行着色所使用的颜色接近图的色数. 相似文献
4.
具有固定顺序的重新排序问题 总被引:1,自引:1,他引:0
在生产实际中经常会出现顾客订单不同时到达的情况,为了保证先来顾客的需求和工件本身的要求,往往是先安排好的工件保持相对顺序不变,使其与后来顾客的工件重新排序.本文着重研究了这种使先来顾客的工件保持相对固定顺序,在有限错位限制的条件下使总目标函数值最优的重新排序问题。 相似文献
5.
The delay-constrained least-cost multicast routing problem is introduced and then a related genetic algorithm is proposed. Finally, simulation results are shown to prove that the genetic algorithm is fast and effective. 相似文献
6.
分装式流水作业加工模型是从生产实践中提炼出来的一种新的加工模型,是流水作业与复合并行机加工方式的组合.在已证明该问题一般情况下是NP-完全问题,没有多项式算法的基础上,进一步研究了TMF排序问题在特殊情况下的多项式时间算法和一般情况下的启发式算法. 相似文献
7.
Tile自组装模型凭借其自组装、可编程等特性在解决NP问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型,该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息,其次通过Tile分子自组装操作生成最大匹配问题解空间,最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析,并通过实验模拟论证了模型的有效性和正确性. 相似文献
8.
江厚元 《贵州工业大学学报(自然科学版)》1993,(3)
本文研究了带有资源约束的两台机器流水作业中的最小排序长度问题,并证明了[4,5]中提出的F2|pmtn、res 111|C_(max)是强NP—困难的。 相似文献
9.
本文定义了一个内存工作区处理语言MPL,并提出了用于描述语言的形式化方法,作为示例,文中最后给出一个程序部分正确性的验证提纲。 相似文献
10.
王晓东 《福州大学学报(自然科学版)》1999,27(5):10-13
讨论了图算法中若干NP完全问题在所给的图是一棵树时的特殊情形- 利用树结构的前序编号表示法提出了解树的最大独立集问题、最小顶点覆盖问题和最小支配集问题的线性时间算法-在渐近意义下这些算法都是最优算法 相似文献