0
$\begingroup$

I have the following problem. I have constructed an algorithm for evaluating some expression, e.g., $L := a_1 \& a_2 \& \ldots \& a_n$ Now the overall costs for some plan P, evaluating L is:

$cost(P) = \sum_{\forall e_i \in L} C(op(e_i))$

Now if I choose the cheapest operator (op) to evaluate $e_i$, then the algorithm should be optimal, and $cost(P)$ should be the lowest possible, or how do you call such cost, optimal? There are more than one operator that can evaluate $e_i$, each operator is associated with some cost, and cost function $C(op)$ returns such cost.

How can I prove it that my algorithm is optimal? This is where I'm having problems, I don't have much experience with formal proofs.

thanks a lot in advance, I got stuck here :(

$\endgroup$

1 Answer 1

0
$\begingroup$

You could, perhaps, show that among all algorithms represented by your approach (i.e., all choices of each op $e_i$), one is the cheapest. But what if I come up with a completely different algorithm that does not use the same $n$ operations, but uses $n/2$ of them instead? Then your proof will not apply to my algorithm, which could be far more efficient.

In short: your approach seems (without further information) doomed to fail.

$\endgroup$
5
  • $\begingroup$ Each $e_i$ has to be evaluated. I just want to show that if I pick the cheapest operator evaluated each $e_i$, then the overall cost should be the lowest possible, and my algorithm is optimal? $\endgroup$
    – Trex
    Commented Sep 10, 2014 at 13:30
  • $\begingroup$ If you can be sure that the costs of the $e_i$ are independent, then yes. But suppose you had to evaluate $x^6 + x^7$. You might find a cheap way to evaluate $x^6$, and a cheap way to evaluate $x^7$, without noticing that you could just take your value for $x^6$, which you've already computed, and multiply by $x$...so those costs would not be independent. Are you certain that your costs are truly independent? (Usually such independence is very hard to prove!) $\endgroup$ Commented Sep 10, 2014 at 13:41
  • $\begingroup$ Yes they are independent, each $e_i$ is different. This assumption can be taken, no problem. $\endgroup$
    – Trex
    Commented Sep 10, 2014 at 13:47
  • $\begingroup$ So John, how I would write a proof, such that the cost(P) is minimal, and that the alg. is optimal? $\endgroup$
    – Trex
    Commented Sep 10, 2014 at 13:59
  • $\begingroup$ Let me get this right: at the core, you need to show that if you have $n$ nonempty sets of positive real numbers $A_i$ ($i = 1, \ldots, n$), and you pick a number $f_i$ from $A_i$ for each $i$, then the sum of the $f_i$ is minimized when you pick $f_i = e_i = \min_{a \in A_i} a$. Well, I'd compare $\sum f_i$ to $\sum e_i$ term by term, and show that the latter was smaller than the former; that proves that among all choices, the lowest-cost one consists of the $e_i$s. $\endgroup$ Commented Sep 10, 2014 at 16:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .