(原创精品)旅行售货员问题(回溯法)

《(原创精品)旅行售货员问题(回溯法)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、旅行售货员问题问题描述：某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短该问题是一个NP完全问题，有(n-1)!条可选路线最优解(1,3,2,4,1)，最优值25问题具体描述：某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路

2、线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。算法描述：旅行售货员问题的解空间是一棵排列树x=[123…..n]——>相应的排列树由x[1:n]的所有排列构成①在递归算法Backtrack中②当i=n时，当前扩展结点是排列树的叶节点的父结点③此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边………算法：templatevoidTraveling::Backtrac

3、k(inti){if(i==n){if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&&(cc+a[x[n-1]][x[n]]+a[x[n]][1]

4、

5、bestc==NoEdge)){for(intj=1;j<=n;j++)bestx[j]=x[j];bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];}}else{for(intj=i;j<=n;j++)//是否可进入x[j]子树?if(a[x[i-1]][x[j]]!=NoEdge&&(cc+a[x[

6、i-1]][x[i]]

7、

8、bestc==NoEdge)){//搜索子树Swap(x[i],x[j]);cc+=a[x[i-1]][x[i]];Backtrack(i+1);cc-=a[x[i-1]][x[i]];Swap(x[i],x[j]);}}}复杂度分析算法backtrack在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)