TSP动态规划C++代码
时间: 2023-07-08 18:14:59 浏览: 59
以下是TSP动态规划的C++代码示例:
```c++
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits.h>
using namespace std;
const int N = 15;
int n;
double dist[N][N];
double dp[1 << N][N];
double tsp(int mask, int pos) {
if (mask == (1 << n) - 1) {
return dist[pos][0];
}
if (dp[mask][pos] != -1) {
return dp[mask][pos];
}
double ans = INT_MAX;
for (int city = 0; city < n; city++) {
if ((mask & (1 << city)) == 0) {
double newAns = dist[pos][city] + tsp(mask | (1 << city), city);
ans = min(ans, newAns);
}
}
return dp[mask][pos] = ans;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> dist[i][j];
}
}
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
double ans = tsp(1, 0);
cout << ans << endl;
return 0;
}
```
在这个示例中,使用了递归的方式来计算子问题的最优解,并将结果存储在一个dp数组中,以避免重复计算。在主函数中,调用tsp函数来计算TSP问题的最优解,并输出结果。
相关推荐
![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)