【编程练习】TSP问题与最短路径
TSP
暴⼒枚举法：此⽅法不适合城市个数>8的。时间复杂度成阶乘上升
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxx 9999
int l[maxx][maxx];//存储两个城市之间的距离
int n;//城市数量
int min_l = maxx;//最短路径
int sum[maxx];//标记每条路线的路程总长度
int go_city;//标记从第go_city个城市出发
int visited[maxx]; //第i个城市已经去过：visited[i]=1；反之则为visited[i]=0;
int path_index = 1; //已经去过的城市数⽬。
int path[maxx][maxx];//存储经过城市的路线
int route = 0;//存储第⼏条路线
int recursion(int index)
{
if(path_index != n)
{
for(int i=1;i <= n;i++)
{
if(visited[i] == 0)
{
visited[i] = 1;
path[route][path_index] = index;
path_index++;
recursion(i);
//回溯
path_index--;
visited[i] = 0;
}
}
}
else
{
//路线中加上最后⼀个城市和第⼀个城市（需要返回到最初的城市）
path[route][path_index] = index;
path[route][path_index + 1] = go_city;
//计算每条路线的路程总长度，并输出路线
printf("路线%d为：\n",route+1);
cstring转为intsum[route] = 0;
for(int i=1;i<=n;i++)
{
sum[route] += l[ path[route][i] ][ path[route][i+1] ];
cout << path[route][i] << " --> ";
//当route+1后，path[route][i]的前⾯需要保持，后⾯变化。
path[route+1][i] = path[route][i];
}
if(min_l > sum[route])
{
min_l = sum[route];
}
cout << path[route][n+1] << endl;
cout << "该路线总长度为： " << sum[route] << endl;
route++;
}
return 0;
}
int main()
{
memset(visited,0,sizeof(visited));
cout << "请输⼊城市数量：";
cin >> n;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
printf("请输⼊%d号城市到%d号城市之间的距离:",i,j);            cin >> l[i][j];
l[j][i] = l[i][j];
}
}
cout << "请输⼊您出发的城市是第⼏个城市：";
cin >> go_city;
visited[go_city] = 1;
recursion(go_city);
cout << "最短路程长度为: ";
cout << min_l << endl;
return 0;
}
动态规划法
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxx 10000
using namespace std;
int n;//城市数量
int l[maxx][maxx];//城市之间的距离
int dp[maxx][maxx];//dp表
int menthod()
{
//给第⼀列赋值
for (int i = 0; i < n; i++)
{
dp[i][0] = l[i][0];
}
//给其他列赋值
for (int j = 1; j < 1 << (n - 1); j++)
{
for (int i = 0; i < n; i++)
{
dp[i][j] = 0x7ffff; //表⽰⽆穷⼤
//判断是否⾛过该城市j，如果⾛过了，就continue
if (j >> (i - 1) & 1)
{
continue;
}
for (int k = 1; k < n; k++)
{
/
/通过位运算判断是否需要经过k城市，不能经过k城市就continue
if ((j >> (k - 1) & 1) == 0)
{
continue;
}
//获取dp[i][j]的最⼩值，(l[i][k] + dp[k][j ^ (1 << (k - 1))这个在思路上有解释    if (dp[i][j] > (l[i][k] + dp[k][j ^ (1 << (k - 1))]))
{
dp[i][j] = l[i][k] + dp[k][j ^ (1 << (k - 1))];
}
}
}
}
return 0;
}
int main()
{
memset(dp, 0, sizeof(dp));
cout << "请输⼊城市数⽬：";
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
printf("请输⼊第 %d 号城市到第 %d 号城市之间的距离：", i, j);
cin >> l[i][j];
l[j][i] = l[i][j];
}
}
menthod();
cout << "最短路径为： " << dp[0][(1 << (n - 1))-1] << endl;
return 0;
}
最短路径问题
（1）所有点到点的
原理：对边进⾏“松弛”，v1到v3的距离 如果 ⼤于v1 到v2+v2到v3 则更新v1-v3的最⼩值。
也就是说v1到v3的距离可以通过v2这个点进⾏更新。
Floyd：
int i,j,k;
for(k=0;k<n;k++)//代表中转结点
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(v[i][j]<v[i][k]+v[k][j])//v[i][j]表⽰结点i到j的距离
v[i][j]=v[i][k]+v[k][j];
}
o(n^3)可得到所有结点之间的最短路径长度。
核⼼代码如上，邻接矩阵的初始化和注意初始值取⼤数的问题。
单源最短路-迪杰斯特拉
假设⼀共n个点，可求得点x到剩余n-1个点的最短路。原理相似。
每次取出距离当前点最近的点，利⽤相邻点进⾏“松弛操作”更新dis数组。最终dis数组保存的值代表了结点0到剩余结点的最短距离。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=0x3f3f3f3f;
int map[110][110];
int dis[110];
int visit[110];
/*
关于三个数组：map数组存的为点边的信息，⽐如map[1][2]=3，表⽰1号点和2号点的距离为3 dis数组存的为起始点与每个点的最短距离，⽐如dis[3]=5，表⽰起始点与3号点最短距离为5 visit数组存的为0或者1，1表⽰已经⾛过这个点。
*/
int n,m;
int dijkstra()
{
int i,j,pos=1,min,sum=0;
memset(visit,0,sizeof(visit));//初始化为0，表⽰开始都没⾛过
for(i=1; i<=n; i++)
{
dis[i]=map[1][i];
}
visit[1]=1;
dis[1]=0;
int T=n-1;
while(T--)
{
min=MAX;
for(j=1; j<=n; j++)
{
if(visit[j]==0&&min>dis[j])
{
min=dis[j];
pos=j;
}
}
visit[pos]=1;//表⽰这个点已经⾛过
for(j=1; j<=n; j++)
{
if(visit[j]==0&&dis[j]>min+map[pos][j])//更新dis的值
dis[j]=map[pos][j]+min;
}
}
return dis[n];
}
int main()
{
int i,j;
while(cin>>n>>m)//n表⽰n个点，m表⽰m条边
{
memset(map,MAX,sizeof(map));
int a,b,c;
for(i=1; i<=m; i++)
{
cin>>a>>b>>c;
if(c<map[a][b])//防⽌有重边
map[a][b]=map[b][a]=c;
}
int sum=dijkstra();
cout<<sum<<endl;
}
return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。