travel.cpp

动态规划算法解决行商问题 VC

#include <list>
#include <iostream>

using namespace std ;

typedef list<int> LISTINT;

LISTINT listAnother;
LISTINT list_result;

int d[4][4]={{-1,2,5,8},{4,-1,7,6},{8,5,-1,6,},{7,5,8,-1}};
int    matrix_length=4;

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(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(4,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;
}