代码之家 › 专栏 › 技术社区 › Make42

动态规划:我有重叠的子问题吗?

dynamic-programming recursion algorithm

Make42 · 技术社区 · 6 年前

假设我有一个实数的二维数组。我从这个数组中的一个特定单元格开始,其中有一个特别大的数字。我想标记其他单元格中的哪个应该属于所提到的起始单元格。规则是这样的:如果我想办法从起始单元格走到另一个单元格,那么另一个单元格就属于起始单元格。我只能在牢房里走来走去。我只能从一个号码高的牢房走到一个号码低的牢房。这里有一个例子,当我从中心9开始

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

现在是第二个方面,我不仅对一个起始单元格这样做,而且对多个起始单元格这样做

动态规划

dynamic programming 发现应用动态规划需要满足两个条件:

子问题需要有最优子结构

“[动态规划]是指以递归的方式将一个复杂的问题分解成更简单的子问题来简化问题[……]如果一个问题可以通过将其分解成子问题然后递归地找到子问题的最优解来进行优化求解,那么它就被称为具有最优子结构。[…]要使动态规划适用,问题必须具有两个关键属性:最优子结构和重叠子问题。如果一个问题可以通过结合非重叠子问题的最优解来解决,则该策略被称为“分而治之”。这就是为什么合并排序和快速排序不属于动态规划问题。最优子结构是指一个给定优化问题的解可以通过其子问题的最优解的组合得到。这种优化子结构通常用递归的方法来描述。[…]重叠子问题意味着子问题的空间必须很小,也就是说,任何解决问题的递归算法都应该反复解决相同的子问题,而不是产生新的子问题。” Wikipedia

假设我们从左图中的橙色9开始,沿着绿色的小路一直走到蓝色5。从那里我们还可以到达蓝色3号和蓝色2号。我们完成了左边橙色9的算法。

这就是为什么我认为我的整个问题可以用动态规划来解决。

我的算法/问题是动态规划吗?为什么,为什么不?

1 回复 | 直到 6 年前

Matt Timmermans 6 年前

是的,这当然是一个动态规划问题。这实际上是最简单/最基本的动态规划问题——在有向无环图(在您的例子中是多个开始节点)中找到从一个开始节点可以到达的所有节点。你可以用深度优先搜索或广度优先搜索来解决这个问题。

它符合这样的定义:

最佳结构?是的,我能从一个细胞x上得到的细胞是x加上我能从x的小邻居那里得到的细胞的并集。

重叠子问题?是的,x的两个邻居可以共享同一个较小的邻居。

function Step(cellNr):
    foreach neighborNr in neighbors_of(cellNr):
        if array_value(neighborNr) < array_value(cellNr) AND cell_is_not_marked(neighborNr):
            mark_cell(neighborNr)
            Step(neighborNr)
Step(centerNr)

请注意,这也会将算法从指数时间更改为线性时间,这是一种深度优先搜索

推荐文章

SkyWalker · 在JavaScript中,合并日期-时间序列的有效算法是什么?

1 年前

root · 计数算法

1 年前

André Silveira · 使用循环将数组的每个槽递增1。数组的大小是传递给函数的参数

2 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Manny · 如何比较Perl中的字符串?

2 年前

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Diret · 获取范围内每个数字的子倍数的算法

2 年前

Saif · 排序时python如何决定何时调用比较器?

2 年前

TryingToLearn · 我如何为通用遥控器构造一个类,该遥控器向连接到它的各种设备发送开/关命令?

2 年前

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前