Keep It Simple, Stupid PerlMonks

### Re^4: Evolving a faster filter? (optimal?)

by tye (Sage)
 on Jan 04, 2013 at 21:32 UTC ( #1011722=note: print w/replies, xml ) Need Help??

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

That's not enough to prove it. You certainly get a solution that can't be improved by a single swapping of adjacent filters. And if your sort order using that algorithm is well-defined, then you will get an optimal solution. That is, if you never get the \$a < \$b < \$c < \$a case. Update: No, maybe not even that (unless someone can convince me that "of adjacent filters" is not needed above). Update: Ah, ruling out adjacent swaps also rules out any swaps. Update: Silly me. Ruling out swapping of elements that start out adjacent doesn't rule out swapping of elements that didn't start out adjacent (but became adjacent from swapping elements that did start out adjacent).

I thought I had already found a case where it wasn't optimal. But the total cost was reported as identical as the first cost despite a different ordering being chosen. So it might be hard to find a case where it isn't optimal.

I bet it makes doing anything more than that not worth the effort for Ovid's usage, at least. :)

- tye

Replies are listed 'Best First'.
Re^5: Evolving a faster filter? (optimal!)
by LanX (Bishop) on Jan 04, 2013 at 21:42 UTC
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.

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

Create A New User
Node Status?
node history
Node Type: note [id://1011722]
help
Chatterbox?
 [atcroft]: Is there an example somewhere of a way to order nodes when using Tree::DAG_Node?

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (3)
As of 2018-04-21 00:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (81 votes). Check out past polls.

Notices?