哈密尔顿回路问题的DNA表面计算模型

首次提出用DNA表面计算模型来解决无向图哈密尔顿回路问题。该模型基于哈密尔顿回路问题的解空间,将问题解空间的DNA分子固定在固体载体上,对其进行荧光标记,然后通过相应的生化反应筛选出哈密尔顿回路问题的所有解。与已有的哈密尔顿路径问题的其它模型相比,新模型具有错误率低,编码简易,读取方便等更好的性能。

有向哈密尔顿路问题的研究

DNA计算是在分子水平上进行的计算,与传统的基于电子计算机的线性计算系统相比较,具有如可并发计算、耗能量小等无法比拟的特点。目前的研究主要集中在一些特定问题上,如NP完全问题,而这些问题在电子计算机上需要指数时间。本文利用已有的Adleman实验[1]解决有向图哈密尔顿路问题,给出了剪贴计算模型的形式化模型,并从算法复杂性角度分析其复杂性。

匈牙利算法与分枝定界法解决调色问题之比较

通过实例分析了匈牙利算法和分枝定界法的算法特征和过程,讨论了以这两种算法求解具体优化问题时所要采取的算法策略.指出在实际应用算法时,根据问题的局部信息,模型与算法的选择是极其重要的,并进一步提出了借用分枝定界法处理哈密尔顿回路问题的设想.

图中含有k-因子的判定算法

本文依据文[3]已有的一个理论成果(定理1),给出了判定一个图是否合有k-因子的一个算法,同时对算法的复杂性作了分析,并示出了一些简单情况的结果。

基于分子生物技术的DNA计算系统

DNA计算是一种应用分子生物技术进行计算的新方法,DNA计算的2个主要特点是高度并行性和巨大的信息存储容量。为解决DNA计算初始化过程存在的问题,提出了数据初始化模型,保证了初始数据的完整性,减少了计算过程中参与筛选的DNA链的数量,提高了计算精度。针对生物实验反应时间较长、活性DNA材料成本高的现状,开发了DNA计算系统,通过仿真实验解决了哈密尔顿问题。

基于隶属云模型蚁群算法与LK搜索的TSP求解

提出一种求解TSP的算法,采用"问题无关的进化算法与问题相关的局部搜索相结合"的策略。采用基于云模型的蚁群算法来产生足够好的解;改进传统的LK算法,新加入5种搜索删除集与添加集元素的准则,以此细化搜索。将该算法用于求解TSPLIB中不同类型、城市数从48到33810内变化的TSP,比较该学派与其他学派算法的偏离率与运行时间,结果均显示该算法更优,有效求解了TSPLIB中的非对称TSP、哈密尔顿圈问题。

Y_3V_3-free图的闭包与稳定性

探讨了与无爪图相关且比无爪图更广的一种图类Y3V3-free图,构造了一种Y3V3-free的闭包,并证明了所构造的闭包具有保持周长稳定等性质且是唯一的.