?? tsp_dp.cpp
字號:
#include <list>
#include <iostream>
#include <string>
using namespace std ;
typedef list<int> LISTINT;
typedef struct {
int minDist; //最短距離
LISTINT path; //最優路徑
} minPath;
#define N 6 //輸入矩陣大小
#define MAX 65535
int D[N][N]={{0,10,20,30,40,50}, //輸入鄰接矩陣D
{12,0,18,30,25,21},
{23,19,0,5,10,15},
{34,32,4,0,8,16},
{45,27,11,10,0,18},
{56,22,16,20,12,0}};
minPath TSP(int i, LISTINT S)
{
int dist,min=MAX;
int nextcity; //保存最優路徑上,S中的第一個城市
minPath temp1,temp; //用于保存中間結果以及處理返回值
if(S.empty())
{
temp.minDist=D[i][0];
temp.path.push_back(0);
return temp;
}
for(int n=S.size();n>0;n--) //循環n次,每次取出一個元素
{
LISTINT Sub(S);
int j=S.front(); //取出S中第一個元素j
S.pop_front();
S.push_back(j); //S中元素循環左移1位
Sub.pop_front(); //Sub = S\{j}
temp1.path.clear();
temp1=TSP(j,Sub);
dist = D[i][j]+temp1.minDist;
if(dist<min) //尋找i出發,經過S中每個城市一次
{ //且僅一次并最后返回城市i的最短距離
min=temp.minDist=dist;
temp.path.clear();
while(!temp1.path.empty()){
temp.path.push_back(temp1.path.front());
temp1.path.pop_front();
}
nextcity=j;
}
}
temp.path.push_back(nextcity);
return temp;
}
void PrintPath(minPath p) //打印結果
{
cout<<"The shortest distance is: ";
cout<<p.minDist<<endl;
cout<<"The best path is: ";
cout<<"v1";
while(!p.path.empty()){
cout<<"->v"<<(p.path.back()+1);
p.path.pop_back();
}
cout<<endl;
}
void main()
{
LISTINT S;
for(int i=1;i<N;i++) //初始化集合S
S.push_back(i); //v1,v2,v3,v4,v5,v6 分別對應 0,1,2,3,4,5,6
PrintPath(TSP(0,S));
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -