求解回溯法TSP问题求解回溯法TSP问题
人工智能实验报告
实验名称： TSP问题
名称： xxx
学校编号： xxx
xx大学计算机学院
2014年1月14日
实验的目的
掌握递归回溯法的思想，可以解决TSP问题，提高自己的编程能力。
实验内容
下图是5个城市的交通图，城市之间的连接权重表示城市之间的路程费用。 要求从a城出发，只经过其他城市一次，最后回到a城，找到费用最低的电路。 请用伪代码的形式描述设计的算法。
溯法思想：
回溯法(搜索和回溯法)是选良检索法，为了达成目标，在选良条件下进行前方检索。 但是，在探索了某一步的时候，如果原来的选择不优秀或者没有达到目标，就返回一步重新选择。 这样，如果不顺利就返回的技术是回溯法，将满足有回溯条件的状态的点称为“回溯点”。
如果已经有满足约束条件的部分解，请设为(x1，x2，x3，……xi )，I )
算法流程：
递归地调用回溯
不
是
不，回去
是
主要技术：
采用递归回溯法，通过递归调用，节省了代码量，使代码更加简洁易懂。
密钥代码：
voidbacktracking(intcityid，int depth，int len )//所走城市的节点编号所经过的节点数所走的长度
if(cityid==0depth==5) (从/a节点出发并返回到a节点，如果通过所有城市时的长度值正好很小，请替换最小
if(len=Mindis ) (
minDis=len；
保存路径(；
}
返回；
}
if(len=Mindis(//长度值较大时，直接追溯选择下一个城市
返回；
}
for(intI=0； i tab[cityId].size (； I ) { //nodeId表示当前城市，I表示与之相连的城市
连接到cityID城市的城市从未访问过if (has vis [ tab [ cityid ] [ I ].second ]==false )
has vis [ tab [ cityid ] [ I ].second ]=true；
pre [ tab [ cityid ] [ I ].second ]=cityid；
返回跟踪(tab [ cityid ] [ I ].second，depth 1，len tab[cityId][i].first )； //递归调用，直到走完5个节点
pre[tab[cityId][i].second]=-1； //回到上一层
has vis [ tab [ cityid ] [ I ].second ]=false； //false表示没有在这条街上走
}
}
}
将原问题所需的数据存入txt文件，通过读取文件读取主题要求，简化操作
密钥代码：
void getTab ()//用户输入城市信息
int u，//城市u
v，//城市v
w； //uv之间的距离
//printf (inputingendsupwith-1-1-1 (n )；
wile(1) {
FP，' %d %d %d '，u，v，w；
if(u==-1v==-1w==-1 ) )
布雷克；
tab[u].push_back(pii(w，v )； //对于城市u来说，uv之间的距离是w
tab[v].push_back(pii(w，u )； //对城市v来说