2
$\begingroup$

Recall the rod cutting problem.

Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces. You may assume no cutting cost.

The following is a question from CLRS 15.1-2.

Show, by means of a counterexample, that the following ‘greedy’ strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p_i/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

Consider prices up to length $4$ are $p_1=1, p_2=5, p_3= 8, p_4 = 9$ respectively. So, densities are $d_1=1, d_2 = 2.5, d_3= 2.67, d_4 = 2.25$ respectively.

If we are given a rod of length $4,$ then an optimal way of cutting the rod to maximize revenue is $2$ pieces of length $2$ each, generating $5+5 = 10.$

However, greedy algorithm above will suggest cutting the rod into 2 pieces of length $3$ and $1$, generating revenue $8+1=9.$

I obtain this example by merely following the same prices given in CLRS but do not understand why such greedy algorithm fails to provide optimal way of cutting the rod.

Improve this question
$\endgroup$
1
  • $\begingroup$ In this case: Rods of length 3, 2 and 4 give the best revenue, length 1 much less so. But by cutting a rod of length 3, you are forced to take another rod of length 1 with much less good revenue. By making one choice that looks good, you are forced to make another choice later on that isn't good at all. $\endgroup$
    – gnasher729
    Jul 7, 2022 at 13:49

3 Answers 3

Reset to default
4
$\begingroup$

Because a local maximum is not always a global maximum.

The length 3 rod is the most price-for-length effective single rod piece. But the optimization goal isn't to find the best price-to-length ratio for a single piece, it's to find the best total price for how much rod we actually have! Once the greedy algorithm chooses the shiniest, most appealing first piece, it is now stuck for the rest of the problem with a highly suboptimal remaining length according to the highly nonlinear price table.

In general, most optimization problems cannot be solved optimally by a greedy strategy. Those that can tend to have some exceptional property that guarantees that a local maximum will also be a global maximum.

Improve this answer
$\endgroup$
3
$\begingroup$

Greedy algorithm doesn't always generate optimal solution. To get optimal solution with it, the problem needs to have some good property such as optimal substructure or matroid. The optimal substructure means optimal solution can be constructed from the optimal solutions of divided problems. Matroid theory shows another good property to characterize where greedy algorithm works: Edmonds–Rado Theorem claims that (best-in) greedy algorithm works with any weight function if and only if the independence system is matroid. Here, independence system is a kind of formalization used to many combinatorial optimization problems. I don't explain the details, but wanted to explain greedy algorithm works for problems with good properties, that the rod cutting problem doesn't hold.

Improve this answer
$\endgroup$
0
$\begingroup$

Actually, there is a simple optimal greedy strategy with these prices: "Don't cut if n ≤ 3. Cut a piece of length 2 if n = 4 and cut a piece of length 3 otherwise, then cut the rest according to this strategy".

Here's two interesting problems:

  1. Given 4 prices, find out if the originally proposed greedy algorithm is optimal.

  2. Given 4 prices, find a simple optimal greedy algorithm.

Improve this answer
$\endgroup$

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.