Wednesday, July 29, 2009

Travelling Salesman Problem is NP-complete

It's been a while since I was last in a classroom studying computability and complexity.

This is one of the most interesting results and it's worth remembering.

The TSP is described succinctly on wikipedia:

Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.


The key is that you have to visit each city exactly once and that it should be the shortest such tour.

Find a lot more about the TSP on wikipedia. And if you don't know what NP-complete is, here is the wikipedia page.

Why is this important? As software engineers and programmers, we should be aware of the limits of what we can do with our craft.

No comments: