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

《经典回溯问题-----旅行员售货问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、并且在init()中设定了所有点的Cost[][];  int Cost[MAX][MAX];//记录任意两点的运费或代价  int bestCost=MAX;//记录目前最少运费或代价  int currentCost;//当前运费或代价  int current[MAX];//当前路径  int best[MAX];//记录最佳路径    void swap(int& a,int& b)  {      int temp=a;      a=b;      b=temp;  }    void backtrack(int t)//其实就是一个排列问题。。。  {   

3、   int j;      if(t==N)//到了最后一层。。      {          if(Cost[current[t-1]][current[t]]+Cost[current[t]][1]+currentCost

4、t[j]=current[j];              }          }      }            for(j=t;j<=N;j++)//排列。。。      {          swap(current[t],current[j]);          if(Cost[current[t-1]][current[t]]+currentCost(t-1)的代价或运费          {              currentCost+=Cost[current[t-1]][cu

5、rrent[t]];              backtrack(t+1);//递归回溯              currentCost-=Cost[current[t-1]][current[t]];          }          swap(current[t],current[j]);      }  }    void init()  {       Cost[1][1]=0;       Cost[1][2]=30;       Cost[1][3]=6;       Cost[1][4]=4;         Cost[2][1]=30;     

6、  Cost[2][2]=0;       Cost[2][3]=5;       Cost[2][4]=10;         Cost[3][1]=6;       Cost[3][2]=5;       Cost[3][3]=0;       Cost[3][4]=20;         Cost[4][1]=4;       Cost[4][2]=10;       Cost[4][3]=20;       Cost[4][4]=0;  }  void main()  {       init();         int i;       for(i=1;i<=

7、N;i++)       {           current[i]=i;       }         backtrack(2);//树的第一层已经找到了，所以从第二层开始         cout<<"最少的运费为:"<";       }       cout<