首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

旅行商问题(动态规划方法,超级详细的)

  • 25-03-07 18:02
  • 2554
  • 5284
blog.csdn.net

一、题目

  • 一个售货员必须访问n个城市,恰好访问每个城市一次,并最终回到出发城市。
    售货员从城市i到城市j的旅行费用是一个整数,旅行所需的全部费用是他旅行经过的的各边费用之和,而售货员希望使整个旅行费用最低。
  • (等价于求图的最短哈密尔顿回路问题)令G=(V, E)是一个带权重的有向图,顶点集V=(v0, v1, ..., vn-1)。从图中任一顶点vi出发,经图中所有其他顶点一次且只有一次,最后回到同一顶点vi的最短路径。

二、测试用例

 

其中1,2,3,4,5代表五个城市。此模型可抽象为图,可用邻接矩阵c表示,如下图所示:

三、动态规划方程

 假设从顶点s出发,令d(i, V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次,最后回到出发点s的最短路径长度。

        推导:(分情况来讨论)

        ①当V为空集,那么d(i, V),表示直接从i回到s了,此时d(i,V) = c_{is} 且 (i\neq s)

        ②如果V不为空,那么就是对子问题的最优求解。你必须在V这个城市集合中,尝试每一个,并求出最优解。

          d(i,V)=min(Cik+d(k,V−(k))d(i,V)=min(Cik+d(k,V−(k))

           注:c_{ik}表示选择的城市和城市i的距离,d(k, V-(k))是一个子问题。

        综上所述,TSP问题的动态规划方程就出来了:

四、用例分析

 

现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)

这里只画出了d(1,{2,3,4}),由于篇幅有限这里就不画了。

 

①我们要求的最终结果是d(0,{1,2,3,4}),它表示,从城市0开始,经过{1,2,3,4}之中的城市并且只有一次,求出最短路径.。
②d(0,{1,2,3,4})是不能一下子求出来的,那么他的值是怎么得出的呢?看上图的第二层,第二层表明了d(0,{1,2,3,4})所需依赖的值。那么得出:
      
     ③d(1,{2,3,4}),d(2,{1,3,4}),d(3,{1,2,4}),d(4,{1,2,3})同样也不是一步就能求出来的,它们的解一样需要有依赖,就比如说d(1,{2,3,4})

      d(2,{1,3,4}),d(3,{1,2,4}),d(4,{1,2,3})同样需要这么求。

    ④按照上面的思路,只有最后一层的,当V为空集时,就可以满足d(i,V) = c_{is} 且 (i\neq s)该条件,直接求出dp数组部分的值。

五、数据结构

由上述动态规划公式d(i,V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次,最后回到出发点s的最短路径长度。根据上述给的测试用例有5个城市编号0,1,2,3,4。那么访问n个城市,恰好访问每个城市一次,并最终回到出发城市的嘴短距离可表示为d(0,{1,2,3,4}),那么问题来了我们用什么数据结构表示d(i,V),这里我们就可二维数据dp[N][M]来表示,N表示城市的个数,M表示集合的数量,即M = 2^{N-1},之所以这么表示因为集合V有2^{N-1}个子集。根据测试用例可得出如下dp数组表格:

 

 

那么你们可能就有疑问了,为什么这么表示?这里说明一下比如集合{1,2,3,4}为什么用15表示,我们可以把 集合中元素看成二进制1的位置(二进制从右开始看),1表示从右开始第一位为1,2表示从又开始第二位为1,所以集合{1,2,3,4}可表示二进制(1111)转化为十进制为15。再举个例子比如集合{1,3}表示为二进制为0101,十进制为5。所以我们求出dp[0][15](通用表示dp[0][2N−1−12N−1−1])就是本题的最终解。

注意:

  • 对于第y个城市,他的二进制表达为,1<<(y-1)。
  • 对于数字x,要看它的第i位是不是1,那么可以通过判断布尔表达式 (((x >> (i - 1) ) & 1) == 1或者(x  & (1<<(i-1)))!= 0的真值来实现。
  • 由动态规划公式可知,需要从集合中剔除元素。假如集合用索引x表示,要剔除元素标号为i,我们异或运算实现减法,其运算表示为: x = x ^ (1<<(i - 1))。

六、最短路径顶点的计算

我们先计算dp[N][M]数组之后,我可以用dp数组来反向推出其路径。其算法思想如下:

比如在第一步时,我们就知道那个值最小,如下图所示:

因为dp[][]数组我们已经计算出来了,由计算可知C01+d(1,{2,3,4})最小,所以一开始从起始点0出发,经过1。接下来同样计算d(1,{2,3,4})

由计算可知C14+d(4,{2,3})所以0--->1---->4,接下来同理求d(4,{2,3}),这里就省略,读者可以自行计算。最终计算出来的路径为:0--->1--->4--->2--->3--->0

七、代码编写

 

  1. #include
  2. #include
  3. #include
  4. #include
  5. using namespace std;
  6. #define N 5
  7. #define INF 10e7
  8. #define min(a,b) ((a>b)?b:a)
  9. static const int M = 1 << (N-1);
  10. //存储城市之间的距离
  11. int g[N][N] = {{0,3,INF,8,9},
  12. {3,0,3,10,5},
  13. {INF,3,0,4,3},
  14. {8,10,4,0,20},
  15. {9,5,3,20,0}};
  16. //保存顶点i到状态s最后回到起始点的最小距离
  17. int dp[N][M] ;
  18. //保存路径
  19. vector<int> path;
  20. //核心函数,求出动态规划dp数组
  21. void TSP(){
  22. //初始化dp[i][0]
  23. for(int i = 0 ; i < N ;i++){
  24. dp[i][0] = g[i][0];
  25. }
  26. //求解dp[i][j],先跟新列在更新行
  27. for(int j = 1 ; j < M ;j++){
  28. for(int i = 0 ; i < N ;i++ ){
  29. dp[i][j] = INF;
  30. //如果集和j(或状态j)中包含结点i,则不符合条件退出
  31. if( ((j >> (i-1)) & 1) == 1){
  32. continue;
  33. }
  34. for(int k = 1 ; k < N ; k++){
  35. if( ((j >> (k-1)) & 1) == 0){
  36. continue;
  37. }
  38. if( dp[i][j] > g[i][k] + dp[k][j^(1<<(k-1))]){
  39. dp[i][j] = g[i][k] + dp[k][j^(1<<(k-1))];
  40. }
  41. }
  42. }
  43. }
  44. }
  45. //判断结点是否都以访问,不包括0号结点
  46. bool isVisited(bool visited[]){
  47. for(int i = 1 ; i
  48. if(visited[i] == false){
  49. return false;
  50. }
  51. }
  52. return true;
  53. }
  54. //获取最优路径,保存在path中,根据动态规划公式反向找出最短路径结点
  55. void getPath(){
  56. //标记访问数组
  57. bool visited[N] = {false};
  58. //前驱节点编号
  59. int pioneer = 0 ,min = INF, S = M - 1,temp ;
  60. //把起点结点编号加入容器
  61. path.push_back(0);
  62. while(!isVisited(visited)){
  63. for(int i=1; i
  64. if(visited[i] == false && (S&(1<<(i-1))) != 0){
  65. if(min > g[i][pioneer] + dp[i][(S^(1<<(i-1)))]){
  66. min = g[i][pioneer] + dp[i][(S^(1<<(i-1)))] ;
  67. temp = i;
  68. }
  69. }
  70. }
  71. pioneer = temp;
  72. path.push_back(pioneer);
  73. visited[pioneer] = true;
  74. S = S ^ (1<<(pioneer - 1));
  75. min = INF;
  76. }
  77. }
  78. //输出路径
  79. void printPath(){
  80. cout<<"最小路径为:";
  81. vector<int>::iterator it = path.begin();
  82. for(it ; it != path.end();it++){
  83. cout<<*it<<"--->";
  84. }
  85. //单独输出起点编号
  86. cout<<0;
  87. }
  88. int main()
  89. {
  90. TSP();
  91. cout<<"最小值为:"<0][M-1]<
  92. getPath();
  93. printPath();
  94. return 0;
  95. }

 

八、测试结果及性能分析 

时间复杂度:O(2^{n}n^{2})

空间复杂度:O(2^{n})

九、更多动态规划相关题目

动态规划经典题目-数据压缩之图像压缩

动态规划经典题目-数据压缩之文本压缩

动态规划经典题目-矩阵链乘法

动态规划经典题目-字符串切分

动态规划经典题目-字符串的编辑距离

动态规划经典题目-最长单调递增子序列

动态规划经典题目-最长公共子串

动态规划经典题目-最长公共子序列

动态规划经典题目-找零钱的方案数

动态规划经典题目-找零钱的最少硬币数

动态规划经典题目——滑雪问题(递归+记忆化搜索)

动态规划经典题目——0-1背包

动态规划经典题目——最大子矩阵和

动态规划经典题目——数塔问题

动态规划经典题目——最大连续子序列之和

动态规划系列——原理与思想

文章知识点与官方知识档案匹配,可进一步学习相关知识
算法技能树首页概览64429 人正在系统学习中
注:本文转载自blog.csdn.net的仁者乐山智者乐水的文章"https://blog.csdn.net/qq_39559641/article/details/101209534"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

101
推荐
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top