|
|
Posted by Moot on 11/01/06 13:19
Jerry Stuckle wrote:
> I thought about it some more. And really, your problem isn't much
> different than the historic traveling salesman (a salesman has to visit
> X cities - what's the shortest distance he has to travel to visit all
> cities). It's a great puzzle - and one which has never been solved
> except by brute force, AFAIK.
>
> And I think that's what you're going to have to do here, unfortunately.
>
If you want to get the *best* possible packaging solution, then like
you say, there's just no way around it...you're going to have to expand
the entire search tree. But, if you could be satisfied with the best
solution chosen from a subset of all solutions, then a
heuristic-directed A* search could be a good candidate.
Without delving deeper into the problem, a good starting heurstic would
simply be the amount of empty space left in the package. Keep
expanding the tree and following the branch dictated by the heuristic
until you get to a point where you can fit no more packages, and
declare that a possible solution. Backtrack out of the solution (how
far to back out will depend upon how similar you want your solution
subset to be...further = a more diverse set). Repeat X times to get
however many possible solutions you want to have, then choose the best
one as your actual packaging setup.
As I said, if you don't need the actual best solution, but only a
*good* solution, then this approach would save you processing time and
memory because you don't have to examine all possible options, just the
most promising ones.
Navigation:
[Reply to this message]
|