#knapsackproblem

I’m a mathematician, so it’s not a huge surprise that I tend to view things through a mathematical lens, however I was shocked how much mathematics there is in planning a trip.

There is a well known math problem called the traveling salesman problem. In this problem, a travelling salesman has a bunch of cities he’d like to visit and wants to find the shortest path that allows him to visit all the cities exactly once. Don’t worry, I’m not going to rehash the choice of cities from my previous post. That’s all done. Mathematicians like to categorize things, and one thing that we do is categorize problems by how long it takes computers to solve them. The travelling salesman problem is a problem that takes a computer a very, very, long time to solve, or “NP”. You may have heard this language before in the “P vs NP” millennium problem. Problems that are “P” might take awhile for your computer to churn through (think uploading a large file to the internet), especially if you’re working with big files, but generally will at worst be “I have to leave my computer running overnight”. NP problems, if you want to do them on any kind of scale, quickly move into “this problem might be done before the sun runs out of fuel, if you’re lucky.” I’m massively oversimplifying a lot of very interesting mathematics here. Don’t at me Computability Theorists, I’m trying to make a joke.

But the travelling salesman problem has nothing on the travelling tourist problem. A tourist is not a salesman; she’s not on the clock, so she has a lot more flexibility. I can choose my landmarks, and I am going to prioritize some over others. For example I’m not looking for nightlife, so the hottest club would be low priority, however I really want to see the Curie Museum (yes, dork, I know). I also can choose how long I spend at each attraction (would you rather stay an extra hour at the Louvre, or climb the Eiffel Tower?). The more choices you have, the harder it gets to find the optimal solution. This is because there are more possible combinations which means more possibilities to check. Computers, they experience decision paralysis, just like us. Even so it might (MIGHT!) be possible to write an algorithm to optimize my path through each city, but it would involve as much effort as the average a PhD dissertation, and I just got OUT of school. On the other hand a group did find the optimal pub crawl through the entire United Kingdom (http://www.math.uwaterloo.ca/tsp/pubs/). Seeing as I leave in less than twenty four hours, and that project took them about 2 years it’s clear I’m a little behind schedule.

Okay, so no optimization algorithms for day planning. I guess I’m stuck making lists of places I absolutely must see, places I want to see, and places it would be nice to see, plotting them on maps and using ye olde eye test to do my best.

But what about packing? We spent two weeks in my mathematical optimization class studying the knapsack problem, which is literally about finding the optimal way to pack a bag for a trip. Due to the inductive magic of dynamic programming, and the fact that there’s less flexibility (each object is either in, or out) I probably would be actually able to solve this one. The problem would be that in order to do so I would have to have a database with the weight and dimensions of every object I might want to pack. And I have better things to do than sit around weighing and measuring all my possessions.

- What's the problem?

Coldplay - Paradise (Peponi) African Style (Piano/Cello) Cover - The Piano Guys ft. Alex Boye (ThePianoGuys tarafından)