基于模拟退火算法求解Steiner树问题(STP)仿真例程

资 源 简 介

该项目提供了一套完整的MATLAB代码，用于利用模拟退火算法（Simulated Annealing, SA）解决经典的斯坦纳树问题（Steiner Tree Problem）。Steiner树问题的核心目标是在给定的加权图中，寻找一个包含所有指定终端节点（Terminals）且总边权最小的子图树结构，为了达到总权重最小，通常需要引入额外的非终端节点（即Steiner点）。该例程通过构建图形邻接矩阵进行建模，并利用模拟退火机制在复杂的解空间内进行启发式搜索。算法实现了从初始解生成到邻域移动、接受准则判断及

详 情 说 明

基于模拟退火算法求解Steiner树问题(STP)的MATLAB项目说明

项目介绍

本项目旨在通过启发式搜索算法——模拟退火（Simulated Annealing, SA）解决图论中的经典难题：斯坦纳树问题（Steiner Tree Problem, STP）。Steiner树问题的目标是在平面内给定一组必须连接的终端节点（Terminals），通过从一组可选的候选点（Steiner点）中挑选最合适的子集，构建出一棵包含所有终端节点且总边权最小的生成树。该方法广泛应用于电路布线、网络拓扑设计及交通物流优化等领域。

功能特性

• 启发式优化策略：采用模拟退火机制，通过Metropolis准则在解空间内进行概率性搜索，有效跳出局部最优解。
• 混合节点建模：支持终端节点（固定点）与候选Steiner点（可选点）的差异化处理与动态筛选。
• 最小生成树集成：内部集成Prim算法，用于快速计算待选节点集合的最小代价生成。
• 高度可视化：自动生成算法收敛曲线图以及最终的网络拓扑图，直观展示节点筛选与结构演变过程。
• 参数解耦设计：用户可灵活调整初始温度、冷却速率、候选点密度等核心参数。

系统要求

• 软件环境：MATLAB R2016b 或更高版本。
• 工具箱要求：无需特殊工具箱，基于MATLAB基础函数库实现。

实现逻辑说明

代码主体流程分为以下六个核心步骤：

1. 环境初始化：设定终端节点数量、候选Steiner点数量、区域空间范围，并定义模拟退火的关键控制参数。为了保证实验的可重复性，代码通过固定随机种子来生成节点坐标。
2. 代价矩阵构建：计算所有节点（包括终端和候选点）之间的欧几里得距离，生成全连通图的距离权重矩阵，为后续MST（最小生成树）的计算提供基础数据。
3. 状态向量定义：算法将解空间抽象为一个二进制向量，其长度等于候选点的总数。向量中的每一位代码对应一个候选点，1表示该点被包含在当前的Steiner树计算中，0表示排除。
4. 模拟退火主循环：

- 邻域搜索：随机选择一个候选点并翻转其状态（0变1或1变0）。 - 代价评估：利用Prim算法计算包含所有终端点和当前选中候选点形成的最小代价数值。 - 接受准则：若新状态代价较低则接受；若代价较高，则根据当前的温度以一定的概率（Exp函数）决定是否接受新状态。

1. 降温控制：在每个温度水平下完成指定次数的迭代后，按照预定的冷却系数降低温度。
2. 结果输出：记录并绘制随着退火过程推进，Steiner树总权重的下降曲线，并渲染最终生成的几何拓扑图。

关键算法与实现细节

• 节点编码方案：代码巧妙地将Steiner点选择问题转化为二进制组合优化问题。初始解假定不选择任何Steiner点，仅连接终端点。
• 代价计算细节：在一个独立的内部函数中实现了Prim算法。该函数根据当前被激活的候选点状态，提取出距离矩阵的对应子集。它维护一个最小距离向量和一个访问标志向量，逐个寻找距离当前生长树最近的节点并更新代价。
• 映射机制：由于每一轮选取的候选点子集不同，函数在进行边连接绘制时，通过建立全局索引与子集索引的映射（Mapping）关系，确保可视化时线条能精准连接到正确的物理坐标。
• 收敛稳定性：通过设定马尔可夫链长度（max_iter）以及指数衰减的降温模型，确保算法在高温阶段有足够的探索能力，在低温阶段能实现精细收敛。
• 拓扑渲染图例：最终的物理图中通过红色圆圈代表终端、蓝色方块代表选中的Steiner点、灰色圆点代表被剔除的候选点，并用绿色实线勾勒出最优的树形结构。