Abstract: 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 combinatorial 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 series of computational experiments and tests the performances, that result within satisfaction.

Key words: Steiner tree; Simulated annealing; Ant algorithm

摘要： 欧氏平面内连接固定原点的最小树长问题，即欧氏Steiner 最小树问题，为组合优化中的NP 难题，因此合理的方法是寻找启发式算法。该文给出了两种智能优化算法——模拟退火法和蚂蚁算法。首先概述智能优化算法并将平面划分成网格，然后分别介绍两种算法的原理及实现过程，最后通过一系列计算实验，测试了算法的运行性能，获得了较好的效果。

关键词: Steiner 树；模拟退火算法；蚂蚁算法