选择贪心算法寻找最低代价路径

Question

我有一个数字金字塔。每个数字表示关联的点数。我需要使用贪婪算法来找到从金字塔顶部到底部的成本最低的路径。我读过关于无信息搜索算法和有信息搜索算法的文章，但我仍然不知道该选择什么。对于这种类型的问题，您认为最合适的是什么？贪婪的最佳优先搜索/ A*搜索还是其他？这是一个如此简单的问题，但我并不是用所有这些算法来知道什么是最佳选择。就像我说的，它必须是一个贪婪的算法。

Answer 1

如果我没理解错的话，在你的金字塔中，你总是可以选择向左或向右下降，而到达底部的成本是你通过的所有节点的总和。

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

Answer 2

如果你不一定要使用贪婪算法，这在这里是不正确的。对于这类问题，您自然会使用一种称为“动态编程”的技术。

你用无穷大初始化你的金字塔的所有方块(你做了一个备份)-除了初始点，它有自己的值。

你从上到下逐行处理金字塔。您尝试从第一行开始尽可能地访问(因此，唯一的一个是top)，然后更新第二行的节点，为它们提供top的值+它们的值。然后移动到第二行，并更新下一行中的节点。

有可能之前你已经找到了到那个节点的更好的路线(从放在左边的节点开始)，所以你只有在新创建的路线“更快”的情况下才更新。(因此，您进行了无限初始化，这意味着在请求时，您不知道是否确实存在任何路由) .After您完成了对某一级别的pyradim的处理，这样您就知道您有可能到达位于该级别下的节点的最佳路由。

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

Answer 3

你需要的是Dijkstra算法，它比A*搜索更简单，但我猜DFS会做到这一点。我不知道你到底想要什么。