旅行商问题贪心算法c++
时间: 2023-10-29 20:08:07 浏览: 145
旅行商问题的贪心算法可以分为两种:最小生成树算法和最近邻算法。其中最近邻算法是比较简单的一种,其基本思路是从一个起点开始,每次选择距离当前点最近的未访问过的点作为下一个点,直到所有点都被访问过,最后回到起点。以下是旅行商问题最近邻算法的C++代码:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
int n; // 城市数量
cin >> n;
vector<vector<int>> graph(n, vector<int>(n)); // 存储城市之间的距离
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> graph[i][j];
}
}
vector<int> path(n); // 存储路径
vector<bool> visited(n, false); // 标记城市是否被访问过
int cur = 0; // 当前所在城市
visited[cur] = true;
path[0] = cur;
for (int i = 1; i < n; i++) {
int next = -1;
int min_dist = INF;
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[cur][j] < min_dist) {
next = j;
min_dist = graph[cur][j];
}
}
visited[next] = true;
path[i] = next;
cur = next;
}
// 计算路径长度
int total_dist = 0;
for (int i = 0; i < n - 1; i++) {
total_dist += graph[path[i]][path[i+1]];
}
total_dist += graph[path[n-1]][path[0]];
// 输出结果
cout << "最短路径长度为:" << total_dist << endl;
cout << "路径为:";
for (int i = 0; i < n; i++) {
cout << path[i] << " ";
}
cout << endl;
return 0;
}
```
阅读全文