"Cornell Scientists Tackle 'Hard' Problems by Teaching Computers to Solve Tough Tasks the Human Way"
Cornell News (02/21/05); Steele, Bill
Cornell University Intelligent Information Systems Institute director Carla Gomes and associate computer science professor Bart Selman have developed new methods for solving hard "combinatorial" computer problems, which were detailed on Feb. 21 at the annual meeting of the American Association for the Advancement of Science in Washington, D.C. The combinatorial nature of the problems the tools are designed to address means that the computer must extract from a large set of variables the most effective combination of values to assign to the variables to fulfill specific parameters. The computing strategy in such cases is to try out every possible combination and choose the one with the optimal outcome; the computer begins selecting different blends of value settings, building a continuously growing possibility tree, re-doing the process until all possibilities have been compared or a satisfactory answer is uncovered. However, sometimes the computer can select a tree whose completion takes too long, which often happens when the computer is attempting to calculate "heavy-tailed" phenomena such as chess or economic trends. Among the techniques Gomes and Selman have come up with is one that involves finding a small number of core variables whose values can be set ahead of time. For instance, solving an airline scheduling problem with thousands of variables could be easier if just a dozen of those variables are fixed in advance. Gomes notes that "Humans are very good at seeing the big picture and seeing what's critical." Real-world problems that Gomes thinks could benefit from such strategies include power outage prediction and management.
http://www.news.cornell.edu/releases/Feb05/AAAS.Gomes.heavytails.ws.html
No comments:
Post a Comment