Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

Re^2: Average Price Algorithm

by camelcom (Sexton)
on Jan 29, 2009 at 07:33 UTC ( [id://739803]=note: print w/replies, xml ) Need Help??


in reply to Re: Average Price Algorithm
in thread Average Price Algorithm

Thanks Limbic, but I'm not sure this approach will find the best solution. I know that, for the given example, there is a selection which gives a maximum error in all buckets of 0.0001754 (3 bucket averages being exactly the average).

Although this approach looks correct, often the best solution will be some blend of fragments which this methodology will not find. I'm thinking some kind of brute-force method may be even better, but still working on options.

Replies are listed 'Best First'.
Re^3: Average Price Algorithm
by MidLifeXis (Monsignor) on Jan 29, 2009 at 11:55 UTC

    (posted here instead of one level up because it seems to expand on the thoughts of the parent)

    ++ to Limbic~Region for the algorithm (grandparent node). I like it.

    It does appear, however, that it is minimizing the error once for each individual fragment, rather than minimizing the error for some summation function (absolute error, statistical deviation, etc) over the entire population.

    As a "good" solution, I think that this is excellent, and it seems to be similar to a "good" solution to the bin packing problem that I remember from my undergrad days. It can be fooled with some nasty data.

    Like any other NP Hard or optimization problem, an approximation's "good enough" value is in the eye of the beholder, and if you are willing to calculate (or wait for) the optimum solution.

    You could add an optimization loop to the end of this algorithm, and bound it with whatever time you are willing to wait (or some other limiting factor), and start swapping values from the bins (picking which ones will give the best change is left as an exercise - perhaps swapping something from the best and the worst, or the two worst, or the worst over and the worst under ), recalculating the fitness, saving the state if better, and repeating if you still have cycles left.

    --MidLifeXis

Re^3: Average Price Algorithm
by Limbic~Region (Chancellor) on Jan 29, 2009 at 14:57 UTC
    camelcom,
    This is a heuristic solution and the problem appears NP hard/complete. That means it is guaranteed not to produce the best solution for all data sets. That is why I said it did amazingly well but didn't say perfect. You indicated you had an acceptable margin of area error and it looked like this could be made to fit your criteria. It is also obviously fast and can be improved.

    Cheers - L~R

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others imbibing at the Monastery: (4)
As of 2024-04-19 03:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found