旅行商问题(TSP,Traveling Salesman Problem)

PLE学习法：Problem（问题）、Learning（学习）、Experience（经验）相结合的学习策略 #生活技巧# #学习技巧# #跨学科学习法#

题意：给定一个n个顶点组成的带权有向图的距离矩阵d(I,j)(INF表示没有边)。要求从顶点0出发，经过每个顶点恰好一次后再次回到顶点0.问所经过的边的总权重的最小值是多少?

假设现在已经访问过的顶点的集合(起点0当作还未访问过的顶点)为S，当前所在的顶点为v，用dp[S][v]表示从v出发访问剩余的所有顶点，最终回到顶点0的路径的权重总和的最小值。由于从v出发可以移动到任意的一个节点u(不属于S)，因此有如下递推式

dp[V][0]=0

dp[S][v]=min{(dp[SU{u}][u]+d(v,u)|u(不属于S)}

按照这个递推式进行计算，在这个递推式中，有一个下标是集合而不是普通的整数，稍加处理，试着采用记忆化搜索，虽然有一个下标不是整数，但是可以把它编码成一个整数，或者给它们定义一个全序关系并用二叉搜索树存储，从而可以使用记忆化搜索来求解。特别地，对于集合可以把每一个元素的选取与否对应到一个二进制位里，从而把状态压缩成一个整数，方便了计算和维护。

附上记忆化搜索代码：

#include<bits/stdc++.h>

using namespace std;

const int MAXN=10;

const int INF=0x3f3f3f3f;

int d[MAXN][MAXN];

int dp[1<<MAXN][MAXN];

int n;

int rec(int S,int v)

{

if(dp[S][v]>=0){

return dp[S][v];

}

if(S==(1<<n)-1&&v==0){

return dp[S][v]=0;

}

int res=INF;

for(int u=0;u<n;u++){

if(!(S>>u&1)){

res=min(res,rec(S|(1<<u),u)+d[v][u]);

}

}

return dp[S][v]=res;

}

void solve()

{

memset(dp,-1,sizeof(dp));

printf("%d\n",rec(0,0));

}

int main()

{

int m;

scanf("%d%d",&n,&m);

memset(d,INF,sizeof(d));

int a,b,c;

for(int i=1;i<=m;i++){

scanf("%d%d%d",&a,&b,&c);

d[a][b]=c;

}

solve();

return 0;

}

附上循环求解代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN=10;

const int INF=0x3f3f3f3f;

int n,m;

int d[MAXN][MAXN];

int dp[1<<MAXN][MAXN];

void solve()

{

memset(dp,INF,sizeof(dp));

dp[(1<<n)-1][0]=0;

for(int S=(1<<n)-2;S>=0;S--){

for(int v=0;v<n;v++){

for(int u=0;u<n;u++){

if(!(S>>u&1)){

dp[S][v]=min(dp[S][v],dp[S|1<<u][u]+d[v][u]);

}

}

}

}

printf("%d\n",dp[0][0]);

}

int main()

{

memset(d,INF,sizeof(d));

scanf("%d%d",&n,&m);

int a,b,c;

for(int i=0;i<m;i++){

scanf("%d%d%d",&a,&b,&c);

d[a][b]=c;

}

solve();

return 0;

}

网址：旅行商问题(TSP,Traveling Salesman Problem) https://www.yuejiaxmz.com/news/view/762629

相关内容

旅行商问题+背包问题
旅行商问题
旅行商问题，车辆路径问题的数学规划模型
破解生活难题：揭秘最优化算法在日常生活中的神奇应用
【python】使用C
TSP
基于 STM32 的室内环境监测系统的背景和研究意义
ItiNera
动态规划解决TSP问题
【ML4CO论文精读】基于深度强化学习的组合优化问题研究进展(李凯文, 2020)

随便看看