贪心算法tsp问题C++
时间: 2024-05-31 11:05:40 浏览: 19
旅行商问题(Traveling Salesman Problem,TSP)是指给定一个地图和一个旅行商人,他必须从某个城市出发,到另外几个城市旅行一次,并回到起点城市,求最短的旅行路线。这是一个NP难问题,因此一般采用近似算法来解决。
贪心算法是解决TSP问题的一种常用方法。具体来说,从起点开始,每次选择与当前位置最近的未被访问过的城市作为下一个目标城市。这样得到的路径不一定是最优解,但是时间复杂度较低,可以在较短的时间内得到一个较优解。
下面是TSP问题的贪心算法的C++代码示例:
```
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 15;
const int INF = 0x3f3f3f3f;
int n, g[MAXN][MAXN], vis[MAXN], ans = INF;
void dfs(int u, int cnt, int sum) {
if (cnt == n && g[u]) {
ans = min(ans, sum + g[u]);
return;
}
for (int i = 0; i < n; i++) {
if (!vis[i] && g[u][i]) {
vis[i] = 1;
dfs(i, cnt + 1, sum + g[u][i]);
vis[i] = 0;
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
memset(vis, 0, sizeof(vis));
vis = 1;
dfs(0, 1, 0);
cout << ans << endl;
return 0;
}
```
相关推荐
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)