旅行商问题用回溯法并且包含排列空间树思想解决,请给我具体C++实现代码
时间: 2024-02-24 18:59:31 浏览: 29
好的,以下是旅行商问题用回溯法并包含排列空间树思想的C++实现代码:
```
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 20;
int n, ans = INF;
int map[MAXN][MAXN];
bool vis[MAXN];
void dfs(int cur, int cost, int cnt) {
if (cnt == n && map[cur][0] != INF) {
ans = min(ans, cost + map[cur][0]);
return;
}
if (cost >= ans) return;
for (int i = 1; i <= n; i++) {
if (!vis[i] && map[cur][i] != INF) {
vis[i] = true;
dfs(i, cost + map[cur][i], cnt + 1);
vis[i] = false;
}
}
}
int main() {
memset(vis, false, sizeof(vis));
memset(map, INF, sizeof(map));
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
vis[0] = true;
for (int i = 1; i < n; i++) {
swap(map[0][i], map[i][0]);
}
sort(map[0] + 1, map[0] + n);
dfs(0, 0, 0);
cout << ans << endl;
return 0;
}
```
其中,用到了排列空间树的思想,将起点固定为0,然后将其它点与0交换位置,然后将与0相邻的点按距离从小到大排序,这样可以大大减少搜索的路径,提高搜索效率。