3
$\begingroup$

For example: s = <s1 s2 s3> is my problem,

I make greedy choice s2 and solve s1 and s3 in a greedy way.

In CLRS, it was mentioned regarding "designing greedy algorithms"

Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve

So why is it that we are left with only one subproblem in greedy method after making greedy choice?

Improve this question
$\endgroup$
5
  • $\begingroup$ The point is that the greedy method only works if we can get away with only making a single choice. $\endgroup$
    – Discrete lizard ♦
    Mar 27, 2019 at 9:34
  • $\begingroup$ Thank you, I know you are correct but just for arguments sake, what is we make a single choice greedily and solve the subproblems left and right of the choice independently and greedily? $\endgroup$
    – aj14
    Mar 27, 2019 at 9:45
  • $\begingroup$ @aj14 There is typo in your comment. I assume you meant "what if we make ...". Well, there is no such "what if". In each step of an greedy algorithm, by definition, you make a single choice, reducing/transforming the current problem to another problem that is smaller (dubbed "one subproblem to solve" in that quote from CLRS), which becomes the current problem in the next round. $\endgroup$
    – John L.
    Mar 27, 2019 at 13:09
  • $\begingroup$ @aj14 If you make a choice and then solve the transformed problem by exploring many choices, you will not be designing a greedy algorithm any more. Does this answer your question? $\endgroup$
    – John L.
    Mar 27, 2019 at 14:04
  • 1
    $\begingroup$ @Apass.Jack Thank you. The conclusion is that greedy algorithms have one subproblem by definition and therefore cannot be questioned :) $\endgroup$
    – aj14
    Mar 28, 2019 at 12:54

1 Answer 1

Reset to default
0
$\begingroup$

I think what you are talking about is Divide and Conquer (and Combine) techniques:

Divide the problem into a number of subproblems that are smaller instances of the same problem.

Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.

Combine the solutions to the subproblems into the solution for the original problem.

CLRS 3rd Ed Ch 4, pp. 65

If not D&C, then at least a variant. It seems you are making an greedy choice, then this divides the problem into multiple, and you solve these subproblems the same way. Consider the following problem which I think can be solved as you mentioned:

Given a directed binary tree $T$ (meaning edges are directed from parent to child) with positive integer values on the nodes, determine the directed path with maximal sum of node values.

Here is how we can solve this:

  1. We make a "greedy" choice to include the root node. Since the values are positive, we know that the root node can only increase the sum of node values.
  2. We now can either go left or right (not both since it is directed towards leaves).
  3. Solve the left case, what is it's maximal path? Let's say it's of weight $L$.
  4. Solve the right case, what is it's maximal path? Let's say it's of of weight $R$.
  5. Now we combine these results, if $L > R$ then we prepend the root node to the path returned from the left case, else we prepend the root node to the path returned from the right case.
  6. If we get down to a leaf node, simply return it because it will be it's own maximal path since values are positive.

So this is a kind of "greedy" algorithm in the sense that we make a greedy choice (include the root node always). However, it is much more of a divide and conquer algorithm based on the definition of D&C. This is why greedy must only be left with one subproblem. If we have multiple subproblems then we are either in the case of Divide and Conquer or Dynamic Programming most likely.

Improve this answer
$\endgroup$
4
  • $\begingroup$ That's a good example. Got me thinking... can we say that the recurrence relation of a greedy algorithms is always T(n) = T(n-1) + O(1)... or something similar? $\endgroup$
    – aj14
    Apr 5, 2019 at 18:54
  • $\begingroup$ And if it is anything else like T(n) = 2T(n/2) + O(1), then is gets into D&C or DP? $\endgroup$
    – aj14
    Apr 5, 2019 at 18:55
  • $\begingroup$ The co-efficient of T() on R.H.S. for greedy is always 1, is it possible to recognize problems directly from their recurrences? $\endgroup$
    – aj14
    Apr 5, 2019 at 19:02
  • $\begingroup$ Yes, after making a greedy choice, there should only be one smaller instance of the problem remaining. Also, remember that these recurrences are just functions, the classification really depends on the problem, not so much the recurrence. Although, I do think you could argue the recurrence for any greedy algorithm must have only one recursive call (if any). $\endgroup$
    – ryan
    Apr 5, 2019 at 20:26

Your Answer

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

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