Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re^5: Evolving a faster filter? (optimal!)

by LanX (Canon)
on Jan 04, 2013 at 21:42 UTC ( #1011723=note: print w/ replies, xml ) Need Help??


in reply to Re^4: Evolving a faster filter? (optimal?)
in thread Evolving a faster filter?

Well my argument is sufficient to show that a solution where two adjacent filters don't follow this order can't be optimal, because otherwise swapping those adjacent filters f[i] and f[i+1] would improve the result.

So any optimal solution must follow this strict order criteria.

qed! =)

Cheers Rolf

PS: I'm glad I didn't start implementing the B&B algorithm :-)

UPDATE:

) and it's easy to see that all ordered solutions (plural b/c adjacent filters can have the same weight) imply the same total cost.


Comment on Re^5: Evolving a faster filter? (optimal!)
Select or Download Code
Replies are listed 'Best First'.
Re^6: Evolving a faster filter? (optimal!)
by tye (Cardinal) on Jan 04, 2013 at 22:35 UTC

    Indeed!

    And the number of choices that leaves you with is rather tiny.

    Worse (or better), from throwing cases at the code, I bet it is possible to prove that all such orderings are optimal so that the one that sort gives you is optimal.

    I think it might not be hard to prove and $a <= $b <= $c implies $a <= $c (assuming non-negative cost and selectivity between 0 and 1). And that should be enough.

    - tye        

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1011723]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (6)
As of 2015-08-01 02:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (285 votes), past polls