?? travel.cpp
字號(hào):
#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<<"旅行商問(wèn)題的動(dòng)態(tài)規(guī)劃算法"<<endl;
cout<<"路線長(zhǎng)度的矩陣表示如下,-1表示無(wú)限大"<<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<<"計(jì)算結(jié)果:"<<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;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -