6
$\begingroup$

I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms.

From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local maxima/minima, we become 'greedy' and declare that as the global maxima/minima.

I suppose that is wrong?

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, Tom van der Zanden, vonbrand, Raphael Jul 26 '15 at 16:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ What have you tried? What self-study have you done? This is explained in many textbooks and online resources. There's little point in us repeating all of that standard explanation here; I worry you might have the same reaction to such a re-explanation. What specifically are you confused about? Have you looked at a specific greedy algorithm? $\endgroup$ – D.W. Jul 24 '15 at 16:59
  • $\begingroup$ SE is unsuited for introductory essays. I recommend you check out a textbook or a similar resource. $\endgroup$ – Raphael Jul 26 '15 at 16:41
  • 1
    $\begingroup$ greedy algorithms are used all over CS but the term might be somewhat slippery to define. think its an acceptable question. however note its covered on wikipedia... $\endgroup$ – vzn Jul 26 '15 at 16:57
0
$\begingroup$

Greedy algorithms are those in which we construct the optimum solution piece by piece.

After identifying a part of the optimum solution (this is intuitive by nature and problem dependent), try to add or subtract elements from it to see whether it still remains optimum.

I guess you should study Matroid Theory and Linear Programming Duality if you are very interested in the mathematics of greedy algorithms.

Try going through these problems on your own and practicing other problems related to these: Maximal Independent Set in a Tree, Disjoint Set (Interval Scheduling), Interval partitioning, 0-1 Knapsack and Fractional Knapsack.

What you are asking is about the Hill Climbing problem specifically. The Wikipedia page provides enough discussion about it, but if you are a newcomer in the world of algorithms I suggest you start out with the above problems first.

$\endgroup$
  • $\begingroup$ "those in which we construct the optimum solution piece by piece" -- that's hardly a characterisation. $\endgroup$ – Raphael Jul 26 '15 at 16:38
  • $\begingroup$ The answer by Arch Wilhes basically states the same thing: "Builds solution step by step/in each step picks out what's best". Even Yuval Filmus states "At every step in time, a greedy algorithm chooses the "best" element, according to some strategy". $\endgroup$ – Sagnik Jul 26 '15 at 19:08
7
$\begingroup$

In simple words, an algorithm is normally considered "greedy" if

  1. it builds solutions step by step without backtracking

  2. in each step it picks what's best in the current state.

To learn more about it, check this pdf out.


enter image description here

The animated gif above illustrates a greedy algorithm for finding the path that adds up to the biggest number.

It does so by choosing the node with the biggest number at each step. (Since the actual solution is the 7-3-99 path, the greedy approach fails to bring forth the correct path.)

This is why greedy algorithm may not always yield the right solution to a certain instance of a problem.

The gif animation was created by Swfung8 on Wikipedia for the article on Greedy Algorithm.

$\endgroup$
5
$\begingroup$

Your understanding is completely wrong: what you describe is known as hill climbing or gradient descent in the continuous case, and local search in the discrete case.

The best way to understand what greedy algorithms are is by an example. Consider the following optimization problem:

Given a set $S$ of positive integers and a number $n$, choose a subset of $S$ of size $n$ with the maximal sum.

For example, if $S = \{3,5,2\}$ and $n = 2$, then the optimal solution is $\{3,5\}$. Here is the greedy algorithm for this problem:

Repeat $n$ times: take the maximal element remaining in $S$.

Continuing our earlier example, the algorithm first takes $5$, and then $3$.

At every step in time, a greedy algorithm chooses the "best" element, according to some strategy. In this case, the best element is the largest one. While in this case the greedy algorithm produces the optimum, in many other cases the result is not optimal but "typically" good, often with provable guarantees. Also, in some cases there might be several reasonable interpretations of "best" to choose among.

If you're interested further in greedy algorithms, I recommend taking up a textbook or consulting online resources.

$\endgroup$
5
$\begingroup$

Greedy algorithms can be used whenever you can think of the solution to the problem being reached in steps. The strategy is then just to choose the next step that looks best in some (usually simple, "local") sense, without ever undoing a step and trying an alternative path.

The classical example is finding a minimal cost spanning tree of a graph. One strategy is to start with just the vertices, and succesively add the cheapest arc that doesn't create a cycle (to get a tree in the end). That this does give a minimal spanning tree is nice. But even if the solution isn't optimal, with a "reasonable" definition of steps and selection of alternative step you should get some solution that isn't too bad.

$\endgroup$
0
$\begingroup$

Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Example: "Coin changing problem".

Brute force approach: Enumerate all possible representations selecting the one with the least number of coins. Using Fibonnaci coins: { 1, 2, 3, 5 } and amount $8.

8 = 5 + 3
8 = 5 + 2 + 1
8 = 5 + 1 + 1 + 1
8 = 3 + 3 + 2
8 = 3 + 3 + 1 + 1
8 = 3 + 2 + 2 + 1 
8 = 3 + 2 + 1 + 1 + 1
8 = 3 + 1 + 1 + 1 + 1 + 1
8 = 2 + 2 + 2 + 2
8 = 2 + 2 + 2 + 1 + 1
8 = 2 + 2 + 1 + 1 + 1 + 1
8 = 2 + 1 + 1 + 1 + 1 + 1 + 1
8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

There are 13 representations overall; 8 = 5 + 3 is optimal.

Greedy algorithm The cashier's algorithm return the largest coin smaller than or equal to the amount and then proceed in analogous fashion for the remaining amount.

Using Fibonnaci coins: { 1, 2, 3, 5 } and amount $8.

The greedy algorithm make the best local choice and then blindly plough ahead. This technique is only applicable if the problem exhibits optimal substructure: an optimal solution contains within it optimal sub-solutions to sub-problems. Not all optimizations problems can be solved with greedy algorithms.

A recursive implementation in SML

(* change : int -> int list *)
func change n =
     if 5 <= n then 5 :: change(n - 5)
else if 3 <= n then 3 :: change(n - 3)
else if 2 <= n then 2 :: change(n - 2)
else if 1 <= n then 1 :: change(n - 1)
else []
$\endgroup$
  • 1
    $\begingroup$ There are other algorithms for solving optimization problems... You might want to edit your first sentence. $\endgroup$ – Yuval Filmus Jul 26 '15 at 12:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.