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

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

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、题目

  • 一个售货员必须访问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(C_{ik} + 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][2^{N-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

七、代码编写

 

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

#define N 5
#define INF 10e7
#define min(a,b) ((a>b)?b:a)

static const int M = 1 << (N-1);
//存储城市之间的距离
int g[N][N] = {
  
  {0,3,INF,8,9},
               {3,0,3,10,5},
               {INF,3,0,4,3},
               {8,10,4,0,20},
               {9,5,3,20,0}};
//保存顶点i到状态s最后回到起始点的最小距离
int dp[N][M] ;
//保存路径
vector<int> path;

//核心函数,求出动态规划dp数组
void TSP(){
    //初始化dp[i][0]
    for(int i = 0 ; i < N ;i++){
        dp[i][0] = g[i][0];
    }
    //求解dp[i][j],先跟新列在更新行
    for(int j = 1 ; j < M ;j++){
        for(int i = 0 ; i < N ;i++ ){
            dp[i][j] = INF;
            //如果集和j(或状态j)中包含结点i,则不符合条件退出
            if( ((j >> (i-1)) & 1) == 1){
                continue;
            }
            for(int k = 1 ; k < N ; k++){
                if( ((j >> (k-1)) & 1) == 0){
                    continue;
                }
                if( dp[i][j] > g[i][k] + dp[k][j^(1<<(k-1))]){
                    dp[i][j] = g[i][k] + dp[k][j^(1<<(k-1))];
                }
            }
        }
    }

}
//判断结点是否都以访问,不包括0号结点
bool isVisited(bool visited[]){
    for(int i = 1 ; i<N ;i++){
        if(visited[i] == false){
            return false;
        }
    }
    return true;
}
//获取最优路径,保存在path中,根据动态规划公式反向找出最短路径结点
void getPath(){
    //标记访问数组
    bool visited[N] = {false};
    //前驱节点编号
    int pioneer = 0 ,min = INF, S = M - 1,temp ;
    //把起点结点编号加入容器
    path.push_back(0);

    while(!isVisited(visited)){
        for(int i=1; i<N;i++){
            if(visited[i] == false && (S&(1<<(i-1))) != 0){
                if(min > g[i][pioneer] + dp[i][(S^(1<<(i-1)))]){
                    min = g[i][pioneer] + dp[i][(S^(1<<(i-1)))] ;
                    temp = i;
                }
            }
        }
        pioneer = temp;
        path.push_back(pioneer);
        visited[pioneer] = true;
        S = S ^ (1<<(pioneer - 1));
        min = INF;
    }
}
//输出路径
void printPath(){
    cout<<"最小路径为:";
    vector<int>::iterator  it = path.begin();
    for(it ; it != path.end();it++){
        cout<<*it<<"--->";
    }
    //单独输出起点编号
    cout<<0;
}

int main()
{
    TSP();
    cout<<"最小值为:"<<dp[0][M-1]<<endl;
    getPath();
    printPath();
    return 0;
}

 

八、测试结果及性能分析 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164401.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • wordpress博客添加新浪微博挂件

    wordpress博客添加新浪微博挂件我一直想着把我的新浪微博嵌入到博客中,今天抽空到网上搜索了一下相关的插件,没有找到。后来看到了一篇如何把微博嵌入WordPress博客的方法,终于实现成功了。感谢分享这些的朋友们。一直想着把我的新浪微博嵌入到博客中,今天终于等来了这个功能的实现。想让你的博客读者顺带看看你的微博吗?新浪微博现在可以嵌入到多种博客之中了,这篇讲讲如何在w…

  • ctrl+c复制,ctrl+v粘贴_C C T V 8

    ctrl+c复制,ctrl+v粘贴_C C T V 8从Windows世界走入Mac世界,最让不习惯的是在Mac中“复制/粘贴”的快捷键是Command+C/V,而且Command键与C/V键靠得太近,只能用大拇指与食指进行操作,也让人不习惯。再加上远程

  • mask rcnn训练自己的数据集_fasterrcnn训练自己的数据集

    mask rcnn训练自己的数据集_fasterrcnn训练自己的数据集这篇博客是基于GoogleColab的maskrcnn训练自己的数据集(以实例分割为例)文章中数据集的制作这部分的一些补充温馨提示:实例分割是针对同一个类别的不同个体或者不同部分之间进行区分我的任务是对同一个类别的不同个体进行区分,在标注的时候,不同的个体需要设置不同的标签名称在进行标注的时候不要勾选labelme界面左上角File下拉菜单中的StayWithImagesData选项否则生成的json会包含Imagedata信息(是很长的一大串加密的软链接

  • mysql 多表查询和更新_MySQL update select 多表关联查询更新

    mysql 多表查询和更新_MySQL update select 多表关联查询更新在遇到需要update设置的参数来自从其他表select出的结果时,需要把update和select结合使用,不同数据库支持的形式不一样,在mysql中如下:updateAinnerjoin(selectid,namefromB)conA.id=c.idsetA.name=c.name;根据AB两个表的id相同为条件,把A表的name修改为B的sql语句就如上所示参考…

  • 雷军反击董明珠:感觉董总好像认输了似的

    雷军反击董明珠:感觉董总好像认输了似的

  • PahoMQTT_mqtt安装

    PahoMQTT_mqtt安装1.安装npminstall paho-mqtt-s2.初始化constPahoMQTT=require(‘paho-mqtt’)constname=newDate().getTime()+’client’constclient=newPahoMQTT.Client(‘www.100link.net’,Number(61615),nam…

    2022年10月31日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号