Posts
 |
| The "knapsack problem" is a widespread computing challenge—and no, it doesn't have to do just with literal backpacks. Photo: golubovy / iStock |
Imagine
you’re a thief robbing a museum exhibit of tantalizing jewelry, geodes
and rare gems. You're new at this, so you only brought a single
backpack. Your goal should be to get away with the most valuable objects
without overloading your bag until it breaks or becomes too heavy to
carry. How do you choose among the objects to maximize your loot? You
could list all the artifacts and their weights to work out the answer by
hand. But the more objects there are, the more taxing this calculation
becomes for a person—or a computer.
This
fictional dilemma, the “knapsack problem,” belongs to a class of
mathematical problems famous for pushing the limits of computing. And
the knapsack problem is more than a thought experiment. “A lot of
problems we face in life, be it business, finance, including logistics,
container ship loading, aircraft loading — these are all knapsack
problems,” says Carsten Murawski, professor at the University of
Melbourne in Australia. “From a practical perspective, the knapsack
problem is ubiquitous in everyday life.”
Researchers once took advantage of the problem’s complexity to create computer security systems, but these can now be cracked since the problem has been so well studied. Today, as technology capable of shattering the locks on our digital communications loom on the horizon, the knapsack problem may inspire new ways to prepare for that revolution...
“The problem the theoreticians started to look at was how efficiently a particular task can be carried out on a computer,” writes Keith Delvin in the book The Millennium Problems. For example: Given a list of 1 million museum artifacts with their weights and monetary values, and a backpack limited to 25 pounds, a computer would have to run through every possible combination to generate the single one with the most lucrative haul. Given an indefinite amount of time, a computer could use brute force to optimize large cases like this, but not on timescales that would be practical...
For those of us who are not computer scientists and face these kinds of problems in real life, how good are we? Murawski’s group finds preliminary results that when you give humans knapsack-like problems, we also struggle mightily. In small experiments in which participants were asked to fill a backpack on a computer screen with items carrying stated values and weights, people tended to have a harder time optimizing the backpack’s contents as the number of item options increased—the same problem computers have. The researchers say this finding may be related to “choice overload”: the way we freeze up when given too many choices, even in simple situations like buying jam at a grocery store.
Read more...
Recommended Reading
 |
| The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles Of Our Time |
Source: Smithsonian
