选择贪心算法寻找成本最低的路径
我有一个数字金字塔。每个数字代表关联的点数。我需要使用贪心算法来找到从金字塔顶部到底部成本最低的路径。我读过有关无知和不知情的内容。知情的搜索算法，但我仍然不知道该选择什么。您认为什么最适合解决此类问题？贪婪的最佳优先搜索/A* 搜索还是其他？这是一个非常简单的问题，但我并没有使用所有这些算法来知道什么是最好的选择。正如我所说，它必须是一个贪婪算法。
I have a pyramid of numbers. Each number represents the number of points associated. I need to use a greedy algorithm to find the path with the lowest cost to get from the top of the pyramid to the bottom. I've read about uninformed & informed search algorithms, but still I don't know what to choose. What do you thing is best suited for this type of problem? Greedy best-first search / A* search or other? It's such a simple issue, but I'm not used with all these algorithms to know what's the best option. And as I said, it has to be a greedy algorithm.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果我理解正确的话，在你的金字塔中，你总是可以选择向左或向右下降，到达底部的成本是你经过的所有节点的总和。
在这种情况下，只需从底部向上操作即可。从底部第二行开始。对于该行中的每个节点，查看下面行中其左子节点和右子节点。将更便宜的子节点的成本添加到您所在的节点上。向上移动一行并重复，直到到达根部/峰部。现在，每个节点将包含从该节点到底部的最便宜路径的成本。只需选择成本更便宜的子节点即可贪婪地下降。
If I am understanding you correctly, in your pyramid you always have the option of descending to the left or to the right, and the cost of getting to the bottom is the sum of all the nodes you pass through.
In this case, simply work your way up from the bottom. Start at the 2nd row from the bottom. For each node in the row, look at its left and right children in the row below. Add the cost of the cheaper child node to the node you are on. Move up a row and repeat, until you are at the root/peak. Each node will now contain the cost of the cheapest path from there to the bottom. Just greedily descend by choosing the child node with the cheaper cost.
如果您没有必要使用贪婪算法，那么这里是不正确的。
对于这种问题，你自然会使用一种称为“动态编程”的技术。
您将金字塔的所有方块（您进行备份）初始化为无穷大 - 除了具有其自身值的初始点。
然后您从上到下逐行处理金字塔。
您尝试从第一行开始（因此唯一的一个是顶部），然后更新第二行的节点，为它们提供顶部的值+它们的值。然后移动到第二行，并更新下一行中的节点。
您可能之前已经找到了到该节点的更好路线（从左侧放置一个位置的节点开始），因此您仅在新创建的路线“更快”时进行更新。 （因此，您进行了无限初始化，这意味着一开始您不知道是否实际存在任何路线）。在完成金字塔级别的处理后，您就知道您有到达放置在水平就在下面。
尽管听起来有点复杂，但实现起来很容易，我希望它不会给您带来麻烦。
If you don't have a must of using greedy algorithm which isn't correct here.
For this kind of problem you naturally use a technique called "dynamic programming".
You initialize all squares of your pyramid (you make a backup) with infinity - except the initial point which has value of its own.
And you proccess pyramid from top to bottom, row by row.
You try to go wherever you can from the first row (so the only one is top) and you update nodes at the second row, giving them the value of the top + their value. And then you move to second row, and update nodes in the next row.
It is possible that earlier you've found a better route to that node (leading from the node placed one place left) so you only update if the newly created route is "faster". (You made therefore an infinity initialization, meaning that at the beggining you don't know if any route actually exists) .After you finish processing a level of pyradim that way you know that you have best possible routes to nodes that are placed in the level just below.
Even if it sounds a bit complicated it's quite easy to implement, i hope it won't make you a problem.
你想要的是 Dijkstra 算法，它比 A* 搜索更简单，但我想 DFS 可以做到这一点。我不确定你真正想要什么。
What you want is the Dijkstra-Algorithm it is simpler then A* search but I guess a DFS would do that to. I'm not sure what you really want.