DNA芯片组技术及其在解决NP问题中的应用

为了用DNA并行算法解决实际应用中的一个NP问题——图的四着色问题,基于先进的DNA计算理论、DNA芯片技术、数据库技术,提出了DNA芯片组技术的概念;通过解决一个极大平面图(包括外边界的中国地图)的四着色问题,阐述了DNA芯片组技术的具体操作步骤;对生化实验进行计算机模拟并对数据库进行分析与处理,得到了所有的可行着色方案,从而验证了DNA芯片组技术在解决NP问题中的巨大应用能力.

基于强化学习的一类NP问题求解算法

Agent强化学习是机器学习的一个重要分支。阐述了Agent强化学习算法的基本理论,建立了求解类货郎担等NP问题的数学模型,给出了Agent强化学习算法解决这类问题的框架和基本方法,并运用该方法成功地解决了一个赛程安排问题,较传统方法有一定的改进。

关于相对化的P与NP问题的若干研究

研究相对化的Ｐ＝？ＮＰ问题，提出了矛盾天书、相对天书和绝对天书的概念，证明了这些天书的客观存在性，并具体地构造了一个矛盾天书和一个ＮＰ集类之外的相对天书．结论对利用现有关于相对化Ｐ＝？

浅谈故障树NP问题的处理

由于故障树分析中存在NP困难,虽然目前计算机在运算速度和存储能力等方面都有了迅速发展,但是对于大型故障树的分析困难还是存在.本文主要研究在进行故障树分析(Fault Tree Analysis,FTA)时NP问题的处理.对于大型故障树的分析采用可选的两条途径,即对于有大量重复事件的故障树分析采用早期不交化、模块化和转移事件来缩小故障树的分析规模;而对于没有重复事件的大型故障树就采用顶点分割和转移事件来缩小故障树规模.经分析处理后,故障树的规模呈指数减小.

一个NP问题的近似算法

对程序排课问题的近似算法进行了探讨 ,提出了一种实用的近似算法 ,可使程序排课问题得到相当程度的解决。

P与NP问题研究

P与NP问题被列为七大世界数学难题之首,由于其相关概念抽象而复杂,许多该领域的学生学者,对其相关概念的理解存在谬误,不少已发表的研究论文都体现了这一谬误。用中文通俗讲解到底什么是P和NP问题以及它们的关系,透过抽象的定义揭示其本质。列举一些科研论文上常见的对P和NP问题理解上的谬误,通过分析揭示其错误实质。同时并对解决这一问题可能的研究方法作一综述,对研究前景做一展望,为在该方向上学习和研究的学生学者,提供有价值的参考。由于文中包括:对复杂抽象的概念进行通俗而深入的剖析,对已有的研究进展进行摘要概括,对未来可能的研究方法和研究路线进行综述和分析,故能对该领域的研究者在概念的正确把握、文献的查阅和研究方向的选择上提供助益。

浅谈NP问题

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

解决NP问题的DNA编码技术

NP问题是密码学中的一个难题,用DNA计算解决NP问题是目前DNA密码研究的一个热点。文章阐述了DNA编码问题及约束条件,归纳出用DNA计算解决NP问题的基本步骤,分析了Adleman解决哈密尔顿回路问题的实验中DNA编码的质量,提出了可选的更好的编码,并总结了目前DNA编码研究中存在的问题。

NP问题的通用多项式算法

由于NP问题存在通用多项式算法,所以NP问题就是一种P类问题.这种P类问题不仅大量存在于各种计算领域,而且确实有可能用非确定性方法一次给出正确答案.这种非确定性方法就是符合最短路线选择定理和最短路线构造定理的计算方法.

基于NP问题的计算机算法思想研究

随着科技的发展越来越迅速,计算机技术也得到了非常大的提高,而其中在NP问题方面,相关的学者也做出了很多的讨论,NP主要是指非确定性多项式,而在这个过程当中,如果这项问题遇到很多困难的话,那么该算法就会很容易的检查出,并且给出相关的方法。文章将针对于这项算法在计算机中的应用目前存在的各类问题提出一些自己的想法,相关的工作人员可以基于这项情况进行简单的探讨和研究,并且促进我国计算机算法的进一步发展。

基于NP问题的机巡计划编排研究

目前大部分电网公司仍采取“人巡+机巡”协同的定期巡检的方式来维护输电线路。定期巡检中机巡计划仍以人工编排为主,耗费大量人力、物力。为解决上述问题,综合各个地市年度机巡作业需求设计机巡计划调度方案模型,实现机巡计划的自动智能编排。

分布式蚁群算法在求解NP问题中的应用研究

集合覆盖问题已被证明是一个NP完全问题，现在所有的NP完全问题，没有多项式时间算法求解。目前为集合覆盖问题的主要的近似算法，复杂或大型集合覆盖问题，现有的算法很难达到理想的优化效果。蚁群算法是基于群体智能的进化算法为基础的小说，关注个体的蚂蚁之间的合作，利用信息素正反馈机制，具有很强的寻找更好的解决方案的能力。蚁群算法已成功地应用在许多复杂的优化问题，其优化能力提供了一种新的思路来解决集合覆盖问题。蚁群算法具有耗时长、易陷入局部最优解的缺点。

并行计算解决部队铁路梯队装载NP问题应用研究

梯队装载问题是铁路军事运输中的典型NP问题。在分析铁路军事运输梯队装载问题的基础上,提出以长度为基本数据,以军列换长最小和使用车辆总数最少为目标的装载优化模型,证明了该问题是NP完全问题。针对普通计算机求解梯队装载问题计算能力不足的实际,引入并行计算技术,用并行全枚举法进行求解数学模型。最后通过实例分析,验证了算法的可行性和有效性。

特征统计算法及其在NP组合优化问题上的应用

特征统计算法是为了解决复杂多极值优化问题而开发的一种新的全局优化算法。为了检验该算法的性能,应用它在一类具有代表性的NP组合优化问题-旅行商问题(TSP)上作了计算。结果发现,该算法虽不是专为TSP问题而开发,却在该问题上取得了很好的结果。所得到的结果表明,特征统计算法可以作为解决这类NP组合优化问题的一个新的途径。

关于相对化的P=?NP问题的注记

问题P=?NP在相对化后随外部信息集的不同可能有相反的答案.本文得出如下进一步的结果:1.存在着无穷个集合S_1,S_2,…,这些集合的复杂度依次严格上升,并且在它们分别地作为外部信息集合,能交替地使命题P=NP和P≠NP,相对比;2.存在着在NP类之外的递归集A,使得P=NP等价于P^A=NP^A.

NP完全问题研究及前景剖析

P vs.NP是理论计算机领域最重要的课题之一,而其中的核心是NP完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是:NP、NP完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P与NP关系的误读,NP问题研究方向的误导等.本文分析了这些谬误,并揭示了相关概念的实质.通过不同角度多方位分析,对NP完全问题可能的解决途径和研究方向,提供了启发式思路.

一个NP─完全问题的求解复杂性剖析

本文提出一个构造的ＮＰ完全问题ＲＨＣ并证明其ＮＰ完全性。在此基础上，通过分析通用图灵机带头移动的次数，讨论了通用图灵机上任一求解ＲＨＣ的算法的复杂性。分析结果揭示了在简单计算模型（定义见正文）上寻找一个对满足ＲＨＣ的任意输入，而不是对某些特殊实例都能正确求解的算法的困难性。根据本文的讨论，我们认为，给出本文分析的严格论证或许只是时间问题。

CAM中一类新的NP完全问题

本文提出了计算机辅助制造(CAM)中的一类作业调度问题并证明了它的NP完全性。

DNA计算方法在求解NP完全问题中的应用

DNA计算是应用分子生物技术进行计算的新方法.本文主要介绍了DNA计算的基本思想及解决NP完全问题的DNA模型,讨论了目前DNA计算存在的问题和今后的发展方向.

一种三值逻辑的NP完全问题与判定问题

本文建立了一种三值逻辑——中介逻辑的三值语义,证明了其命题演算MP与MP的可满足问题是NP完全的且其谓词演算(带或不带等词)MF,MF与ME的判定问题是算法不可解的。