最近插入法tsp代码C++
时间: 2023-07-11 13:26:34 浏览: 68
以下是C++语言实现最近插入法TSP算法的代码示例:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
double get_dist(pair<double, double> p1, pair<double, double> p2) {
double dx = p1.first - p2.first;
double dy = p1.second - p2.second;
return sqrt(dx*dx + dy*dy);
}
int main() {
int n;
cin >> n;
vector<pair<double, double>> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
vector<int> path(n);
for (int i = 0; i < n; i++) {
path[i] = i;
}
double ans = INF;
do {
double len = 0;
for (int i = 1; i < n; i++) {
len += get_dist(points[path[i-1]], points[path[i]]);
}
ans = min(ans, len);
} while (next_permutation(path.begin(), path.end()));
cout << ans << endl;
vector<int> new_path;
new_path.push_back(0);
new_path.push_back(1);
for (int i = 2; i < n; i++) {
int pos = -1;
double min_dist = INF;
for (int j = 0; j < i; j++) {
double dist = get_dist(points[path[j]], points[path[i]]) + get_dist(points[path[i]], points[path[(j+1)%i]]);
if (dist < min_dist) {
min_dist = dist;
pos = j;
}
}
new_path.insert(new_path.begin() + pos + 1, path[i]);
}
len = 0;
for (int i = 1; i < n; i++) {
len += get_dist(points[new_path[i-1]], points[new_path[i]]);
}
ans = len;
cout << ans << endl;
return 0;
}
```
注意,上述代码中的 `get_dist` 函数用于计算两个点之间的距离。对于一个包含 $n$ 个点的 TSP 问题,暴力求解的时间复杂度为 $O(n!)$,因此我们需要使用启发式算法来解决大规模的问题,比如最近插入法。