美文网首页
动态规划算法

动态规划算法

作者: 三方斜阳 | 来源:发表于2021-08-05 22:06 被阅读0次

算法基本思想:

  • 将复杂问题分解为若干子问题
  • 先求解子问题,重复利用子问题的解求得原问题的解

基本要素:

  • 最优子结构性质
  • 重叠子问题

基本步骤:

建立状态转移方程 -> 存储并复用之前的结果 -> 自底向上求解

应用:

条件随机场(CRF)
概率无向图模型、判别模型
常用于序列标注任务的推理层

序列标注:给定输入X=<x1,x2,x3,...xn> 给出对应的标注Y=<y1,y2,y3,...yn> y∈{tag|有限的标签种类}
推理层:学习状态转移参数/解

总结:

  • 动态规划算法可以降低时间复杂度,代价为提高了空间复杂度
  • 可以找到全局最优解
  • 如何分解为可以被重复调用的子问题(找到状态转移方程)是难点

相关文章

  • 动态规划算法

    动态规划算法 最长上升子序列

  • 维特比算法

    维特比(Viterbi)算法是一种动态规划算法,在处理隐马尔可夫(HMM)最优路径问题时经常被使用. 动态规划算法...

  • 最短路径解决方法

    Floyd算法;Dijkstra算法;Bellman-Ford算法;动态规划算法

  • 背包问题

    介绍 学习动态规划算法的经典例题。动态规划算法一般有3个特征1、最优化原理:最优解所包含的子问题的解也是最优的。2...

  • 动态规划算法(01背包问题)

    一. 动态规划算法介绍: 动态规划算法和分治算法类似,也是将待求解问题分成若干个小问题一步步求解,不同的是,每一个...

  • 基础算法

    二分查找 冒泡排序(优化) 归并排序 动态规划算法

  • 动态规划入门

    1.什么是动态规划动态规划是在前面已有答案的基础上向下递推的过程 动态规划算法的两种形式上面已经知道动态规划算法的...

  • 【JS算法】动态规划 - 斐波那契数列

    动态规划算法 动态规划算法的核心思想是:将大问题划分为小问题进行解决,从而一步步获取最优解的处理算法。其基本思想也...

  • 2019-11-04 回溯算法

    package others; import java.util.Arrays; /** 动态规划算法计算10个工...

  • 动态规划

    动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...

网友评论

      本文标题:动态规划算法

      本文链接:https://www.haomeiwen.com/subject/qutvvltx.html