欧氏Steiner最小树问题的智能优化算法  

Intelligent Optimization Algorithms for Euclidean Steiner Minimum Tree Problem

作　　者：金慧敏[1] 马良[1] 王周缅[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程》2006年第10期201-203,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(70471065)

摘　　要：欧氏平面内连接固定原点的最小树长问题,即欧氏Steiner最小树问题,为组合优化中的NP难题,因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将平面划分成网格,然后分别介绍两种算法的原理及实现过程,最后通过一系列计算实验,测试了算法的运行性能,获得了较好的效果。The Euclidean Steiner tree problem, which concerns the construction of a tree that connects a given set of terminal points in Euclidean space with the minimal total lengths, is NP-hard in eomhinatorial optimization. This paper presents two intelligent optimization algorithms-the simulated annealing algorithm and the ant algorithm. Firstly, this paper summarizes the intelligent optimization algorithm and divides space into grids, then introduces the principles of two algorithms and their implementations. Finally, it implements serics of computational experiments and tests the performances, that result within satisfaction.

关 键 词：STEINER树 模拟退火算法 蚂蚁算法 

分 类 号：O22[理学—运筹学与控制论]