用模拟退火 写一个TSPc++代码
时间: 2023-12-29 16:45:55 浏览: 30
以下是一个基本的TSP的模拟退火算法的C++代码:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 1005;
const double delta = 0.99;
const double T = 1e-15;
const double INF = 1e15;
double x[maxn], y[maxn], dis[maxn][maxn], ans;
int n, cnt, path[maxn], best_path[maxn];
double calc(int i, int j) {
return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
void init() {
for (int i = 1; i <= n; i++) {
scanf("%lf %lf", &x[i], &y[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
dis[i][j] = dis[j][i] = calc(i, j);
}
}
}
double eval() {
double sum = 0;
for (int i = 2; i <= n; i++) {
sum += dis[path[i - 1]][path[i]];
}
sum += dis[path[1]][path[n]];
return sum;
}
void SA() {
double t = 10000;
while (t > T) {
int x = rand() % n + 1, y = rand() % n + 1;
while (x == y) y = rand() % n + 1;
double delta = dis[path[x - 1]][path[y]] + dis[path[x + 1]][path[y]] + dis[path[y - 1]][path[x]] + dis[path[y + 1]][path[x]]
- dis[path[x - 1]][path[x]] - dis[path[x + 1]][path[x]] - dis[path[y - 1]][path[y]] - dis[path[y + 1]][path[y]];
if (delta < 0 || exp(-delta / t) * RAND_MAX > rand()) {
swap(path[x], path[y]);
if (ans > eval()) {
ans = eval();
memcpy(best_path, path, sizeof(path));
}
}
t *= delta;
}
}
int main() {
srand((unsigned)time(NULL));
scanf("%d", &n);
init();
for (int i = 1; i <= n; i++) {
path[i] = i;
}
ans = eval();
memcpy(best_path, path, sizeof(path));
while (cnt <= 500) {
SA();
cnt++;
}
printf("最短路径长度为: %.2f\n", ans);
printf("遍历路径为: ");
for (int i = 1; i <= n; i++) {
printf("%d ", best_path[i]);
}
printf("\n");
return 0;
}
```
该算法的主要思想是维护一个当前的解,并且在每次迭代中随机选择两个位置进行交换,如果新的解更优,则使用新的解,否则以一定概率接受新的解。通过不断降温,最后达到一个全局最优解。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)