分子信标在一类特殊的整数规划问题中的应用

分子信标具有高灵敏度、易操作以及检测成本低等优点,因此广泛地应用于DNA计算中;此外,金(Au)表面对荧光团具有猝灭能力,可以取代猝灭基团。文章将分子信标固定在Au表面上,构建一种高灵敏的分子信标模型,该模型可用于求解一类特殊的整数规划问题。首先将变量映射成固定在Au表面上的分子信标,且设计出不同的输入链表示变量的不同取值;其次根据变量的取值向试管中加入不同的输入链;在输入链加入后,试管中出现不同荧光信号,然后根据荧光信号的显示来判断约束条件的可行解;最后搜寻问题的最优解。与传统的分子信标模型相比,该模型允许反复清洗过程,可用于大规模检测,更易于应用于疾病监测、医药检测中。     

双编码方式求解整数规划问题的DNA算法

DNA计算是以DNA分子作为数据的一种新型计算模式,在DNA计算中首要面对的问题是编码问题。文中提出了一种双编码方法,利用这种编码方法使得在DNA计算的读解过程类似于DNA测序过程,容易实现自动化操作。基于该编码方法所建立的DNA计算模型可用于求解整数规划问题,只需有限的几次PCK反应即可读取问题的可行解。与其他DNA算法相比,该算法具有操作简单、易于实现的优点。     

0-1整数规划问题的DNA四面体步行者计算模型

DNA折纸术是一种新型的自组装方法,广泛应用于DNA计算中。基于DNA折纸术设计了一个DNA四面体步行者,并将DNA四面体步行者应用于求解0-1整数规划问题。通过DNA四面体步行者的行走,来找出所有可能解。最后,通过DNA四面体步行者所携带的纳米金颗粒的个数来判断是否是0-1整数规划问题的可行解。该模型求解错误率低,具有很强的可控性和实用性。     

一类非线性整数规划问题的最优解

该文给出了一类非线性整数规划总是的最优解。     

一类最优投资问题的非线性整数规划

考虑了教育投资导出的一类非线性整数规划．讨论其解集的性质，给出了一个可行解是最优解的充要条件和求解方法，讨论了计算时间复杂性，最后给出了计算实例     

一类具有整数约束条件的数学规划问题的求解算法

给出了具有整数约束的数学规划问题的求解算法，而不论目标函数是线性函数还是非线性函数，此方法计算量比较小。     

求解一类整数规划问题最优解的算法

本文给出了求解一类整数规划问题所有最优解的两个算法．一个算法较为简单，其时间复杂性为O（n）,另一个算法求解较为快速，其时间复杂性为O（log n）.     

称球的整数规划问题

分而治之算法是数据结构中最大最小问题、排序问题的有效算法之一。它能够对一个问题很快地设计一种计算步骤进行计算从而解决问题，但是对于解决这些问题所需最少操作数这个问题，它并不能给出实质的解答。该文考察分而治之算法应用的一个问题并将它一般化，通过分析对这种更一般问题建立了求解该问题所需最少操作数的整数规划模型，通过求解该模型，能够得出解决这种更一般问题所需要的最少操作数。     

一类整数规划问题有唯一最优解的充要条件

给出了一类整数规划问题有唯一最优解的充要条件.并且当有多个最优解时,确定了此整数规划问题的最优解的个数.这解决了文献[1]提出的两个公开问题.     

一类非线性整数规划问题的切平面分支定界算法

针对一类非线性整数规划问题,提出了一个基于切平面的分支定界算法.在这个方法里,用切平面方程将非线性可行域线性化,同时在子问题上确定可行方向,生成切平面,切掉没有整数解的可行域,缩小了可行域,可以减少分支的次数,并进行了收敛性分析和证明.     

整数瓶颈问题的两个多项式算法

研究了一个特殊的整数瓶颈问题并给出了两个求最优解的多项式算法程序。通过对算例的分析可知该算法运行效率高。     

一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.     

整数约束分派问题的GAT算法

主要讨论整数约束的分派问题,以遗传算法为主体,结合模拟退火和禁忌搜索算法,构造GAT算法,对其进行求解,最后得到较好的结果.     

基于粘贴系统求解无向图最短路径问题的DNA计算模型

提出了用粘贴系统求解赋权无向图中固定端点最短路径的DNA算法。该算法首先将无向图中每条边用两条方向相反的有向边代替,将无向图转化为有向图,同时利用粘贴系统的巨大并行性得到两端点间的所有路径,最后通过探针、电泳等分子生物技术手段获得最短路径,并通过实例说明算法的可行性。     

图顶点着色问题的质粒DNA计算

图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。     

基于粘贴和删除系统求解旅行商问题的DNA算法

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的NP完全问题.粘贴和删除模型是DNA计算的两个基本计算模型.结合上述两个模型的优点,构造粘贴-删除模型,并利用该模型给出求解旅行商问题一种新的DNA算法.     

求解K-闭包问题的DNA算法

给出了解决K-闭包问题的DNA算法，进一步表明了用DNA计算来解决NP-完全问题是非常有前景的。     

基于DNA链置换的分子逻辑门计算模型

DNA计算是近年来的研究热点,分子逻辑门是DNA计算机体系结构和运算实现的重要基础。将DNA自组装与链置换技术和荧光标记相结合,在现有的链置换逻辑计算模型的基础上,构造了非门,与门,与非门,或门和或非门。可在室温下进行,减少了因复杂的生物操作步骤带来的误差。使用荧光检测来判断逻辑结果,操作简单,容易检测,且灵敏度高。     

从线性整数规划谈一维下料问题

一维下料问题是运筹学的一个经典NP-hard问题,在生产中普遍存在．优化下料可以提高原材料的利用率, 是企业增加经济效益的途径之一．从线性整数规划开始讨论了下料问题的各种模型,提出了一些需要改进的问题, 介绍了目前该问题研究的热点．     

最大匹配问题Tile自组装模型

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