3

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?

4
  • 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. Commented Nov 26, 2014 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. Commented Nov 26, 2014 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. Commented Nov 26, 2014 at 23:06
  • @Deduplicator I wasn't saying it cannot be optimal, but usually it isn't designed with that in mind. Commented Nov 27, 2014 at 2:30

1 Answer 1

2

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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