Project FINDING BETTER SHORTCUTS

The human mind has this remarkable knack of often being able to solve puzzles "just by looking at them," notes Michael. He and practically every computer scientist would love to discover how we do that, so they could emulate our thinking processes in computers. Meanwhile, they've got their hands full trying to find ways to tackle certain problems that absolutely defy solutions with today's technology.

forbes project
Michael Forbes demonstrates a new solution to the traveling salesman problem
The most notorious example is the Traveling Salesman Problem, or TSP. Its goal is easy to state: Find the shortest, most cost-efficient path among X number of cities or stores or whatever. "It seems simple, but there's a devious amount of complexity hidden behind it," says Michael.

For 10 stopovers, it's a no-brainer — just 1,024 possibilities. But for 100 cities, the alternatives explode to 1,267,000,000,000,000,000,000,000,000,000. And for 1,000 stops, the zeros outnumber the visible stars — and finding the one best route, using every computer in the world, would take centuries. Obviously, no one bothers to try.

However, businesses do hunt constantly for new shortcuts that can quickly get closer to the optimum path. Better almost-optimum answers can be worth tons of money to electronics, telecommunications, and transportation companies. One simple example: The back of a printed-circuit board needs to be spot-welded by a robot at 149 points; what's the fastest sequence?

Michael devised algorithms for an imaginary supermarket chain. It has one milk truck that can hold 2,000 cartons of milk. Suppose that today, the truck needs to deliver 12,000 cartons to the chain's four stores, picking up the milk from dairy farms scattered around the area, which have a total supply of 25,000 cartons. Considering all the variations, including distances, number of cartons at each farm, and the demand at each store, what's the most efficient schedule for getting the milk to the stores in a single trip? Michael's software can find the answer.


See the Questionaire>>
COMMENTS On The Issues

funding more r&d: Many people don't see the value of basic research. They're interested only in practical applications. But without the exploration of new fundamental ideas, no new practical techniques would come about.

Basic research mostly occurs in two places — academia and government — because free markets lack the foresight to invest in basic R&D due to its low immediate return. So governments must fund most basic research. This type of research may not have immediate applications, but it facilitates the next breakthrough technologies. When Einstein was developing E=mc^2, he wasn't thinking of building nuclear bombs or nuclear power stations, he was working on quantum physics. Sure enough, though, his work advanced both theoretical and applied sciences.

What this means is that money spent today on basic research will give an appreciable increase in living standards and productivity down the line. So any rational increase in funding would be justified, even if it would require raising taxes.

INTEL SCIENCE SEARCH FINALIST Michael A. Forbes

Michael A. Forbes


Essay:

Why America's Schools Are Slipping


Montgomery Blair High School
Silver Spring, Md.


Hobbies: Ballroom dancing, origami, bonsai, golf, Linux


Ambition: Computer science professor