共查询到19条相似文献,搜索用时 109 毫秒
1.
最小顶点覆盖问题的DNA分子算法 总被引:2,自引:0,他引:2
最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。 相似文献
2.
停机位分配问题的顶点着色模型及算法 总被引:1,自引:0,他引:1
给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解. 相似文献
3.
4.
5.
6.
提出了一种用于中药配方优化的DNA算法,该算法基于质粒DNA技术。首先将中药配方优化问题转化为求无向图的最大权团问题:选取6种具有抑制大肠杆菌生长功效的中药作为图的顶点,分别做抑菌试验,将它们的抑菌圈直径作为顶点的权。然后两两配对进行抑菌试验以确定它们在图中是否有边连接。这样构造了一个顶点赋权的无向图,这个图的最大权团具有最大的抑菌效力,也是这些中药的最佳配伍。求图的最大权团是一个典型的NP.完全问题,而DNA计算具有求解该问题的能力。该方法的提出探讨了DNA计算实用的可能性。 相似文献
7.
8.
9.
研究了点簇聚合的目标顶点位置的计算问题。当计算过程中得到的目标顶点不在小单元之内,或者虽然在小单元之内,但目标顶点的位置不能唯一确定时,则将求解目标顶点的问题转化为求解带约束的二次优化问题。此二次优化问题的解既能保证目标顶点位于小单元之内,在位置上又最接近该点簇的重心。实验结果表明,该算法的时间效率类似于Lindstrom的算法,但在简化质量上要优于后者。 相似文献
10.
用混合遗传算法求解图的邻强边着色问题 总被引:1,自引:0,他引:1
图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。 相似文献
11.
车辆路径规划问题及其求解方法研究进展 总被引:21,自引:1,他引:21
对车辆路径规划问题(Vehicle Routing Problem,VRP)领域的研究进行综述,根据目前的研究状况对该问题进行分类;分析该问题的图模型和数学模型两大类模型各自的优缺点;分四大类讨论求解该问题的算法:精确算法(exact algorithm),构造启发式算法(constructive heuristic algorithm),改进启发式算法(improving heuristic algorithm),和亚启发式算法(meta-heuristic algorithm)。评迷各类算法适用的问题求解阶段以及各自的优缺点;探讨国内在VRP领域的研究成果。在此基础上,对求解该问题的方法进一步的研究方向做了展望。 相似文献
12.
模式发现是计算生物学一个重要的研究方向,但目前的大部分算法还不能保证获得最优的模式。将模式发现问题转化成层次图的路径搜索问题,推导了针对三个序列片段相似性关系的判据,以其作为剪枝规则提出并实现了一种深度优先的穷举搜索算法:判据搜索算法(CriterionSearchAlgorithm,CRISA)。理论分析表明,对于绝大多数模式发现问题,CRISA具有多项式的计算时间复杂度和线性的空间复杂度。对仿真的和实际的DNA序列数据的测试表明,CRISA能够快速而完全地识别出序列中所有的模式,并且获得了优于其它算法的总体评价。 相似文献
13.
边连通度问题的三维DNA图结构解法 总被引:1,自引:0,他引:1
针对求边连通度这一难解问题,提出了三维DNA图结构算法。该算法利用k臂DNA这一特殊的分子结构构建了相应的图结构,通过相关的限制性内切酶处理和凝胶电泳分析来确定图的边连通度。通过探讨算法的可行性,基于目前的实验室技术给出了算法的具体分子生物学操作步骤。指出这一DNA结构可直观地反映图结构,易于建立图论模型。结论显示,该算法可以直观有效地求解边连通度,用于解某些难解问题有着特殊的优越性。 相似文献
14.
考虑存在通讯时延,在有向通讯拓扑结构下研究多Euler-Lagrange系统的协调跟踪控制问题。仅有部分跟随者可以获得静态领航者信息。对每一个跟随者设计了一种分布式观测器,以获得领航者的状态量。针对系统模型具有非线性不确定性和外部扰动情况,基于神经网络方法提出了两种分布式自适应协调控制律,分别使每一个跟随者对领航者的跟踪误差最终有界和渐近收敛到零。运用Lyapunov稳定性理论对两种控制律的稳定性进行了证明。数值仿真验证了本文提出的控制律的有效性。 相似文献
15.
16.
超细长弹性杆动力学模型在DNA分子结构模型的平衡、稳定性等问题的研究中有重要的应用。为了便于其数值仿真、图形后处理以及研究表面接触等问题的处理,需要建立弹性杆的表面模型。利用Kirchhoff弹性杆模型的动力学比拟技巧,建立了由四元数的描述超细长弹性杆曲面的常微分,积分方程组,利用Adames方法和递推方法设计了方程的数值解法,并蛤出了超细长弹性杆的数值仿真和图形处理的计算实例。 相似文献
17.
赋权Hamilton路的DNA计算模型 总被引:10,自引:1,他引:9
DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。 相似文献
18.
XUDachuan 《系统科学与复杂性》2003,16(2):260-267
Using outward rotations, we obtain an approximation algorithm for MAX n/2-UNCUT problem, i.e., partitioning the vertices of a weighted graph into two blocks of equal cardinality such that the total weight of edges that do not cross the cut is maximized. In many interesting causes, the algorithm performs better than the algorithms of Ye and of Halperin and Zwick. The main tool used to obtain this result is semidefinite programming. 相似文献