共 1 条
最大流问题的DNA计算两阶段法
被引：11
作者：
周康
王子成
许进
机构：
[1] 武汉工业学院数理科学系
[2] 华中科技大学控制科学与工程系
[3] 华中科技大学控制科学与工程系 湖北武汉
[4] 湖北武汉
来源：
关键词：
最大流;
DNA计算;
Δ-松弛网络;
增广路;
D O I：
10.13245/j.hust.2005.08.033
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ;
0812 ;
0835 ;
1405 ;
摘要：
给出了最大流问题的DNA计算两阶段法:第一阶段采用路序问题DNA算法得到包括所有增广路的路集,算法有两点改进,即采用等码长编码和不进行排序,这减少了生化实验时间.第二阶段算法思路是:设置一个逐步减小的增量Δ,对每个确定的Δ值从第一阶段得到的路集中寻找并增广容量不小于Δ值的增广路,对整数容量网络,当Δ<1时获得最大流.证明了算法的正确性和复杂性,并指出在以增广路为基础的最大流算法中,本算法复杂度最低,这说明DNA计算和电子计算相结合的巨大优势.
引用
收藏
页码：104 / 107
页数：4
相关论文