学步园

回溯法很简单，但是时间太长了，我在程序中使用了tsplib的ulysses16，十六个城市

目前找到的最优解为

best current: 59.9963
0 14 12 10 8 9 13 4 5 6 11 15 1 2 3 7

比给出的参考标准要好不少

但是比标准数据更好的情况几乎不可能发生

也许是我求距离错了，因为这个case中有负的坐标值，看看再说吧

standard path:
0 13 12 11 6 5 14 4 10 8 9 15 2 1 3 7
length of standard path:
 79.6844

找到这个解后一个多小时内没有更优解

我实在没有耐心运行下去了

于是想保存运行参数，在下次运行时载入参数继续运行

在写了之后，却发现行不通，程序使用了递归调用，要保存参数，就要保存所有深度的参数，而我只保存了最后一层

要真正实现这个功能，就得用较大篇幅写保存参数了

我没去写

如果哪位仁兄完整运行了本程序，劳驾把最优解贴上来

程序中居然使用了ms级的计时器，这也太无聊了

不如直接看一下表，以小时为单位得了

完整的程序在这儿下载

程序写的比较乱

欢迎批评、建议和讨论

/*<br /> * backtracking solution for TSP<br /> *<br /> * @author:onezeros@yahoo.cn<br /> */<br /> #include <iostream><br /> #include <fstream><br /> #include <algorithm><br /> #include <vector><br /> #include <stdlib.h><br /> #include <time.h><br /> #include <assert.h></p> <p>using namespace std;</p> <p>//fast sorting,descending<br /> int quicksort_partion(vector<int>&queueNext,int i,int j,const vector<vector<double> >& distance,int currPos)<br /> {<br /> int tmp=queueNext[i];<br /> double tmp_d=distance[currPos][tmp];</p> <p> int h=i;<br /> for (int k=i+1;k<=j;k++)<br /> {<br /> double k_d=distance[currPos][k];<br /> if (k_d>tmp_d)<br /> {<br /> h++;<br /> int t=queueNext[h];<br /> queueNext[h]=queueNext[k];<br /> queueNext[k]=t;<br /> }<br /> }<br /> int t=queueNext[i];<br /> queueNext[i]=queueNext[h];<br /> queueNext[h]=t;<br /> return h;<br /> }</p> <p>void quicksort(vector<int>&queueNext,int i,int j,const vector<vector<double> >& distance,int currPos)<br /> {<br /> if (i<j)<br /> {<br /> int p=quicksort_partion(queueNext,i,j,distance,currPos);<br /> quicksort(queueNext,i,p-1,distance,currPos);<br /> quicksort(queueNext,p+1,j,distance,currPos);<br /> }<br /> }<br /> // params:<br /> // bestPath: length of best path found for the moment<br /> // currPathLen:length of partial path from start city to currentPos<br /> // queueNext: a queue of avalible cities to go<br /> // currentPos: current Position<br /> // distance: distance table<br /> // path: the path from start city to currentPos<br /> void backtrack(double&bestPath,double currPathLen,vector<int> queueNext,<br /> int currentPos,const vector<vector<double> >& distance,<br /> vector<int>&path)<br /> {<br /> path.push_back(currentPos);<br /> /*cout<<"current Position: "<<currentPos<<endl;<br /> for (int i=0;i<queueNext.size();i++){<br /> cout<<queueNext[i]<<" ";<br /> }<br /> cout<<endl;*/<br /> if (queueNext.size()==0){//leaf nods<br /> for (int i=0;i<path.size()-1;i++){<br /> cout<<path[i]<<" ";<br /> }<br /> cout<<endl;</p> <p> currPathLen+=distance[currentPos][0];<br /> if (currPathLen<bestPath){<br /> bestPath=currPathLen;<br /> cout<<bestPath<<endl;<br /> //output to a file<br /> fstream f("data/result.txt",ios::app);<br /> f<<"best current: "<<bestPath<<endl;<br /> for (int i=0;i<path.size();i++){<br /> f<<path[i]<<" ";<br /> }<br /> f<<endl;<br /> f.close();</p> <p> }<br /> }else{<br /> //sort queueNext by distance between element in queneNext and currentPos<br /> //the last one in queue is nearest to currPos<br /> quicksort(queueNext,0,queueNext.size()-1,distance,currentPos);</p> <p> for (int i=queueNext.size()-1;i>=0;i--){<br /> //copy all elements except the last one to next generation<br /> vector<int> next_queue(queueNext.begin(),queueNext.end());<br /> next_queue.erase(next_queue.begin()+i);<br /> //update current length<br /> double next_currLen=currPathLen+distance[currentPos][queueNext[i]];<br /> if (next_currLen<bestPath){//limitation<br /> backtrack(bestPath,next_currLen,next_queue,queueNext[i],distance,path);<br /> }<br /> }<br /> }<br /> path.pop_back();<br /> }<br /> int main()<br /> {<br /> srand((unsigned)time(NULL));</p> <p> //read data from file<br /> //because backtracking will take much time ,so I use a smaller data set here.<br /> fstream filein("data/ulysses16.tsp.processed",ios::in);</p> <p> if (filein==NULL){<br /> cout<<"cannot open data file"<<endl;<br /> return 1;<br /> }</p> <p> //number of cities<br /> unsigned int cityNum;<br /> //read data from filein<br /> filein>>cityNum;<br /> //standard path<br /> int* standardPath;<br /> standardPath=new int[cityNum];<br /> for (int i=0;i<cityNum;i++){<br /> filein>>standardPath[i];<br /> }<br /> //distance between cities<br /> vector<vector<double> > distance;<br /> for (int i=0;i<cityNum;i++){<br /> vector<double> v;<br /> for (int j=0;j<cityNum;j++){<br /> double d;<br /> filein>>d;<br /> v.push_back(d);<br /> }<br /> distance.push_back(v);<br /> }<br /> //write fileout<br /> fstream fileout("data/result.txt",ios::out);<br /> if (fileout==NULL){<br /> cout<<"cannot open a file to write data"<<endl;<br /> return 1;<br /> }<br /> fileout<<"standard path:"<<endl;<br /> double standardbestlen=0;<br /> for (int i=0;i<cityNum;i++){<br /> fileout<<standardPath[i]<<" ";<br /> }<br /> for (int i=0;i<cityNum-1;i++){<br /> standardbestlen+=distance[standardPath[i]][standardPath[i+1]];<br /> }<br /> standardbestlen+=distance[standardPath[cityNum-1]][standardPath[0]];<br /> fileout<<endl<<"length of standard path: "<<endl<<" "<<standardbestlen<<endl;<br /> cout<<"length of standard path: "<<endl<<" "<<standardbestlen<<endl;</p> <p> //assume start from city 0<br /> vector<int> queueNext;<br /> for (int i=1;i<cityNum;i++){<br /> queueNext.push_back(i);<br /> }<br /> //length of best path found<br /> double best_path_len=1<<(8*sizeof(int)-2);<br /> vector<int> path;<br /> double currentPathLen=0;<br /> int currentPos=0;</p> <p> //timer<br /> time_t start,finish;<br /> start=clock();<br /> backtrack(best_path_len,currentPathLen,queueNext,currentPos,distance,path);<br /> finish=clock();</p> <p> cout<<"time used :"<<finish-start<<" ms"<<endl;<br /> fileout<<"length of best Path found:"<<endl<br /> <<best_path_len<<endl<br /> <<"time used :"<<finish-start<<" ms"<<endl;</p> <p> //free memory/////////////////////////////////////////////////////////////<br /> filein.close();<br /> fileout.close();</p> <p> delete[] standardPath;<br /> return 0;<br /> }