回溯法求解TSP问题

人工智能实验报告

实验名称：TSP问题

姓名：xxx

学号：xxx

xx大学计算机学院

2014年1月14日

一．实验目的

掌握递归回溯法的思想，能够求解TSP 问题，增强自己的编程能力.

二．实验内容

下图是5个城市的交通图，城市之间的连线权重表示城市之间路程的费用。

要求从A 城出发，经过其它城市一次且仅一次，最后回到A 城，找出一条费用最低的回路。请用伪代码形式描述所设计的算法。

A

B

D

C

E

10

6

9

9

2

3

12

8

118

三、回溯法思想：

回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

若已有满足约束条件的部分解，不妨设为（x1,x2,x3,……xi ），I

四、算法流程：

递归调用回溯法

否

是

否，返回

是

五、关键技术：

1、使用了递归回溯法，通过递归调用，节省了代码量，使代码更简洁易懂。 关键代码：

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); //递归调用，直到走完5个节点

pre[tab[cityId][i].second] = -1;//返回上一层

hasVis[tab[cityId][i].second] = false; //false表示没有走过这个城市 }

}

}

2、把原问题需要的数据存放在了txt文件当中，通过读取文件来读取题目要求，使得操作更简单

关键代码：

void getTab() { //用户输入城市信息

int u, //城市u

v, //城市v

w; //uv之间的距离

//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)); //对于城市u来说，uv之间的距离是w

tab[v].push_back(PII(w, u)); //对于城市v来说也是一样

}

}

3、使用了vector容器，更有利于存放子空间的解，避免了使用数组不当造成的相关问题。

typedef pair PII;//定义类型存放城市的相邻城市和它们之间的费用vector tab[10];

tab[u].push_back(PII(w, v));

tab[nodeId][i].first tab[nodeId][i].second

六、实验心得

1、重温了算法课程里面学过的回溯法，强化了这种编程思想。

2、深刻理解了递归调用的思想。

3、学习了容器这样一种结构，可以简单的理解为一种数组，但是它有很多有用的方法，很多时候可以直接调用相关函数以减少代码的冗余。

4、通过这次实验对TSP算法的C++解法有了进一步的了解，把理论知识应用于

实验中。