HILL-CLIMBING, SIMULATED ANNEALING AND THE STEINER PROBLEM IN GRAPHS
HILL-CLIMBING, SIMULATED ANNEALING AND THE STEINER PROBLEM IN GRAPHS
复制标题
DOI：
10.1080/03052159108941063
复制
发表时间：
1991-02
影响因子：
2.7
通讯作者：
K. Dowsland
中科院分区：
文献类型：
--
作者：
K. Dowsland
本文考虑局部优化或改进算法在图的Steiner问题上的应用。通过考虑任何斯坦纳树作为一个不相交的联盟的路径，我们表明，它是可以定义一个邻域结构的可行的解决方案，可用于在一个k-opt交换启发式。然后将这些想法扩展到模拟退火方法。计算经验，比较这些新的方法与现有的最好的计算方法之一。
Abstract This paper considers the use of local optimization or improvement heuristics on the Steiner problem in graphs. By considering any Steiner tree as a disjoint union of paths we show it is possible to define a neighbourhood structure on the set of feasible solutions which can be used in a k-opt exchange heuristic. These ideas are then extended to a simulated annealing method. Computational experience, comparing these new methods with one of the best existing heuristics is presented.