12/04/2009

12-04-09 - Bike Optimization

I mentioned before about how saving money on cheap inner tubes is dumb. So there's this amusing site Weight Weenies with lists of lots of bike components and weight.

As soon as I saw it I immediately thought "MMO". It's just like the list of gear for kitting out your character. Should I get the ring of +1 str or the bracers of +5 HP ?

It's funny to me that people seem to love doing that sort of optimization in games, but not in real life. People love MMO's with lots of gear, they love to sit and think about the best way to kit out their character and how to maximize his stats and all that. It's a very detailed cost/benefit analysis, and lots of people do it. But those same people either suck at it miserably in real life, or even just refuse to do it, saying something like "I don't want to live that way" ( "that way" being rationally and logically ). So you don't want to think about maximizing benefit/cost in real life, but you enjoy it so much that you choose to spend your leisure time doing that activity, hmm. Maybe if you would think about benefit/cost in real life a bit you would decide not to spend your time playing an MMO. Anyhoo...

Weight Weenies obviously presents the idea of computing the weight of each part of a bike and its cost and finding the optimal weight reduction strategy for a given budget.

A lot of people would approach this with the "greedy strategy". That is, first find the one item that has the very best (benefit/cost) slope and buy that upgrade. Repeat until you are out of money.

This is obviously wrong for various reasons. For one thing, the upgrades are not additive, an upgrade to the same "slot" (eg. the "ring" in an MMO character, or the "seat post" on a bike) replaces the previous item in that slot. That means you only ever want to buy one item for each slot, and the greedy algorithm does not guarantee that you buy the best item for a given slot. The greedy algorithm also doesn't deal with using the finite budget well, it could leave you with left over money that isn't used well.

The obvious solution is a kind of dynamic programming like the LZSS optimal parse. Consider all prices to be in integer dollars. You have a budget of N dollars, think of that as the "X" axis on the time line. You are trying to walk from X=0 ($0 spent) to X=N (full budget spent) and get the maximum step on the Y axis (benefit).

So you can make this a graph. At (X=0,Y=0) you have the initial node with all M upgrade paths coming out of it; each path has an X length equal to its cost and Y length equal to its benefit. After you take a path, all upgrades on the same slot are excluded, so the next node has a reduced set of paths. Note that the graph does *not* branch exponentially, because the nodes come back together. That is, an upgrade like {ring,bracer} is the same as {bracer,ring} so they go to the same node. If you had infinite budget, the paths would wind up all ending in points with no exit paths (there would be many of them, equal to the number of possible ways to do a full-slot kit-out).

You can phrase this another way to make the dynamic programming aspect obvious. (dynamic program just means caching shared bits of a computation). If you have D dollars remaining and you have the set S of upgrade slots unused, the item you choose next is I(D,S). I(0,S) is null. I(1,S) is the best item in the set S that you can get for 1 dollar. Then :


I(D,S) = arg_max(i) {  Benefit(i) + Benefit( I( D - cost(i) , S - type(i) ) ) }

i = an item with type(i) in the set S and cost(i) <= D

arg_max = return the iterator which maximizes the enclosed expression

One way to solve it is the LZSS way which avoids any recursion : you start at the "end" of your spending, when budget remaining is zero, and you walk backwards doing the above computation for each D, until you reach D = N (your initial budget), and then I(N,all) is the first item you should buy (and you follow the paths back forward to get the full list of items to buy).

The other way involves heavy recursion. You just ask for I(N,all) , which will call I() on lots of sub choices, which calls I() some more until you have your answer.

I think that's optimal;

1 comment:

Autodidactic Asphyxiation said...

It us amusing (but not altogether surprising or inappropriate) that you think of dynamic programming problems in terms of LZSS.

In general:

http://en.wikipedia.org/wiki/Knapsack_problem

old rants