DPBD——设计一类强NP-Complete问题近似算法的有效方法

本文针对一类强NP-Complete问题近似算法的设计问题,提出一种通用的设计策略DPBD,它通过一局部近似算法而获得一全局近似算法,并保证精度在一定范围内.最后,本文将DPBD应用于一著名的NP难度问题:平面Covering问题,对方法的有效性给予了证实.

基于粒子群优化算法在NP难问题中的应用研究

为解决NP难问题中算法应用领域划分问题,分别运用不同算法对不同问题规模的TSP问题进行求解,寻求最优路径规划.采用随机数据来最大化模拟实际情况,设置了5、10、15、20、30和100个随机城市坐标点,分别采用PSO算法、C-PSO算法、GA算法和ACO算法进行求解,求解一条经过各城市且一次的旅行最低费用的路线,分析比较四种算法的鲁棒性与实效性.结果表明:基于C-PSO算法在NP难问题中的具有良好鲁棒性和较短的运行时间,在问题规模小时,可以采用PSO算法和ACO算法;在问题规模大时,可以采用C-PSO算法.

基于DNA链置换反应网络求解0-1背包问题

目的基于DNA链置换的化学反应网络可以作为一种有效的编程语言来解决各种数学问题,而0-1背包问题是一个经典的NP问题。为了求解0-1背包问题。方法提出利用DNA链置换反应网络,并利用Visual DSD设计仿真实验。结果通过加权、求和和阈值3个反应模块进行求解,最后由输出的单链DNA来表达结果。由于浓度的检测存在一定误差,使用带有荧光分子的单链DNA输出表达操作结果。最后,使用DSD仿真软件得到变量转换模块相对应的链置换反应网络图、变量仿真图以及阈值比较图。模型表明,该算法能够有效降低0-1背包问题的复杂度,并且具有较高的求解精度和稳定性。结论所提出的模型进一步丰富了DNA计算,并拓宽了DNA链位移的计算宽度。

求解最小支配集问题的禁忌遗传混合算法

将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优。

P与NP问题研究

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

电力系统NP难问题全局优化算法的研究

通过对现有的 NP难问题求解方法的分析 ,结合非确定性图灵机理论 ,提出基于随机化技术的方法是求解 NP难及 NP完全问题惟一有效途径的猜想。在现有的随机化方法中具有多点搜索特性的遗传算法具有最强的全局搜索能力 ,其局部精细寻优能力差的缺陷应通过专门的局部优化算法来补偿 ,即利用具体问题的特点开发面向问题的遗传算法。提出了开发新的高效全局优化算法的指导思想 :多点随机化全局搜索策略 +面向问题的局部寻优算法 =最有效的全局优化算法。

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

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

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

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

遗传算法用于NP完全问题的求解

讨论了如何利用遗传算法求解布尔表达式的可满足性问题 ,并给出该结果对求解其他NP完全问题时的应用 .

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

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

一个正则NP-完全问题及其不可近似性

通过一个适当的归约变换,可以将一个CNF(conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性。带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满足性和计算复杂性。极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足。借助此临界特性,给出了一个从3-CNF公式到正则(3,4)-CNF公式的多项式归约转换。这里,正则(3,4)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4。因此,正则(3,4)-SAT问题是一个NP-完全问题,并且MAX(3,4)-SAT是不可近似问题。

CAM中一类新的NP完全问题

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

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

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

d-正则(k,s)-SAT问题的NP完全性

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.

两个分批排序问题的NP-完备性证明

讨论了单台与两台批处理机上的、目标函数均为加权总完工时间的分批排序问题.用整数背包问题具体证明了这两个问题的NP-完备性.

求解Covering问题的拟物方法——NP难度问题的一个处理途径

本文提出的算法模拟了由万有引力和屏蔽现象所引起的力学过程.这种拟物的方案可为许多NP难度的问题得出有价值的近似算法.该算法对拟物类型的选择与现代递归论中的有穷损害优先方法的精神是一致的.

粮库PWSN部署中NP-Hard问题的研究

以无线传感器网络在粮库中的应用为例,将传感器节点部署中出现未覆盖区域问题归属为NP-Hard问题.结合近似算法、Bidding协议、Voronoi diagrams等方法,对粮库PWSN部署中的NP-Hard问题进行了较深入的研究,对解决粮库无线传感器网络的覆盖问题提出了新思路.

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

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

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

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

几个多面体网格剖分问题的NP难度证明

主要讨论了两类多面体网格剖分问题——网格表面单调剖分和地形多面体剖分.首先研究了判定一个多面体表面能否被剖分成k个单调片的问题,通过构造与SAT问题(satisfiability problem)相应的几何模型,证明出该判定问题是NP完全的,而与之对应的最优剖分问题是NP-hard的.然后将证明方法推广到地形多面体剖分的问题:将一个带洞多面体或者简单多面体剖分成最小数量的地形多面体,这两个问题都被证明是NP-hard的.