tsp.rar_TSP dynamic_salesman_tsp 旅行商_旅行商_旅行商问题

#include <list> #include <iostream> using namespace std ; typedef list<int> LISTINT; LISTINT listAnother; LISTINT list_result; int d[5][5]={{-1,20,30,10,11},{15,-1,16,4,2},{3,5,-1,2,4},{19,6,18,-1,3},{16,4,7,16,-1}}; int matrix_length=5; int getPath(int n,LISTINT list_org) { // cout<<"-------------------"<<n<<"-start-------"<<endl; LISTINT::iterator i; int minValue; if(n==1){ i=list_org.begin(); minValue= d[*i-1][0]; if(list_org.size()==matrix_length-1){ list_result=list_org; } //cout<<"---"<<*i<<"-"<<"1"<<"="<<minValue<<endl; } else{ int temp; i=list_org.begin(); temp=*i; list_org.erase(i); i=list_org.begin(); minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org); if(list_org.size()==matrix_length-1){ list_result=list_org; } /* cout<<"----"<<temp<<"--"<<*(i)<<"="<<minValue<<"--链表里还剩有如下元素"; for (i = list_org.begin(); i != list_org.end(); ++i) cout << *i << " "; cout << endl; */ for(int j=2;j<n;j++) { i=list_org.begin(); for(int k=1;k<j;k++){ i++; } int tempvalue=*i; list_org.erase(i); list_org.push_front(tempvalue); i=list_org.begin(); tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org); /* cout<<"----"<<"---"<<temp<<"--"<<*(i)<<"="<<tempvalue<<"--所有的"; for (i = list_org.begin(); i != list_org.end(); ++i) cout << *i << " "; cout << endl; */ if(tempvalue<minValue){ if(list_org.size()==matrix_length-1){ list_result=list_org; } minValue=tempvalue; } } } //cout<<"-------------------"<<n<<"---end-----"<<endl; return minValue; } int main(int argc, char* argv[]) { LISTINT list_org; LISTINT::iterator h; list_org.push_front(5); list_org.push_front(4); list_org.push_front(3); list_org.push_front(2); list_org.push_front(1); cout<<"旅行商问题的动态规划算法"<<endl; cout<<"路线长度的矩阵表示如下,-1表示无限大"<<endl; for(int j=0;j<matrix_length;j++){ cout<<endl; for(int k=0;k<matrix_length;k++){ cout<<" "<<d[j][k]; } } cout<<endl; cout<<"计算结果:"<<getPath(5,list_org)<<endl; list_result.push_front(1); list_result.push_back(1); cout<<"走的路径:---->:"; for (h = list_result.begin(); h != list_result.end(); ++h) cout << *h << " "; cout << endl; int i; cin>>i; return 0; }