选择贪婪算法找到最低成本路径

Question

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

Answer 1

如果我正确地理解了你，在你的金字塔中，你总是可以选择向左或向右下降，到底的成本就是你通过的所有节点的总和。

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

Answer 2

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

Answer 3

如果您没有使用贪婪算法的必要性，这里不正确。 对于这种问题，你自然会使用一种叫做“动态编程”的技术。

你初始化你的金字塔的所有方块（你做一个备份）与无限 - 除了它自己的价值初始点。

然后你从上到下逐行处理金字塔。 您尝试从第一行开始（只有一行是顶部），并且您更新第二行的节点，并为它们赋予top +它们的值。然后移动到第二行，并更新下一行中的节点。

您可能以前找到了一个更好的路由到该节点（从节点放置一个位置开始），因此只有在新创建的路由“更快”时才会更新。 （因此你做了无限初始化，这意味着在开始时你不知道是否有实际存在的路线）。当你完成pyradim的处理后，你知道你有最好的路线来放置在级别在下面。

即使它听起来有点复杂，它很容易实现，我希望它不会让你成为一个问题。