共查询到16条相似文献,搜索用时 250 毫秒
1.
2.
提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。 相似文献
3.
4.
最优指派问题DNA算法 总被引:1,自引:1,他引:1
对求最小值的最优指派数学模型,设计并实现了DNA计算算法。首先经过特殊的DNA编码将二维的决策变量和二维的效益值编入DNA序列中;然后通过杂交实验和分离实验得到指派问题的全部可行解;最后通过电泳实验和检测实验获得最优指派问题的最优解。证明了算法的复杂性并举例说明了算法的可行性。分别给出了求最大值的最优指派问题和人数与工作数不等的最优指派问题的处理方法。 相似文献
5.
当网络中的权值不是常数而是含参数的函数时,它可以看作是一种动态网络,用传统的算法求解这类网络的最短路径变得十分困难.为此,提出了含二次参数权的多阶段网络最短路问题,并利用Dijkstra算法思想和隐枚举方法给出了求该网络最短路的隐枚举标号算法,最后对该算法的复杂性进行了分析.理论分析与实验结果表明,尽管该算法不是多项式的,但对于一定规模的该类网络还是十分有效的. 相似文献
6.
TSP的DNA计算算法 总被引:11,自引:1,他引:11
提出了TSP的DNA算法,共有六个步骤:首先将TSP转化为有向图的经过所有点最短闭链问题并进行编码;其次从某点开始用有目的的终止技术——芯片技术、保护基技术以及杂交实验——得到起点和终点相同的DNA链;再用分离实验产生经过所有顶点的DNA链;然后用电泳实验取出链长最短的DNA链;最后用标记实验解读最优解集。讨论了算法的复杂性并用实例说明了算法的有效性。还讨论了推广的TSP——推销员在城市有停留时间——的算法的变化——只需改变编码方式,以及实验的简化问题。最后说明了本算法提出的一种新的合成技术——有目的的终止技术的优势和前景。 相似文献
7.
8.
9.
10.
首先给出了在非负网络中构造最短路网络的算法,然后将树形图的计数算法到最短路网络中,设计出了最短路树计数问题的算法,将Gabow算法应用到最短路网络中,设计出了产生全部最短路树的算法,最后研究了最短路树的优化问题。 相似文献
11.
Closed circle DNA algorithm of change positive-weighted Hamilton circuit problem 总被引:2,自引:0,他引:2 下载免费PDF全文
Chain length of closed circle DNA is equal. The same closed circle DNA's position corresponds to different recognition sequence, and the same recognition sequence corresponds to different foreign DNA segment, so closed circle DNA computing model is generalized. For change positive-weighted Hamilton circuit problem, closed circle DNA algorithm is put forward. First, three groups of DNA encoding are encoded for all arcs, and deck groups are designed for all vertices. All possible solutions axe composed. Then, the feasible solutions axe filtered out by using group detect experiment, and the optimization solutions are obtained by using group insert experiment and electrophoresis experiment. Finally, all optimization solutions are found by using detect experiment. Complexity of algorithm is concluded and validity of DNA algorithm is explained by an example. Three dominances of the closed circle DNA algorithm are analyzed, and characteristics and dominances of group delete experiment axe discussed. 相似文献
12.
Path determination is a fundamental problem of operations research.Current solutions mainly focus on the shortest and longest paths.We consider a more generalized problem;specifically,we consider the path problem with desired bounded lengths(DBL path problem).This problem has extensive applications;however,this problem is much harder,especially for large-scale problems.An effective approach to this problem is equivalent simplification.We focus on simplifying the problem in acyclic networks and creating a path length model that simplifies relationships between various path lengths.Based on this model,we design polynomial algorithms to compute the shortest,longest,second shortest,and second longest paths that traverse any arc.Furthermore,we design a polynomial algorithm for the equivalent simplification of the DBL path problem.The complexity of the algorithm is 0(m),where m is the number of arcs. 相似文献
13.
14.
有向最短哈密尔顿路问题的DNA算法 总被引:11,自引:2,他引:9
首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。 相似文献
15.
服务质量路由问题的一个新进化算法 总被引:1,自引:0,他引:1
针对服务质量路由问题,设计了一种新颖的进化算法QoS_EA.该算法具有以下特点:(1)通过采用一种前向自然教编码方法,使路径不包含圈,节省了进化算法在求解该问题时的圈检查过程;(2)设计了一种散接交叉算子,以防止出现不可行的路径,确保交又操作的有效性和种群的多样性;(3)与交叉算子相对应设计了一种基于局部链路选择性修改的选择性变异算子,以确保路径由任意初始状态进化到满足约束的路径.理论分析证明该算法具有明显的优越性,并以概率1收敛于所求路径.计算机仿真结果表明该算法性能优于其他同类算法. 相似文献
16.
在通信网络中,因突发事件造成通信路由节点毁坏或者中断的现象时有发生,传输的数据包不得不从中断处沿着最短的替代路径行进到数据包的接收节点,在这种情形下,哪个路由节点中断使得数据包实际行进的总路程最长呢?从通信网络管理的角度来看这是一个非常重要的问题。对该问题.以前的文献都是从确定情形(事先具有节点中断的完全信息)下进行研究的,本文从不确定情形(只有数据包行进到中断节点的邻接点时才获得该节点中断的信息)的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点概念,给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析,比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题,指出了不确定情形下最短路径关键点问题更具有实际意义。 相似文献