using namespace std
double graph[25][25]
int vis[25]
double a[25]
double ub
double ans
struct point {
int x
int y
}p[25]
double dis(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
}
void dfs(int n, int x, double temp, int cnt)
{
//printf("%.2lf\n", temp)
if(cnt == n-2)
{
ub = min(ub, temp+graph[x][n-1])
return
}
vis[x]=1
for(int i=0i<n-1i++)
{
if(graph[x][i] &&!vis[i])
{
temp += graph[x][i]
if(temp <ub)
dfs(n, i, temp, cnt+1)
temp -= graph[x][i]
vis[i]=0
}
}
}
int main()
{
int t, n, x, y
scanf("%d", &t)
while(t--)
{
int cnt=0
ub=0x3f3f3f3f
double temp=0
memset(graph, 0, sizeof(graph))
memset(vis, 0, sizeof(vis))
scanf("%d", &n)
for(int i=0i<ni++)
scanf("%d%d", &p[i].x, &p[i].y)
for(int i=0i<ni++)
for(int j=0j<nj++)
graph[i][j] = dis(p[i], p[j])
vis[0]=1
dfs(n,0,temp,0)
printf("%.2lf\n", ub)
}
return 0
}
旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。解决TSP问题的思想有回溯法、贪心法、动态规划法等。
如果动态规划法解决TSP问题，可以参考程序代码：
#include <list>
#include <iostream>
using namespace std
typedef list<int>LISTINT
LISTINT listAnother
LISTINT list_result
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}
int matrix_length=4
int getPath(int n,LISTINT list_org)
{
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
}
}
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
}
for(int j=2j<nj++)
{
i=list_org.begin()
for(int k=1k<jk++)
{
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)
if(tempvalue<minValue)
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org
}
minValue=tempvalue
}
}
}
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=0j<matrix_lengthj++){
cout<<endl
for(int k=0k<matrix_lengthk++){
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
}
#include <list>#include <iostream>
using namespace std
typedef list<int>LISTINT
LISTINT listAnother
LISTINT list_result
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-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=2j<nj++)
{
i=list_org.begin()
for(int k=1k<jk++){
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=0j<matrix_lengthj++){
cout<<endl
for(int k=0k<matrix_lengthk++){
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
}
