摘要
给出了最大流问题的DNA计算两阶段法:第一阶段采用路序问题DNA算法得到包括所有增广路的路集,算法有两点改进,即采用等码长编码和不进行排序,这减少了生化实验时间.第二阶段算法思路是:设置一个逐步减小的增量Δ,对每个确定的Δ值从第一阶段得到的路集中寻找并增广容量不小于Δ值的增广路,对整数容量网络,当Δ<1时获得最大流.证明了算法的正确性和复杂性,并指出在以增广路为基础的最大流算法中,本算法复杂度最低,这说明DNA计算和电子计算相结合的巨大优势.
DNA algorithm with two phases for maximum flow problem was put forward In first phase the DNA algorithm of arranging path to obtain path set including all augmenting paths for every flows. Differing from the former of this DNA algorithm is to encode of equal DNA＇s length and not to arrange paths which can reduce time of the experiment of biochemistry. The secondly phase was to design an increment △ which decrease step by step, and for any fixed value of △, finding out from path set and the augmenting path whose capability not less than the value of △. When △〈 1, maimum flow is obtained for integer capability network. The validity and the complexity of the DNA algorithm were proved. It was also pointed that the complexity of this algorithm is minimum in all algorithms based on augmenting path, showing that there is huge advantage to combine with DNA computing and electronic computing.
出处
《华中科技大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2005年第8期104-107,共4页
Journal of Huazhong University of Science and Technology(Natural Science Edition)
基金
武汉工业学院校立科研项目资助项目(04-D-05)
关键词
最大流
DNA计算
△松弛网络
增广路
maximum flow
DNA computing
△-relaxation network
augmenting path
