Choosing greedy algorithm to find lowest cost path

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.