摘要
Steiner森林问题是组合优化理论中一个著名的NP-完备问题。针对Steiner森林问题设计了一种同步增长算法。该算法利用同步增长各连通片对偶值的方法,逐步求得可行解,在不影响可行性的前提下进行调整,最后得到一个新的解。
Steiner forest problem is a well - known NPC problem in combinatorial optimization, so in this paper we advocate an algorithm to solve the Steiner forest problem. The algorithm increases the dual value of each connected component synchronously, and gets a feasible solution gradually. Then we adjust the solution constantly and finally prove the correctness and validity of the algorithm.
出处
《重庆科技学院学报（自然科学版）》
CAS
2016年第4期122-124,共3页
Journal of Chongqing University of Science and Technology：Natural Sciences Edition
基金
云南省教育厅科学研究基金项目"视频监控中的全景摄像机自标定技术"(2013Y167)
关键词
Steiner森林
同步增长
连通片
Steiner forest
increase synchronously
connected component
