Week 5 Discussion Forum

Greedy Algorithms

Greedy Algorithms

by MD.TORIKUL ISLAM ( 192-15-2852 ) EMON -
Number of replies: 2

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solutions is the best fit for Greedy.

For example consider the Fractional Knapsack Problem. The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to a globally optimal solution because we allowed taking fractions of an item.

 


84 words

In reply to MD.TORIKUL ISLAM ( 192-15-2852 ) EMON

Re: Greedy Algorithms

by Alif Pranto -
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

55 words

In reply to MD.TORIKUL ISLAM ( 192-15-2852 ) EMON

Re: Greedy Algorithms

by MD. IFTEKHARUL ISLAM RIDOY -
Many optimization problems can be solved using a greedy approach. The basic principle is that local optimal decisions may be used to build an optimal solution. But the Greedy approach may not always lead to an optimal solution overall for the problems. The key is knowing which problems will work with this approach and which will not.
A greedy algorithm always makes the choice that looks the best at the moment .
My everyday examples are :
  • Driving from Dhanmondi to Ashulia campus.
  • Playing card.
  • Invest on stocks.
Overall , Greedy algorithm are simple and straightforward.

93 words