最小成本路径问题

Question

我正在通过动态方法解决最小成本路径问题，但突然我意识到贪婪方法也是有效的。我像这样应用贪婪:选择底部、右侧和对角线成本中的最小值，并在最小成本路径中移动。

1 2 3

4 8 2

1 5 3

其中数字是成本，如果我们包括这一点，它将被添加到所需成本中。从1到3的路径是12到贪婪是8。

如果我的方法没有遵循所有的示例，那么这是什么示例？

Answer 1

下面这样的地图怎么样：

1  1  1
2  10 10
1  1  1

您贪婪的方法最终将采用1+1+1+10+1，而不是1+2+1+1

Answer 2

贪婪算法可以通过几个小步骤给它们一个长长的曲折路径来“击败”它们：

2 2 e
2 ∞ 0
s 3 0

在这种情况下，从s到e将需要

• 贪婪的解决方案:看到2更小，吃力地通过几个3个2，总成本为6
• 动态解决方案:3之后，有一条简单的路径，总成本为3。

另外，我会看看你的两个算法是如何定义长度的。最优路径实际上是1 -> 4 -> 2 -> 3，它的成本是10。如果您的动态解决方案没有返回该值，则可能表明发生了其他事情。