Steiner森林问题的一种同步增长算法研究.pdf

18 4 ( ) 2016 8 第 卷 第 期 重庆科技学院学报 自然科学版 年 月 Steiner 森林问题的一种同步增长算法研究 李睿 杨子兰 周华君 ( ， 674100) 云南大学旅游文化学院信息科学与技术系 云南 丽江 :Steiner NP － 。 Steiner 摘 要 森林问题是组合优化理论中一个著名的 完备问题 针对 森林问题设计了一种同步增长 。 ， ， ， 算法 该算法利用同步增长各连通片对偶值的方法 逐步求得可行解 在不影响可行性的前提下进行调整 最后得 到一个新的解。 :Steiner ; ; 关键词 森林 同步增长 连通片 中图分类号:O157 文献标识码:A 文章编号:1673 － 1980 (2016)04 － 0122 － 03 DOI:10.19406/j.cnki.cqkjxyxbzkb.2016.04.034 珔 Steiner 1， u S ，v S ， r (u ，v)= 1 ; 森林问题是组合优化理论中的一个经典 若存在 ∈ ∈ 且 。 ［1］: G = f (S)= {0 ， 。 问题 一般可描述如下 给定一个无向图 否则 (V，E ;c)， 中c :E Q+ ( 1， e G ; 其 → 为定义在边上的权重 边 若边 出现在 中 ， ) V x (e)= {0 ， 权重 也称费用 ，V ，V ，…，V 为顶点 互不相交的 否则。 1 2 k k ， G G ， G : 个子集 要找到图 的某个子图 使得在 中各 则可得到如下整数线性规划 V ， i 内部的顶点保持相互连通 使所得子图的边权重 min c x ∑ e e e E ( SFP)。 ， V = V ， ∈ 之和最小 简称为 显然 若 i 则此问题 Steiner ， NP －