/SimulateAnneal

模拟退火算法求解TSP问题

Primary LanguageC++Apache License 2.0Apache-2.0

SimulateAnneal

模拟退火算法求解TSP问题

本程序使用 C++实现了通过模拟退火算法求解 TSP 问题

(为保证开发速度与实际性能,使用了部分 C++11 新特性,编译时请加参数-std=c++11)

用法:

TSP 类包含两个构造函数,分别用于有数据文件、随机生成数据情况。

TSP(int city, int line, string file) 
city:城市数 
ling:数据文件行数 
file:数据文件名 

TSP(int city) 
city:城市数 

TSP 类 calculate 方法,通过模拟退火算法计算最短路径长度,返回值为 double类型的最短路径长度

double calculate(int loop, double t, double delta, double epsilon, const int limit) 
loop 循环次数
t 初始温度 
delta 温度衰减率 
epsilon 最低温度 
limit 限制迭代次数 

TSP 类 detail 方法,返回一个 vector,包含了最短路径所经节点 vector<int> detail()

性能测试:

Intel i5-7200U、8GB 内存、Windows10 操作系统、TDM-GCC 4.9.2,编译选项std=c++11 算法参数为 loop = 40 , t = 1 , delta = 0.999, epsilon= 1e-30, limit=300000

城市数 10 20 35 50 运行时间(ms) 226 256 295 354