经典回溯问题-----旅行员售货问题

《经典回溯问题-----旅行员售货问题》由会员分享，可在线阅读，更多相关《经典回溯问题-----旅行员售货问题（3页珍藏版）》请在金锄头文库上搜索。

1、经典回溯问题经典回溯问题-旅行员售货问题旅行员售货问题问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费） ，他要选定 一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。以上图为例：售货员要从 1 开始经过 2，3，4 又返回 1。 给我的感觉就是一个排列问题。在进行计算排列的同时要判断是否该排列有必要进行 下去，因为可能在中途就可以判断这样肯定得不到我们想要的结果，此时采用回溯。 代码实现： #include using namespace std; #define MAX 1024 int N=4;/可以自己输入，这里我就指定了，并且在 init

2、()中设定了所有点的 Cost; int CostMAXMAX;/记录任意两点的运费或代价 int bestCost=MAX;/记录目前最少运费或代价 int currentCost;/当前运费或代价 int currentMAX;/当前路径 int bestMAX;/记录最佳路径 void swap(int a=b; b=temp; void backtrack(int t)/其实就是一个排列问题。 。 。 int j; if(t=N)/到了最后一层。 。 if(Costcurrentt-1currentt+Costcurrentt1+currentCost(t-1)的代价或运费 curre

3、ntCost+=Costcurrentt-1currentt; backtrack(t+1);/递归回溯 currentCost-=Costcurrentt-1currentt; swap(currentt,currentj); void init() Cost11=0; Cost12=30; Cost13=6; Cost14=4; Cost21=30; Cost22=0; Cost23=5; Cost24=10; Cost31=6; Cost32=5; Cost33=0; Cost34=20; Cost41=4; Cost42=10; Cost43=20; Cost44=0; void main() init(); int i; for(i=1;i“; coutbest1endl; 运行结果为：