TSP--旅行家问题
发布网友
发布时间：2023-03-31 00:58
共1个回答
热心网友
时间：2023-11-07 10:58
假设有矩阵C,储存的数据是两个顶点之间的距离，TSP问题采用贪心策略:从任意的城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。
#include<bits/stdc++.h>
using namespace std;
//TSP问题 --假设旅行家要旅行n个城市，要求每个城市经历且只经历一次然后回到出发城市，并要求所走的路程最短
const int n=5;
const int MAX=10000;
int TSP(int arc[n][n],int w)// arc[n][n]是一个矩阵，表示两个点之间的距离 ,w是起始顶点的下标
{
int edgeNum=0,TSPLength=0;//边的数量 最小路径的值
/*
min用来保存矩阵中每一行数据的最小值
u用来保存每一行矩阵
v用来保存每一列矩阵
*/
int min,u,v;
int flag[n]={0}; //未加入最短路径的顶点，初始值都为1
u=w;//u的初始值为w
flag[w]=1;//w加入最短路径
while (edgeNum<n-1) //边数=顶点数-1
{
min=100; //每次循环都让min=100
for(int j=0;j<n;j++) //求当前行的最小值 即arc[u]的最小值
{
if((flag[j]==0)&&(arc[u][j]!=0)&&arc[u][j]<min) { //未加入最小路径 arc[u][j]！=0
v=j; //v是最小值所在的列
min=arc[u][j]; //min是最小值
}
}
TSPLength+=arc[u][v];//计算最小路径
flag[v]=1;//加入的顶点标记为1
edgeNum++;
cout<<u<<"-->"<<v<<endl;//输出经过的路径
u=v;//下一次从顶点v出发
}
cout<<v<<"-->"<<w;//回到起点
return (TSPLength+arc[u][w]);
}
int main()
{
int arc[n][n]={
{MAX,3,3,2,6},
{3,MAX,7,3,2},
{3,7,MAX,2,5},
{2,3,2,MAX,3},
{6,2,5,3,MAX},
};
int length=TSP(arc,0) ;
cout<<endl<<length;
return 0;
}
此问题用贪心求的结果不是最优解，而是局部最优解，因为本题的最短路径是13，路线是1->2->5->4->3->1
