Ask HN: Solved this problem with stochastic beam search. Any alternatives?
3 comments
[Update] This can be seen as one variation of the knapsack problem.
http://en.wikipedia.org/wiki/List_of_knapsack_problems
http://en.wikipedia.org/wiki/List_of_knapsack_problems
Since the count of items is known a priori (=sizeof(S)), doesn't that mean that the mean and the sum are related in a well defined way? Basically then both critera can be simplified to a single criterion on either sum or mean.
Thanks for your response, skip! SUM is the sum of attributes A, but MEAN is the mean of attributes B, so I don't see how they can be simplified.
Oh, I missed this detail. In that case for a deterministic result I think you need to look at every possible combination. However, you can order them by the minimum criterion first, and start searching from the smallest to largest, so then the first group than meets the interval criteria is guaranteed optimal.
Givens:
There are N types of item.
For each item type, M instances exist.
Each item instance has two integer attributes, A and B.
There is some subset S of item types (i.e. a set of up to N distinct item types)
Goal: For a given set S, choose the optimal set R of item instances corresponding to the set (i.e. one item instance in R for each item type in S).
Let SUM be the sum of all the values of A in R. Let MEAN be the mean of all the values of B in R.
The optimal set is one that meets one of the two following conditions (depending on which one we are looking for at the give moment)
My approach: Two-part stochastic beam search. In the first part, the objective function is based on the distance from the center of the constraint space (i.e. the space where SUM or MEAN is within the acceptable range). This goes until we have k states within the constraint space. In the second part, the objective function is defined by the qualification for an "optimal set" defined in the paragraph above. At each step, only successor states within the constraint space are considered. Iteration continues until MAX_STEPS is exceeded.
What other approaches would you consider for solving this problem? One issue I have with the current approach is that, while it does generate results that satisfy the conditions, the results are not optimal, in the sense that I can run the algorithms several times and get different answers.