combinatorial problems
many, many years ago, i spent a good deal of my life trying to solve some really brutal combinatorial problems with every widget i could find in the geek arsenal – i hacked on trees and heuristics and neural networks and genetic algorithms and all kinds of strange combinations thereof to coax optimizations out of personal computers.
this was an affort to improve on human optimization of really large combinatorial problems, and do it interactively, so the “human intuition” could augment “brute force” (and vice-versa) to push the solution closer to a true optimization rather than letting it get stuck in a “local optimization.”
during this time, i ran into the amd 286zx and 286lx processors (i think that’s right), which were essentially systems-on-a-chip. these are now so ancient that they don’t even show up on amd’s site anymore. anyway i had some crazy idea about packing a whole stack of these little 10mhz parts into a desktop-sized box with a 386 playing arbiter and doing user-interface duty. i figured that asymetric multiprocessing would be an interesting approach to the problem, where some small piece of the problem was assigned to one of the “slave cpu’s” which would be allowed to grind away on it until the “master cpu” (perhaps prompted by the user) decided that it was spinning its wheels, killed it and gave it a new subproblem to chew on for a while. i figured i’d start with the 286zx’s since they were available, but could slip in any sort of optimized slave processor as it came along (say, chunk of silicon design specifically to run neural network simulations or whatever). it was fun to think about.
ultimately, though, i ran out of money and ideas and patience and never quite got to a functional solution (and couldn’t afford to build custom hardware).
i bring this up now, because it sounded errily familiar when i stumbled into this news release from cornell.
Mostly their approach is to have the computer do what a human being might do: stop, go back and start over and try something different.
these people are definitely smarter than i am, but it’s neat to see it crop up again.
one tip for the cornell team: it’s possible to get some really, really neat visualizations out of these problems, and if you tweak them a bit you can get some wicked user-interaction experiences.
i bet current graphics processors would be really good at this stuff – both the visualization and the actual problem-solving. a lot better than the 286zx’s, anyway…