专栏首页数据魔术师利用动态规划求解旅行商问题时空复杂度分析以及相关实验验证

利用动态规划求解旅行商问题时空复杂度分析以及相关实验验证

利用动态规划求解旅行商问题(Travelling Salesman Problem,简称TSP)在之前的推文中已经有了详细的介绍,今天我们要对这个问题进行更深一步的探索,即随着问题规模的变化,使用动态规划算法求解TSP耗费的时间是多少?耗费的计算机内存又是多少?这都值得我们进一步去探索,为此,我们特地做了一组实验来探索上面的问题。我们实验中使用的计算机的配置如下:

首先对于之前写的代码的时间复杂度(执行算法所需要的计算工作量)进行理论分析,核心代码如下:

double slove(){
    int M = (1 << N);
    dp[1][0] = 0;
    for (int i = 1; i < M; i ++){
        for (int j = 1; j < N; j ++){
            if (i & (1 << j)) continue;
            if (!(i & 1)) continue;
            for (int k = 0; k < N; k ++){
                if (i & (1 << k)){
                    dp[(1 << j) | i][j] = min(dp[(1 << j) | i][j], dp[i][k] + dis[k][j]);
                }
            }
        }
    }
    for (int i = 0; i < N; i ++)
        ans = min(dp[M - 1][i] + dis[i][0], ans);
    return ans;
}

抛开复杂的时间复杂度分析理论不谈,我们知道一般一层for循环就是一个乘数,把每个嵌套的循环次数乘起来最大的那个就是我们的时间复杂度。所以我们上面的代码的时间复杂度应该是O(MN^2),其中N是给定算例的点的个数,而M = 2^N,所以总体的时间复杂度为O(N^2*2^N),是一个指数级的时间复杂度,随着N的增大,其时间代价会顺势快速增长。

为了进一步表现这个时间复杂度的可怕之处,我们令N,也就是完全图中的点的个数,从3变到30生成28个随机算例,做出来的时间图像大概是这样:

由此可见,指数级的算法时间增长还是相当恐怖的。

但是,同时我们要清楚,利用动态规划求解TSP 的空间复杂度(是对一个算法在运行过程中临时占用存储空间大小的量度)同样也是O(N^2*2^N),为此,我们特地测试了同等规模算例的空间使用情况,大概的图像就是这样:

我们使用的计算机最大内存为480G(可以说配置相当高了)。但是,当数据规模达到31个服务点的时候,仍然出现了内存溢出的情况,因此我们制作了如下图的表格来更清晰的表现实验的状况。

可以看出,在数据规模较小的时候,算法消耗的时间和空间甚至都可以忽略不计,但是随着问题规模的扩大,时间和空间消耗都到达了难以忍受的地步。

本文分享自微信公众号 - 数据魔术师(data-magician),作者:贺兴

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-11-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 干货|十分钟教你用动态规划算法解Travelling Salesman Problem(TSP)问题,附代码……

    乍一看标题,大家是不是觉得“动态规划”这四个字组合在一起有点眼熟?似乎哪会儿学过来着……但是吧,细细一琢磨,又忘了它具体是什么、怎么用、用来解决哪些问...

    用户1621951
  • 经典优化算法之分治法(Divide-and-Conque Algorithm)

    分治分治,即分而治之。分治,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即...

    用户1621951
  • 分治法(Divide-and-Conquer Algorithm)经典例子分析

    上一篇文章里给大家介绍了归并排序,今天首先给大家带来同样运用分治法来解决问题的快速排序。

    用户1621951
  • 转载 | 利用动态规划求解旅行商问题(Travelling Salesman Problem)时空复杂度分析以及相关实验验证

    利用动态规划求解旅行商问题(Travelling Salesman Problem,简称TSP)在之前的推文中已经有了详细的介绍,今天我们要对这个问题进行更深一...

    短短的路走走停停
  • 算法训练 K好数

    问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = ...

    AI那点小事
  • 经典算法之动态规划

    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。在面试笔试中动态规划也...

    用户3467126
  • LeetCode 931. 下降路径最小和(动态规划)

    下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

    Michael阿明
  • LeetCode 279. Perfect Squares

    ShenduCC
  • 浙江工业大学校赛 小M和天平

    小M和天平 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

    ShenduCC
  • Golang Leetcode 956. Tallest Billboard.go

    dp思路 dp方程的键为两个柱子之间的高度差,值为当前高度差情况下,两个柱子的最小高度 状态转移的时候有三种情况,其中后两种可以合并 最后dp[0]保存的...

    anakinsun

扫码关注云+社区

领取腾讯云代金券