Greedy Algorithm

[jumper007]

I have the following given algorithm.

Algorithm_Greedy(S)
 S1 <- S
 SOL <- (void)
 While (NOT STOP-Condition) Do
   x <- a local, optimal element from S1
   S1 <- S1 - {x}
   If (SOL |_| {x} satisfy conditions) Then   // Where |_| = union.
       SOL <- SOL |_| {x} // Where |_| = union.
   End_If
 End_While
END_Algorithm_Greedy(S)

Can someone explain this to me ? or guide me to an "understandable" tutorial about this ?

Thanks in advance.

[jumper007]

Anyone ? Anything ? please.....

[viliml]

Srry, but I don't even know which programming language that is...

[R0mai]

Can you tell us, where did this algorithm came from? What is it's purpose etc.
It is very hard to say more than what is obvious from the code without any context.

[viliml]

OK, here are my questions which need to bw answered in order for me to provide YOU an answer:
Which language is this? What is the definition of S? Where and how is STOP-Condition defined? what does {x} mean? What does union mean?

[R0mai]

@viliml I can answer those questions :
This is probably just a simple pseudo-code, probably used by his professor.
S is a set.
STOP-Condition probably could be deduced from the context (not provided).
{x} is a set of one element : x.
Union : http://en.wikipedia.org/wiki/Union_(set_theory)

Edit : The algorithm is not complex at all, but without any context it is hard to say what it will do.

[viliml]

OK, so, that algorithm first copies the set S to the set S1, , and makes the set SOL an empty set. Then, while the stop condition isn't set, it takes an element from S1 and puts it in x, and removes x from S1, and then, if the union of SOL and x satisfies conditions, it adds x to the set SOL(which is probalby the SOLution).
The C++ equivalent would be:

template<typename T>
set<T> algorithm_greedy(set<T> S)
{
      set<T> S1=S, SOL;
      while (!STOP_Condition)
      {
             T x=a local, optimal element from S1;
             S1.erase(x);
             SOL.insert(x);
             if (!(SOL satify conditions)) SOL.erase(x);
             }
      return SOL;
      }

[R0mai]

http://www.scribd.com/doc/49531864/115/Problem-6-Minimaler-Spannbaum-Kruskal-Algorithmus page 306. But I don't speak German...

[viliml]

But I don't speak German...

LOL, neither do I, but guess who does... Google translate!!

Google translate wrote:

Basics

Greedy algorithms are characterized in that they choose immerden current best successor. Therefore, they must evaluate before all the avail-able successor known, and they turn to the Gradient. The greedy algorithms work fairly quickly and often find a good solution. This also means that it is not usually the best solution. The manrecht easily recognize when one considers the classical problem for this algorithm, namely the discrete knapsack problem and the traveling salesman problem. the Greedy Algorithm to find a relatively good solution, but the optimal solution can only be found when backtracking algorithm applies unddamit the effort increases significantly. The two problems are NP-complete, the and both the Greedy and the backtracking Algorithm build the solution step-wise up, but only at backtracking it also goes back to a predecessor-ger, and also explains the enormous run-time differences between the two methods. Here is a general form of the Greedy Algorithm: