NP完全

摘要： 近些年来,随着基因测序技术的继续发展与应用,大量不完整基因组片段的处理问题有待研究。同时由于目前大部分的生物学研究是基于基因组序列可以提供完整信息的假设,但通过生物测序技术获得一个完整的基因组序列仍是困难的。因此基因组重组问题在计算生物学领域愈发受到关注和研究,研究如何填充缺失基因组使其完整,具有重要意义。针对单面基因组片段填充算法,目前常采用最大化公共邻接数目的度量依据,是将缺失基因填充至不完整基因序列中得到填充后的重排列基因序列,使之与参照基因序列之间的新公共邻接数目最大。主要研究了基于contig(片段重叠群)的单面重复基因组填充问题,重点对该问题的现有算法在近似比、核心技术以及时间复杂度等多方面进行了对比分析与总结,并分别提出了各类算法的改进思路,有助于进一步研究基于contig的单面序列填充问题。

摘要： 随着物联网的不断发展,大量边缘设备的可信认证需要占用物联管理平台越来越多的计算与通信资源,传统方法难以在有限时间与资源约束下进行实时响应。将该问题建模为并发认证调度问题(CASP),并证明了它是NP完全的。首先提出了一个贪心算法(SJF),并证明了在某些场景下SJF具有近似比。随后将其扩展并提出了一个启发式算法(MBF)来解决一般场景下的CASP问题。实验结果表明:提出的算法能够取得比较好的效果,且在小规模时算法性能接近于最优算法。

摘要： 随着物联网的不断发展,大量边缘设备的可信认证需要占用物联管理平台越来越多的计算与通信资源,传统方法难以在有限时间与资源约束下进行实时响应。将该问题建模为并发认证调度问题(CASP),并证明了它是NP完全的。首先提出了一个贪心算法(SJF),并证明了在某些场景下SJF具有近似比。随后将其扩展并提出了一个启发式算法(MBF)来解决一般场景下的CASP问题。实验结果表明:提出的算法能够取得比较好的效果,且在小规模时算法性能接近于最优算法。

摘要： 伴随生物测序技术的不断发展,大量基因组片段的后续处理问题亟待解决.基因组片段填充是有效解决方法之一,受到广泛关注.基于普通序列的单面基因组片段填充问题是将缺失的基因序列填充到一个不完整基因组片段B中,得到B′,与完整的参考基因组A对比,使得A和B′之间的邻接数最大化.基于片段重叠群的该问题区别在于基因组片段通常由一组连续的片段重叠群(contig)构成,缺失基因只能在contig两端进行插入.针对这两个领域的相关问题进行深入研究,对已有算法及算法复杂性进行详细的分析与比较,为未来基因组片段填充问题的研究及生物测序技术的发展提供有价值的参考.

摘要： 最优技能集扩张问题是从一个已有技能集扩张为一个要求技能集,使得扩张过程的获取费用为最小.目前文献中已有基于整数规划的数值方法.本文建立有向网络的连接模型,并提出组合最优化的研究途径.主要结果是证明如下结论:1)问题是强NP-困难的;2)当中间顶点数是常数时,问题可在多项式时间求解;3)问题存在性能比为2的近似算法.此外,本文还提供精确算法(分枝定界算法)及启发式算法.

摘要： PQ-树是一种树状数据结构,用来表示元素排列集合.虽然消逝物种完整基因组序列具有不确定性,但是根据同源物种可以确定部分基因的相对位置,所以可以利用PQ-树来存储消逝物种的基因组.在生物学中,进化树用来表示物种之间的进化关系.当构建生物进化树时,叶子结点表示现存物种,其基因组用排列表示;内部结点为祖先物种,其基因组用PQ-树表示.为了确定物种间的进化关系,需要确定PQ-树可以产生的排列与已知排列之间的距离.以断点距离为标准,研究了p-PQ-树断点中心问题,即从给定PQ-树中产生一个排列,使之与给定的p个排列的断点距离之和最小.证明当p≥2时,p-PQ-树断点中心问题是NP完全的.当p=1时,p PQ-树断点中心问题是参数化可计算的,针对1-PQ-树断点中心问题,提出了时间复杂度为O(3Kn)的参数化算法,其中K为最优解的断点距离.

摘要： 该文提出了一种基于群体协作的计算模型。该模型首先将输入的数据单元建模成微观个体，然后基于求解目标设计个体间的协作规则，最后通过个体在协作过程中涌现出的宏观现象来得到全局最优解。通过运用群体协作模型求解具有NP-完全复杂度的最优图着色问题，结果表明该模型的性能优于若干启发式方法，并且得到如下结论：1)如果算法的动力学特征类似于混沌边缘现象，则算法能够在线性或亚线性时间复杂度求解问题。2)如果算法的动力学特征呈现出完全随机性或强收敛性，则算法将退化成蛮力搜索。%This study proposes a computing model based on group cooperation. The data unit of the input is first modeled as group individual, the cooperation rules between individuals are then designed based on the target of the problem. Finally, the problem’s global optimal solution is obtained through the emergence phenomenon of individuals’ cooperation process. By applying group cooperation model to solve graph coloring problem which has NP-complete complexity, it shows that the proposed model works better than several heuristic methods. Experimental results illustrate that: 1) if the algorithm’s dynamics exhibits the edge of chaos phenomenon, the algorithm can solve the problem in linear or sub linear time complexity; 2) if the algorithm’s dynamics is completely random or exhibits strong convergence, the algorithm degenerates into brutal force search.

摘要： 点覆盖问题是最重要的NP完全问题之一,也是近年来参数算法设计中研究得最多的问题之一。针对现有点覆盖近似算法的一些不足,基于点覆盖问题参数算法的进展,提出了该问题一个基于NT定理规约的2-近似算法。利用了参数算法中的核化技术对图进行化简,在剩余图上采用贪心策略来指导节点的选择,核化技术为算法提供了有效的近似度保障。为检验新算法性能,在不同类型的随机图上通过仿真实验比较了新算法和经典的基于匹配的2-近似算法。仿真实验结果表明新算法较基于匹配的2-近似算法有着明显的优势。

摘要： 多色点集划分研究如何将含有不同颜色点的平面划分为各个区域，每个区域中只包含一种颜色的点。这是计算几何中的一种组合优化问题。但是现有的多边形划分方式性能较差。为此，提出用直线来划分平面。针对平面上多色点集的直线划分，将其离散化，证明其可以被非确定性图灵机在多项式时间内判定。并将Max2SAT问题在多项式时间内归约到组合优化问题，证明多色点集直线划分为NP难，从而证明其是NP完全的。利用最优化版本的特有性质，运用贪心方法构造出多项式时间的近似算法，并L归约到Setcover问题，以此证明算法的近似比为O( lgn)。%Partitioning multi-colored point set into monochromatic parts is an optimization problem in computational geometry. It focuses on how to dissect the plan with polychrome points into regions with monochrome points. But the approach of partitioning with polygon cannot get good partition results now. This paper comes up with an approach of partitioning with straight line. This problem is discredited to prove that non-deterministic turing machine can decide this problem. It reduces Max2SAT problem to this problem in polynomial time,and proves that it is NP-hard. Then multi-colored point set is partitioned into monochromatic parts problem with straight line in NP-complete class. It gives an approximation algorithm for the optimization version by using L-reduction from Setcover problem, and proves the approximation ratio is O( lgn) .

摘要： 针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法.

摘要： 本文对服务组合问题进行规划建模,证明了该问题是NP完全的,提出了一种基于图的自动组合方法ASC-Graph, ASC-Graph分为组合规划图构造阶段和组合解搜索阶段.通过组合规划图构造,可在多项式级时间内判定服务组合问题的可满足性.在组合解搜索阶段,提出了一种启发式搜索策略。最后,通过模拟实验验证了ASC-Graph在解决大规模服务组合问题上的有效性.

摘要： 本文对服务组合问题进行规划建模,证明了该问题是NP完全的,提出了一种基于图的自动组合方法ASC-Graph, ASC-Graph分为组合规划图构造阶段和组合解搜索阶段.通过组合规划图构造,可在多项式级时间内判定服务组合问题的可满足性.在组合解搜索阶段,提出了一种启发式搜索策略。最后,通过模拟实验验证了ASC-Graph在解决大规模服务组合问题上的有效性.

摘要： 本文对服务组合问题进行规划建模,证明了该问题是NP完全的,提出了一种基于图的自动组合方法ASC-Graph, ASC-Graph分为组合规划图构造阶段和组合解搜索阶段.通过组合规划图构造,可在多项式级时间内判定服务组合问题的可满足性.在组合解搜索阶段,提出了一种启发式搜索策略。最后,通过模拟实验验证了ASC-Graph在解决大规模服务组合问题上的有效性.

摘要： 本文对服务组合问题进行规划建模,证明了该问题是NP完全的,提出了一种基于图的自动组合方法ASC-Graph, ASC-Graph分为组合规划图构造阶段和组合解搜索阶段.通过组合规划图构造,可在多项式级时间内判定服务组合问题的可满足性.在组合解搜索阶段,提出了一种启发式搜索策略。最后,通过模拟实验验证了ASC-Graph在解决大规模服务组合问题上的有效性.

摘要： 在Pandya提出的CTL*[DC]逻辑的基础上,对其语法和语义进行扩展,并对路径长度进行限制,定义了一个新的逻辑CTL*[k-QDDC],它可应用于实时系统的描述和验证.给出了在Kripke结构中直接验证CTL*[k-QDDC]逻辑公式在某状态是否成真的基本算法.在某些假设下,也证明了CTL*[k-QDDC]中的某个逻辑运算符的验证问题是NP完全的,这就说明CTL*[k-QDDC]的验证问题至少是NP难的.

摘要： 在Pandya提出的CTL*[DC]逻辑的基础上,对其语法和语义进行扩展,并对路径长度进行限制,定义了一个新的逻辑CTL*[k-QDDC],它可应用于实时系统的描述和验证.给出了在Kripke结构中直接验证CTL*[k-QDDC]逻辑公式在某状态是否成真的基本算法.在某些假设下,也证明了CTL*[k-QDDC]中的某个逻辑运算符的验证问题是NP完全的,这就说明CTL*[k-QDDC]的验证问题至少是NP难的.

摘要： 在Pandya提出的CTL*[DC]逻辑的基础上,对其语法和语义进行扩展,并对路径长度进行限制,定义了一个新的逻辑CTL*[k-QDDC],它可应用于实时系统的描述和验证.给出了在Kripke结构中直接验证CTL*[k-QDDC]逻辑公式在某状态是否成真的基本算法.在某些假设下,也证明了CTL*[k-QDDC]中的某个逻辑运算符的验证问题是NP完全的,这就说明CTL*[k-QDDC]的验证问题至少是NP难的.

摘要： 在Pandya提出的CTL*[DC]逻辑的基础上,对其语法和语义进行扩展,并对路径长度进行限制,定义了一个新的逻辑CTL*[k-QDDC],它可应用于实时系统的描述和验证.给出了在Kripke结构中直接验证CTL*[k-QDDC]逻辑公式在某状态是否成真的基本算法.在某些假设下,也证明了CTL*[k-QDDC]中的某个逻辑运算符的验证问题是NP完全的,这就说明CTL*[k-QDDC]的验证问题至少是NP难的.

摘要： 在网络中定位最优复制以最小化通讯代价.假定网络采用read-one-write-all策略来保证网络数据一致性,那么存在一个决定复制定位的最优化问题.提出了研究复制问题中读、写比率以确定最优化通讯代价.问题可转换成一个0-1线性规划问题,并将此问题扩展为一个p中值问题,可以证明这个问题是NP-complete的问题,并提出了一种多项式时间内的此问题求解算法.

摘要： 在网络中定位最优复制以最小化通讯代价.假定网络采用read-one-write-all策略来保证网络数据一致性,那么存在一个决定复制定位的最优化问题.提出了研究复制问题中读、写比率以确定最优化通讯代价.问题可转换成一个0-1线性规划问题,并将此问题扩展为一个p中值问题,可以证明这个问题是NP-complete的问题,并提出了一种多项式时间内的此问题求解算法.

摘要： 本发明公开了一种zif‑8纳米球同时负载Au NPs和Fe3O4 NPs的方法。具体步骤如下：(1)柠檬酸钠还原法制备13nm金纳米粒子，用聚乙二醇mPEG‑SH稳固；(2)铁(III)乙酰丙酮(Fe(acac)3)与油酸‑乙醇反应制备12nm油酸稳定的Fe3O4 NPs，用聚乙二醇mPEG‑COOH稳固；(3)将(1)与(2)同时加入到硝酸锌中，搅拌均匀，再加入二甲基咪唑，反应制备zif‑8同时负载Au NPs和Fe3O4 NPs的纳米球。通过本发明制备的zif‑8纳米球具有光热性能和磁共振成像作用，可以用于生物探针、磁靶向等多种用途，尤其适用于癌症的磁靶向给药和细胞内光热治疗。该方法获得的包埋两种纳米粒子于zif‑8中的技术易于控制载入的Au NPs和Fe3O4 NPs的量，产率高，可实现大规模制备。

摘要： 本发明提供了H‑Beta型分子筛在NPs检测或吸附中的应用和同时检测8种NPs的方法，涉及分析检测技术领域。本发明采用H‑Beta型分子筛作为样品前处理过程中新烟碱类农药(NPs)的吸附剂，能够实现对样品中NPs的特异性吸附，从而提高水以及蜂蜜中NPs检测的准确度、精确度和灵敏度；H‑Beta型分子筛的重复利用率高，能满足待测样品中8种NPs样品前处理以及检测的快速、准确、节约、重复性好的要求。通过高效液相色谱‑串联质谱检测进行检测。本发明提供的方法能够实现8种痕量NPs的精确检测，水中NPs的检出限＜0.1ng/mL，蜂蜜中NPs的检出限＜2.0ng/g。

摘要： 提供了用于求解NP难/NP完全问题的分级神经网络及其方法。在一些实施例中，所述方法包括：识别多个第二NP难/NP完全问题，其中，第二NP难/NP完全问题中的每一个与第一NP难/NP完全问题相似；识别针对第二NP难/NP完全问题的解；利用第二NP难/NP完全问题和所述解来训练深度神经网络；将第一NP难/NP完全问题提供给经训练的深度神经网络，其中，所述经训练的深度神经网络生成针对第一NP难/NP完全问题的初步解；以及将所述初步解提供给被配置用于执行能量最小化搜索的递归神经网络，其中，所述递归神经网络基于所述初步解生成针对所述问题的最终解。

摘要： 本发明公开了一种基于NP完全问题延伸的七爻排课方法，包括如步骤：获取学生的选科数据；创建数据模型；设置数据组，每个数据组填充入所有参与组班的学生；对数据组的学生进行组班，对数据组分别进行运算，根据数据组中行政班中的科目组合是否相同进行组班。本发明解决传统的算法难以实现排课的问题，通过建立数据组对选择不同科目的学生进行组班，实现合理的排课，有效的避免班级冲突，保证排课的高效性和合理性。

摘要： 本发明公开了一种基于NP完全问题延伸的七爻组班方法，包括步骤：获取组班基础数据，包括学生总人数与科目数量；获取组班约束条件；根据基础数据和约束条件，完成行政班组班。本发明能够实现合理的排班排课，有效的避免班级冲突，保证排课的高效性和合理性。

摘要： 在满足问题或任何决策或可简化为满足问题的其它问题内，本发明追踪蕴涵沿着其传播的路径，并且识别条件矛盾，并且随后将所述矛盾沿着所述蕴涵路径朝向假设或其它无前提断言移回，以排除所述矛盾。所述动作在比由现有方法引发的时间短的时间内完成，并且因此提供对解决这些问题的装置、软件或过程的性能改进。这些问题由涉及许多技术领域的装置、软件和过程解决，包括：矿石精炼；管道布线；纱线制造；面料切割；锯木；机械部件设计；数据处理系统的结构设计；电路或半导体掩模的设计和分析；集装箱、管道和画廊的检查和保护；传感器阵列操作；轨道卫星操作；数据压缩；化学分析；蛋白质的设计和分析。

摘要： 一种非诊断目的基于H‑rGO‑Pd NPs和Au NPs@rGO纳米材料检测GPC3的方法，采用电沉积将Au NPs@rGO修饰在SPE表面，通过吸附作用将GPC3Ab负载Au NPs@rGO/SPE表面；以H‑rGO‑Pd NPs纳米材料为载体，制备H‑rGO‑Pd NPs‑GPC3Apt检测探针，利用GPC3与GPC3Ab和GPC3Apt特异性结合，构建夹心型电化学适配体传感器；基于H‑rGO‑Pd NPs纳米拟酶材料催化银沉积作用放大检测信号，采用电化学工作站的DPV进行扫描，记录其峰电流，实现对GPC3的检测。

摘要： 本发明提供了H‑Beta型分子筛在NPs检测或吸附中的应用和同时检测8种NPs的方法，涉及分析检测技术领域。本发明采用H‑Beta型分子筛作为样品前处理过程中新烟碱类农药(NPs)的吸附剂，能够实现对样品中NPs的特异性吸附，从而提高水以及蜂蜜中NPs检测的准确度、精确度和灵敏度；H‑Beta型分子筛的重复利用率高，能满足待测样品中8种NPs样品前处理以及检测的快速、准确、节约、重复性好的要求。通过高效液相色谱‑串联质谱检测进行检测。本发明提供的方法能够实现8种痕量NPs的精确检测，水中NPs的检出限＜0.1ng/mL，蜂蜜中NPs的检出限＜2.0ng/g。

摘要： 本发明公开了一种具有较好灵敏度的P1NP检测试纸、P1NP检测试剂盒和检测方法。该P1NP检测试纸包括依次连接的标记垫、包被膜和吸水垫，标记垫上包被有P1NP荧光标记第一抗体，包被膜在沿层析方向上依次设有检测线和质控线，检测线上包被有P1NP第二抗体，质控线上包被有抗抗体，抗抗体特异性结合P1NP荧光标记第一抗体，检测线和质控线相互分离，P1NP荧光标记第一抗体和P1NP第二抗体与P1NP抗原的不同表位相结合。本发明所提供的P1NP检测试纸利用双抗体夹心层析检测原理，明显的提高检测的特异性，缩短检测所需时间。通过荧光标记第一抗体，能够明显的提高检测灵敏度。

摘要： 本实用新型公开了一种具有较好灵敏度的P1NP检测试纸、P1NP检测试剂盒和检测方法。该P1NP检测试纸包括依次连接的标记垫、包被膜和吸水垫，标记垫上包被有P1NP荧光标记第一抗体，包被膜在沿层析方向上依次设有检测线和质控线，检测线上包被有P1NP第二抗体，质控线上包被有抗抗体，抗抗体特异性结合P1NP荧光标记第一抗体，检测线和质控线相互分离，P1NP荧光标记第一抗体和P1NP第二抗体与P1NP抗原的不同表位相结合。本实用新型所提供的P1NP检测试纸利用双抗体夹心层析检测原理，明显的提高检测的特异性，缩短检测所需时间。通过荧光标记第一抗体，能够明显的提高检测灵敏度。