What is a greedy algorithm? How to use it?

[Zont]

Hello comunity.

I'm somwhat new in computer science and maths algorithm, in a problem in which i am working i have been told that using greedy would be shorter and that it should work well.
But i don't know specifically what or how i should use a greedy algorithm.
I'm working in an ACM-ICPC 2013 problem, to be more specific the problem I-Inverting Huffman. https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544

[fiveworlds]

A greedy algorithm is an algorithm that sacrifices accuracy for speed an example of which would be bubble sort 99% of the time it sorts correctly 1% of the time it doesn't.

 

The google hashcode competition featured a karnaugh map generation problem for a couple of million zeros and ones and asked people to find the optimal solution. It would be too slow to test every value so participants needed to work out a sub-optimal solution.

Edited April 12, 2017 by fiveworlds

[pzkpfw]

fiveworlds, can you give an example where a properly written bubble sort doesn't sort correctly?

[fiveworlds]

fiveworlds, can you give an example where a properly written bubble sort doesn't sort correctly?

 

 

 

It does sort correctly an example of where bubble sort is greedy is when you include the swap heuristic.

for(int x=0; x<n; x++)
{
for(int y=0; y<n-1; y++)
{
if(array[y]>array[y+1])
{
int temp = array[y+1];
array[y+1] = array[y];
array[y] = temp;
}
}
}

greedy

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
    boolean changed = false;
    do {
        changed = false;
        for (int a = 0; a < comparable.length - 1; a++) {
            if (comparable[a].compareTo(comparable[a + 1]) > 0) {
                E tmp = comparable[a];
                comparable[a] = comparable[a + 1];
                comparable[a + 1] = tmp;
                changed = true;
            }
        }
    } while (changed);
}

not all greedy algorithms sacrifice accuracy. However if bubble sort uses the max amount of swaps then the greedy version is slower.

Edited April 12, 2017 by fiveworlds

[John Cuthber]

That doesn't make a lot of sense. You say.

"A greedy algorithm is an algorithm that sacrifices accuracy"

and

"not all greedy algorithms sacrifice accuracy"

 

which one is right?

Also,. bubble sorts are not (generally) fast.

Edited April 12, 2017 by John Cuthber

[pzkpfw]

It does sort correctly ...

So what did you mean by:

 

... an example of which would be bubble sort 99% of the time it sorts correctly 1% of the time it doesn't. ...

[pzkpfw]

Hello comunity.

 

I'm somwhat new in computer science and maths algorithm, in a problem in which i am working i have been told that using greedy would be shorter and that it should work well.

But i don't know specifically what or how i should use a greedy algorithm.

I'm working in an ACM-ICPC 2013 problem, to be more specific the problem I-Inverting Huffman. https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=615&page=show_problem&problem=4544

A little more time, so ...

 

A greedy algorithm is one that at each step chooses the immediately (local) "best" looking choice, with the hope that overall it leads to something close to the best overall (global) solution.

 

https://en.wikipedia.org/wiki/Greedy_algorithm

 

They can work well, but are not guaranteed to always give the best solution. Take a simplified knapsack problem; you have a knapsack that can hold N kg of rocks and some rocks of equal value per kg, but of different sizes. You want as much of the rocks in the sack as possible, i.e. as little space un-filled as possible. A simple greedy algorithm is to always pick the smallest rock to put in the sack, to leave as much space as possible for more rocks. That may work well in many cases, especially where there are lots of small rocks, but can go wrong.

 

Say you can fit 10 kg in the sack, and have 10 x 1 kg rocks, and 1 x 5 kg rock. The simple greedy algorithm would put all 10 of the 1 kg rocks in the sack - no space wasted. Perfect. (Actually equal to the 5 kg rock plus 5 of the 1 kg rocks).

 

If there were 9 x 1 kg rocks, and 1 x 5 kg rock; the greedy algorithm would put 9 x 1 kg rocks in the sack and have 1 kg space left over as the 5 kg rock can't fit. That's not as good as sticking the 5 kg rock in first, followed by 5 of the 1 kg rocks - but still not a bad result.

 

If there were 1 x 1 kg rock and 2 x 5 kg rocks, then you get 6 kg of rocks in the sack, with 4 kg of space wasted, a much worse result than if the two 5 kg rocks went in.

 

https://en.wikipedia.org/wiki/Knapsack_problem

 

I thought the usual huffman coding method was greedy, but anyway, this article covers it:

 

http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

 

(Seems a bit detailed for homework help, but it's there on the internet anyway. Also, note that some of the comments on that item miss the point.)

Edited April 12, 2017 by pzkpfw