回溯法求解TSP问题
本文档介绍了使用回溯法来解决旅行商问题（TSP）的方法。回溯法是一种选优搜索法，通过递归调用来实现。实验报告中，使用了回溯法来解决5个城市的交通图问题，目标是找出一条费用最低的回路。
一、实验目的
掌握递归回溯法的思想，能够求解TSP问题，增强自己的编程能力。
二、实验内容
下图是5个城市的交通图，城市之间的连线权重表示城市之间路程的费用。要求从A城出发，经过其它城市一次且仅一次，最后回到A城，找出一条费用最低的回路。
三、回溯法思想
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
四、算法流程
递归调用回溯法否是否，返回是
五、关键技术
1. 使用了递归回溯法，通过递归调用，节省了代码量，使代码更简洁易懂。
关键代码：
```c
void Backtracking(int cityId, int depth, int len) {
//正走到的城市的节点号 经过的节点数 走过的长度
if (cityId == 0 && depth == 5) {
//如果从A节点出发又回到A节点，且经过刚好走过所有城市所得的长度值较小，则替换minDis
if (len <= minDis) {
minDis = len;
savePath();
}
return;
}
if (len >= minDis) {
//如果长度值较大，直接回溯选择下一个城市
return;
}
for (int i = 0; i < tab[cityId].size(); i++) {
//nodeId 表示当前城市，i 表示Backtracking（回溯法）如 果 城 市 id=0 并且深度等于5？通过比较，找到最小的距离
if (hasVis[tab[cityId][i].second] == false) {//当与cityID城市连接的城市没有被访问过
hasVis[tab[cityId][i].second] = true;
pre[tab[cityId][i].second] = cityId;
Backtracking(tab[cityId][i].second, depth + 1, len + tab[cityId][i].first);
pre[tab[cityId][i].second] = -1;//返回上一层
hasVis[tab[cityId][i].second] = false; //false 表示没有走过这个城市
}
}
}
```
2. 把原问题需要的数据存放在了txt文件当中，通过读取文件来读取题目要求，使得操作更简单
关键代码：
```c
void getTab() {
//用户输入城市信息
int u,
int v,
int w;
//printf("Inputing ends up with -1 -1 -1\n");
while (1) {
fscanf(fp,"%d %d %d", &u, &v, &w);
if (u == -1 && v == -1 && w == -1)
break;
tab[u].push_back(PII(w, v));
tab[v].push_back(PII(w, u));
}
}
```
本文档详细地介绍了使用回溯法来解决TSP问题的方法，并提供了关键代码和实验报告，供读者参考。
- 1
- 2
前往页