Thoughts on the Greedy Theorem
On the train back to Changhua, I thought about why the greedy theorem requires S to be monotonic on Rº instead of R. Read naïvely, "S . FR ⊆ R . S" (which is not the monotonicity condition of greedy theorem) says that if we decrease (improve) the input to S, the result would be smaller (better) than what we get from feeding the original input to S. To compare, the real monotonicity condition "S . FRº ⊆ Rº . S" says if we increase (\sth -> make sth worse) the input to S, the result would be larger (worse) than what we get from feeding the original input to S. The two statement seems to be the same, both suggesting that we always choose the least result during folding, while the first one looks more intuitive.
But it's an imprecise interpretation. What the two monotonicity conditions tell us is when we decrease/increase the input to S, the result would be smaller/larger than one of the possible results we get from feeding the original input to S. This makes a difference. Say we have a smaller input i and a larger input j, and ΛS i = {a, b}, ΛS j = {c, d}. Given S is monotonic on R, we can only guarantee that any of a and b is better (smaller) than one of c and d but not necessarily both, and it is therefore possible that the optimum result is one of c and d. On the other hand, if we have that S is monotonic on Rº, choosing c or d as the final result would be unwise, since one of a and b is going to be better.
A remaining question is: isn't it possible that we need some suboptimum steps in order to reach the final optimum result? The key is that we are using folds as the generating structure. Very informally, the folding process may be interrupted at any time, so we must give the optimum result after every folding step. More formally, it may be possible to exploit the min/max principle to prove that after every step the optimum result must be produced. But we do not need another formal proof since the greedy theorem is already proved, so the informal explanation is quite enough.
However, why is the naïve interpretation wrong? The problem is that S may generate more than one possible results. This immediately suggests that if S is a function, we may be able to prove that the first monotonicity condition is equivalent to the second one, which is indeed a fact that can be easily proven by shunting and already pointed out in AoP.
--
Well, it is beyond my English writing ability to express such a complicated discussion...
Labels: Program Derivation
Shouldn't the monotonicity condition be S . FRº ⊆ Rº . S? :)
You are right that non-determinism in S is the reason why the two notions of non-determinism are different. On the other hand, in optimisation problems S is usually non-deterministic, so we have multiple choices in each step.
> A remaining question is: isn't it possible that we need some suboptimum steps in order to reach the final optimum result?
It is possible! And these kind of algorithms are not covered by the current greedy theorem. Sharon Curtis talked in her thesis about "best local" v.s. "best global", addressing some generalisations to cover more algorithms. The more generalised you go, however, the more complicated the theorems would become.
> Shouldn't the monotonicity condition be S . FRº ⊆ Rº . S? :)
Oops, corrected. :P
> Sharon Curtis talked in her thesis about "best local" v.s. "best global", addressing some generalisations to cover more algorithms.
Wow, I'll read that after I am familiar with AoP to some extent. (Maybe a few months later...)
<< 回到主頁