Search code examples
algorithmgraphpathgreedy

Choosing greedy algorithm to find lowest cost path


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.


Solution

  • 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.