2

As a preface I will state this is for a homework assignment. I have already discussed this with the professor and will not be using this design. This purpose of this question is whether or not the defined algorithm is greedy. Also if this is in the wrong section I apologize and please let me know where it should be asked.

I would like to know if the following algorithm would be considered as a greedy algorithm. There are two stages for the algorithm but I am interested in the algorithm as a whole.

First stage: Run a series of pre-defined greedy algorithms. Each algorithm would come up with a solution for the overall problem. For example, given the scheduling problem, if I had the following alogorithms:

  1. Pick the longest request of all choices.
  2. Pick the shortest request of all choices.
  3. Pick the latest ending request of all choices.

Second stage: I would now have three "solutions" to choose from. I now pick the "best" solution from some criteria, say maximum number of requests scheduled.

Is this two stage algorithm considered to be a greedy algorithm since all of the parts themselves are greedy?

  • 1
    For the second stage, what would separate a greedy choice from an optimal choice? Usually greedy algorithms don't pick the "best" choice, they pick the choice that brings the most gain in the present state. – afuzzyllama Nov 26 '14 at 22:57
  • @afuzzyllama: Greedy algorithms can be optimal. And yes, I still consider it greedy, even though it combines other greedy algorithms by picking the best result found. – Deduplicator Nov 26 '14 at 23:05
  • @afuzzyllama The way that I see this is that the second stage would pick the option according to its design. In the example above I mentioned maximum number of requests, so the second stage would pick from the three options which ever one scheduled the most number of requests. In this design the second stage would only have one iteration of choices to make. – John Thomas Nov 26 '14 at 23:06
  • @Deduplicator I wasn't saying it cannot be optimal, but usually it isn't designed with that in mind. – afuzzyllama Nov 27 '14 at 2:30
1

Let's first define a greedy algorithm - I'll take it from Wikipedia because it is a reasonable one.

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

For your considered solution, it isn't a greedy algorithm because there really isn't a question of multiple stages and making choices in the hopes of finding a global optimum at all. I'd be more likely to call it an amalgamated method or, more idiomatically, a Goldilocks method - try all the options and choose the one you like the most. This more closely resembles a brute-force method, or a best-of-three method (such as with some optimizations of quicksort in the problem of picking a good median), than it resembles a traditional greedy algorithm.

The main problem, beyond the technical definitions, is the reason for considering the term "greedy" itself: how does an attempt to solve a problem deal with the fact that sometimes what seems like the best idea at the time can in fact not bring about the ideal outcome? If it generally ignores this problem and just does what makes the most sense one step at a time, the solution is generally considered a greedy one; if it attempts to consider the impact of local optima in some way, it isn't (even if it produces terrible results!); if it considers all possible solutions, it's brute-force...etc.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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