algorithm - 选择贪心算法找到成本最低的路径

Question

我有一个数字金字塔。每个数字代表关联的点数。我需要使用贪心算法来找到从金字塔顶部到底部的成本最低的路径。我读过关于不知情和知情的搜索算法，但我仍然不知道该选择什么。你觉得什么最适合这类问题？贪婪的最佳优先搜索/A* 搜索还是其他？这是一个如此简单的问题，但我并没有使用所有这些算法来知道什么是最佳选择。正如我所说，它必须是一个贪心算法。

Answer 1

如果您不必使用这里不正确的贪心算法。对于这类问题，您自然会使用一种称为“动态规划”的技术。

您将金字塔的所有正方形（您进行备份）初始化为无穷大 - 除了具有自己价值的初始点。

你从上到下逐行处理金字塔。您尝试从第一行（所以唯一的一个是顶部）去任何地方，然后更新第二行的节点，给它们顶部的值 + 它们的值。然后移动到第二行，并更新下一行中的节点。

可能早先您已经找到了到该节点的更好路线（从放置在左侧的节点开始），因此您只有在新创建的路线“更快”时才更新。（因此，您进行了无限初始化，这意味着在开始时您不知道是否确实存在任何路线）。在您完成处理 pyradim 级别之后，您知道您有可能到达放置在水平略低于。

即使听起来有点复杂，它也很容易实现，我希望它不会给你带来麻烦。

Answer 2

如果我对您的理解正确，在您的金字塔中，您始终可以选择向左或向右下降，而到达底部的成本是您通过的所有节点的总和。

在这种情况下，只需从底部向上工作即可。从底部的第二行开始。对于行中的每个节点，查看下面行中的左右子节点。将较便宜的子节点的成本添加到您所在的节点。向上移动一行并重复，直到你到达根/峰。每个节点现在将包含从那里到底部的最便宜路径的成本。只需通过选择成本较低的子节点来贪婪地下降。

Answer 3

您想要的是 Dijkstra 算法，它比 A* 搜索更简单，但我想 DFS 会这样做。我不确定你真正想要什么。