博客
关于我
最大半连通子图
阅读量:578 次
发布时间:2019-03-11

本文共 596 字,大约阅读时间需要 1 分钟。

为了解决给定的有向无环图(DAG)中的最长路径问题,我们可以使用一种基于拓扑排序和动态规划的方法。以下是优化后的解释步骤:

  • 压缩强连通分量:使用tarjan算法对图进行压缩点,以将每个强连通分量(SCC)压缩为一个单一的点。这样处理后的图将不再包含环,可以丰富为DAG。

  • 构建新的DAG:对于每条原始边,如果它连接的两个点在不同的强连通分量中,则在新构建的DAG中添加这条边。这样确保新图中没有环,所有路径都是从一个点到另一点不通过自身。

  • 初始化数组:为每个点分配一个唯一的标识符,并初始化相关数组来记录大小、深度优先搜索时间dfn、最低点low,以及动态规划数组f和g。

  • 拓扑排序:根据tarjan算法的结果,按照拓扑顺序对点进行处理,从最后一个点逆序处理到第一个点。

  • 动态规划计算

    • 从后向前遍历每个点,计算每个点到终点的方案数(g数组),以及达到该点的最大方案数(f数组)。
    • 对每条出边,检查目标点。如果目标点的方案数小于当前点方案数加上目标点大小,则更新目标点的方案数和最大值。
    • 如果方案数相等,则方案数相加并取模,更新目标点的最大值。
  • 结果汇总:遍历所有点,找出最大方案数,并求和对应的方案数总和。

  • 这种方法有效地将最长路径问题转化为动态规划问题,利用了DAG的拓扑顺序,使得计算高效可靠。

    经过这一系列步骤,我们可以轻松地找到DAG中的最长路径及其对应的方案数,解决问题得以完成。

    转载地址:http://xritz.baihongyu.com/

    你可能感兴趣的文章
    [系列] Go gRPC 调试工具
    查看>>
    django-表单之模型表单渲染(六)
    查看>>
    c++之程序流程控制
    查看>>
    yarn出现“There are no scenarios ; must have at least one"
    查看>>
    spring-boot-2.0.3之redis缓存实现,不是你想的那样哦!
    查看>>
    httprunner学习23-加解密
    查看>>
    有道云笔记 同步到我的博客园
    查看>>
    李笑来必读书籍整理
    查看>>
    http头部 Expect
    查看>>
    Hadoop(十六)之使用Combiner优化MapReduce
    查看>>
    《机器学习Python实现_10_06_集成学习_boosting_gbdt分类实现》
    查看>>
    CoreCLR源码探索(八) JIT的工作原理(详解篇)
    查看>>
    IOS开发Swift笔记16-错误处理
    查看>>
    flume使用中的一些常见错误解决办法 (地址已经使用)
    查看>>
    andriod 开发错误记录
    查看>>
    C语言编译错误列表
    查看>>
    看明白这两种情况,才敢说自己懂跨链! | 喵懂区块链24期
    查看>>
    张一鸣:创业7年,我经历的5件事
    查看>>
    git拉取远程指定分支代码
    查看>>
    CentOS5 Linux编译PHP 报 mysql configure failed 错误解决办法
    查看>>