网站布局设计排版,网站外部链接做多少合适呢,水墨风logo一键制作,浙江省建设厅查询官方网站题目#xff1a;TSP旅行商
旅行商问题#xff0c;即TSP问题#xff08;Traveling Salesman Problem#xff09;又译为旅行推销员问题、货郎担问题#xff0c;是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市#xff0c;他必须选择所要走的路径#xff0c;路… 题目TSP旅行商
旅行商问题即TSP问题Traveling Salesman Problem又译为旅行推销员问题、货郎担问题是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市他必须选择所要走的路径路径的限制是每个城市只能拜访一次而且最后要回到原来出发的城市。要求经过的路程为所有路径之中的最小值。
输入 输出22 5 8 0 1 3 0 3 4 1 2 5 2 0 4 2 3 5 3 4 3 4 0 7 4 1 6 思路
如果采用搜索剪枝算法复杂度为O(n!)。
而这种情况下恰好可以考虑状态压缩常用的状态压缩为二进制对应0和1两种状态
当然如果有三种状态的话就要使用3进制哦不对我们应该用4进制因为4进制比3进制更快一点 状态压缩将集合作为整数来记录状态的算法 基于状压的dp是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题 我们设置dp[S][u]表示已经访问的集合为S当前所在的节点为u所对应的最优解 dp[S][u]min{dp[S|{v}][v]g[u][v] }v不属于S 因为dp[S][u]的下个状态就是dp[S|{v}][v] 下面给出记忆化dfs写法一般来讲记忆化dfs比动态规划要快一点因为动态规划往往会在计算无意义的状态中浪费时间。
#include bits/stdc.h//TSP旅行商问题
using namespace std;
int dp[115][20],g[15][15],path[115][15];//path为路径
int n,m,INF;void init(){memset(dp,-1,sizeof(dp));memset(g,0x3f,sizeof(g));INFg[0][0];
}int run(int s,int u){if(dp[s][u]0) return dp[s][u];if(s(1n)-1u0) return dp[s][u]0;int ansINF;for(int v0;vn;v)if(!(sv1)g[u][v]!INF){int tmprun(s|1v,v)g[u][v];if(anstmp){anstmp;path[s][u]v;//保存后继如果不存储集合的话}// ansmin(ans,run(s|1v,v)g[u][v]);不输出路径的写法}return dp[s][u]ans;
}
void print(int s,int u){if(s(1n)-1)return;//这是倒序输出的写法先找到终态然后倒着输出。如果我们存的是前驱那就要正序输出了int vpath[s][u];cout-v;print(s|1v,v);
}
int main(){int u,v,w;cinnm;init();for(int i0;im;i){cinuvw;g[u][v]w;}run(0,0);coutdp[0][0]\n;cout0;print(0,0);//输出路径return 0;
}题目吃馅饼POJ3311
题意一个人从0开始送外卖每次送外卖不超过10个地方给你两两之间所需的时间求送完外卖回到店里的总时间最小每个地方可以经历任意次
输入0表示结束 输出8 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0 思路 因为每个点可以走很多次那么最好就是先把两点间最短距离写出floyd然后就转化成了旅行商问题 因为我们要把所有点都走至少一次那么当旅行商问题可以解出答案时就一定是最佳答案 #include bits/stdc.h
using namespace std;
const int M19,INF0x3f3f3f3f;
int dp[111][M],g[M][M],path[115][15];//path为路径
int n;void init(){memset(dp,-1,sizeof(dp));memset(g,0x3f,sizeof(g));
}void floyd(){for(int k0;kn;k)for(int i0;in;i)for(int j0;jn;j)g[i][j]min(g[i][j],g[i][k]g[k][j]);
}
int TSP(int s,int u){if(dp[s][u]0) return dp[s][u];if(s(1n)-1u0) return dp[s][u]0;int ansINF;for(int v0;vn;v)if(!(sv1)g[u][v]!INF){int tmpTSP(s|1v,v)g[u][v];if(anstmp){anstmp;path[s][u]v;//保存后继如果不存储集合的话}//ansmin(ans,run(s|1v,v)g[u][v]);//不输出路径的写法}return dp[s][u]ans;
}
void print(int s,int u){if(s(1n)-1)return;//这是倒序输出的写法先找到终态然后倒着输出。如果我们存的是前驱那就要正序输出了int vpath[s][u];cout-v;print(s|1v,v);
}
int main(){while(scanf(%d,n)1n){n;//加原点init();for(int i0;in;i)for(int j0;jn;j)scanf(%d,g[i][j]);floyd();memset(dp,-1,sizeof(dp));printf(%d\n,TSP(0,0));cout0;print(0,0);//输出路径}return 0;
}
