Why is the Traveling Salesperson Problem "Difficult"?

Question

The Traveling Salesperson Problem is originally a mathematics/computer science optimization problem in which the goal is to determine a path to take between a group of cities such that you return to the starting city after visiting each city exactly once and the total distance (longitude/latitude) traveled is minimized. For $n$ cities, there are $(n-1)!/2$ unique paths - and we can see that as $n$ increases, the number of paths to consider becomes enormous in size. For even a small number of cities (e.g. 15 cities), modern computers are unable to solve this problem using "brute force" (i.e. calculate all possible routes and return the shortest route) - as a result, sophisticated optimization algorithms and approximate methods are used to tackle this problem in real life.

I was trying to explain this problem to my friend, and I couldn't think of an example which shows why the Travelling Salesperson Problem is difficult! Off the top of my head, I tried to give an example where someone is required to find the shortest route between Boston, Chicago and Los Angeles - but then I realized that the shortest path in this case is pretty obvious! (i.e. Move in the general East to West direction).

Real world applications of the Travelling Salesperson Problem tend to have an additional layer of complexity as they generally have a "cost" associated between pairs of cities - and this cost doesn't have to be symmetric. For example, buses might be scheduled more frequently to go from a small city to a big city, but scheduled less frequently to return from the big city to the small city - thus, we might be able to associate a "cost" with each direction. Or even a simpler example, you might have to drive "uphill" to go from City A to City B, but drive "downhill" to go from City B to City A - thus there is likely a greater cost to go from City A to City B. Many times, these "costs" are not fully known and have to be approximated with some statistical model. However, all this can become a bit complicated to explain to someone who isn't familiar with all these terms.

But I am still looking for an example to explain to my friend - can someone please help me think of an obvious and simple example of the Travelling Salesperson Problem where it becomes evidently clear that the choice of the shortest path is not obvious? Every simple example I try to think of tends to be very obvious (e.g. Manhattan, Newark, Nashville) - I don't want to overwhelm my friend with an example of 1000 cities across the USA : just something simple with 4-5 cities in which it is not immediately clear (and perhaps even counterintuitive) which path should be taken?

I tried to show an example using the R programming language in which there are 10 (random) points on a grid - starting from the lowest point, the path taken involves choosing the nearest point from each current point:

library(ggplot2)

set.seed(123)

x_cor = rnorm(5,100,100)
y_cor = rnorm(5,100,100)


my_data = data.frame(x_cor,y_cor)

      x_cor     y_cor
1  43.95244 271.50650
2  76.98225 146.09162
3 255.87083 -26.50612
4 107.05084  31.31471
5 112.92877  55.43380


ggplot(my_data, aes(x=x_cor, y=y_cor)) + geom_point() + ggtitle("Travelling Salesperson Example")

But even in this example, the shortest path looks "obvious" (imagine you are required to start this problem from the bottom most right point):

I tried with more points:

set.seed(123)

x_cor = rnorm(20,100,100)
y_cor = rnorm(20,100,100)


my_data = data.frame(x_cor,y_cor)

ggplot(my_data, aes(x = x_cor, y = y_cor)) +
    geom_path() +
    geom_point(size = 2)

But my friend still argues that the "find the nearest point from the current point and repeat" (imagine you are required to start this problem from the bottom most right point):

How do I convince my friend that what he is doing corresponds to a "Greedy Search" that is only returning a "local minimum" and it's very likely that a shorter path exists? (not even the "shortest path" - just a "shorter path" than the "Greedy Search")

I tried to illustrate this example by linking him to the Wikipedia Page on Greedy Search that shows why Greedy Search can often miss the true minimum : https://en.wikipedia.org/wiki/Greedy_algorithm#/media/File:Greedy-search-path-example.gif

• Could someone help me think of an example to show my friend in which choosing the immediate nearest point from where you are, does not result in the total shortest path? (e.g. some example that appears counterintuitive, i.e. if you choose a path always based on the nearest point from your current position, you can clearly see that this is not the optimal path)

• Is there a mathematical proof that shows that the "Greedy Search" algorithm in Travelling Salesperson has the possibility of sometimes missing the true optimal path?

Thanks!

Answer 1

Here's a simple explicit example in which the greedy algorithm always fails, this arrangement of cities (and euclidean distances):

If you apply the greedy algorithm on this graph, it'll look like the following (or a flipped version):

This is true regardless of the starting point. This means the greedy algorithm gives us a path with a total distance traveled of $20 + 2 + 2\sqrt{101} \approx 42.1$

Clearly, this isn't the optimal solution though. Just by eyeballing it, you can see that this is the best path:

It has a total length of $4\sqrt{101} \approx 40.2$, which is better than the greedy algorithm.

You can explain to your friend that the reason why the greedy algorithm fails is because it doesn't look ahead. It sees the shortest path (in this case, the vertical one), and takes it. However, doing so may later force it to take a much long path, leaving it worse off in the long run. While it's simple to see in this example, detecting every case where this happens is a lot harder.

Answer 2

It seems to me that you are looking for an intuitive insight, and not a counterexample or a formal proof. I was wondering the same thing many years ago and the following allowed me to achieve an intuitive insight:

I experimented with a TSP solver program called Concorde. That program allows you to place points and it can also drop points randomly. It will then show the solving process as it happens.

You can then see live how the currently known best path is evolving. Very different paths will be shown, each one a little bit better than before.

This showed me that vastly different paths can lead to incremental tiny improvements. And this showed me how "non-convex" the solution is. You can't just use a hill climbing algorithm to zero in on the best solution. The problem contains decision points leading to vastly different parts of the search space.

This is an entirely non-formal way of looking at this, but it helped me a lot.

Answer 3

Here's a 7 city example, from Wikipedia. The nearest-neighbor algorithm gives different paths depending on which city you start at, so the result must be suboptimal for all but one of these paths. The illustration uses paths instead of cycles, but you can mentally connect up all of those paths to cycles and my point still applies.

Answer 4

The problem is hard because of the combinatorial complexity of proving you have the best answer

There is a subtle distinction at play when people talk about optimal results in problems like this. A mathematician or an operational research expert use the term "optimal" in a different way to to non-experts. Many non-experts interpret optimal as "good enough" but experts often insist on proof of optimality.

When solving real world TSP-like problems it is arguable that the lay definition ("good enough") is actually more useful (especially if the cost of finding a better answer is high). But TSP like problems have a serious issue with proving any answer is optimal in the expert sense. We don't know an efficient way of proving that a given answer is best that doesn't, in effect, involve testing every possible route which is ridiculous as the number of possibilities rises with the factorial of the number of cities (even small problems are too big: 50! is more than 10^64).

The be fair to some commenters, there are some methods better than brute force but none escape the fundamental difficulty of NP-hard problems where the time to solve a problem grows too quickly with the size of the problem for any usable algorithm to be of practical general use. Goyal, summarising some results about efficient algorithms, puts this insight in more mathematical terms (my highlight):

The combinatorial optimization version i.e. the problem of finding the minimum hamiltonian cycle in a graph of cities, and the decision version i.e. the problem of checking the existence of a hamiltonian cycle in a graph smaller than a given weight. In the theory of computational complexity, the combinatorial optimization version belongs to the NP Hard set of problems implying that there is no polynomial time algorithm even for checking the correctness of a given solution to the problem, whereas the decision version belongs to the class of NP complete problems implying that a solution can be checked in polynomial time. Though without a proof that P≠NP, it can only be assumed that there is no efficient algorithm for solving any version of the TSP.

In practice, there are heuristics that can get very good results quickly but none can guarantee the absolute best result.

As Andrew P pointed out in his answer, it is possible to show that even in very simple systems a greedy algorithm is sometimes wrong on the expert optimality criterion. But your friend might be wondering whether that difference matters as it is often not huge versus the known optimal answer.

That is where being clear about what optimal means is important. Experts might argue that they need absolute proof that the answer is the best possible. Non-experts might argue that "good enough" is fine. Or even that the idea of optimality needs to be extended include the cost to get the answer (some combination of computer power and time taken).

If you are of the opinion that cost-to-find-the-answer is relevant (as many practical real world users are) then your "optimal" answer will be good enough without being optimal in the expert sense. Most TSP-like problems have many easy to find good answers that are within a few % of the known expert optimum. Greedy algorithms will often find those in non-pathological cases, though there are more complex algorithms that are better.

So be clear about your definition of "optimal" and much of the argument might disappear.

Answer 5

An analogous problem is the knight's tour (making a knight visit every square on a chessboard exactly once). In my book XSLT Programmer's Reference I included a "solution" to this (written in XSLT) that used the intuitive approach of always moving to the available square with fewest exits: and I appealed to my readers for feedback on whether the algorithm was actually guaranteed to succeed. Ten years later a reader responded with a counter-example: a starting square where the knight got stuck and had to backtrack. It turned out there was only one such starting square (ignoring symmetries).

I mention this purely as an example of how an intuitive algorithm can give a useful solution most of the time even though it is wrong.

Incidentally, the example from @AndrewP suggests that the route produced by a naive algorithm is only a bit worse than the optimal route. That isn't always going to be the case. Consider 1000 points 1km apart around the circumference of a circle, and one point 20km outside the circle. There's a good "obvious" solution which is to visit the outlier when you're at the point nearest to it; but that "obvious" solution is far better than the simplistic greedy algorithm.

Answer 6

A counterargument to the notion that the greedy algorithm is optimal is to note that the greedy solution can produce different solutions depending on where you start, but there is usually just one optimal loop through all the cities regardless of starting point. The greedy algorithm can produce more than one solution, and so long as they represent solutions of different total length, not all of them can be optimal.

Suppose you have 4 cities, A, B, C, and X. A and B both have X as their nearest neighbor, while X has C as its nearest neighbor. If you start at A, the greedy path will include A-X-C, while if you start at B, the greedy path will include B-X-C. It's simple to construct path distances such that the total distances of these solutions are unequal, and therefore, they cannot both be optimal. The length of the shortest circuit is a function of travel cost matrix only, the starting point is irrelevant. Since the greedy method can produce multiple solutions of different total length, we certainly cannot guarantee that a particular solution it produces is optimal (although in some cases, it may be).

Answer 7

Here's an example that isn't obvious to me. Your goal is to visit the capital cities of all 50 US states as cheaply as possible. You can rent a car, so long as you are not heading to Hawaii or Alaska, and the cost is however much you'll have to pay to get from one city to the next, taking into account driving time, traffic, gas prices, rental prices, hotel prices, etc. You can also fly, and the cost of the flight depends on how popular the route is and how far you are flying. Let's assume there are always direct flights but they might be very expensive for unusual routes. I honestly have no clue how you would figure out even a halfway decent route without computer science.

As for why the greedy algorithm doesn't work: Let's suppose you start in Maine and the most expensive destinations are Hawaii and Alaska (not surprising). You'd make your way greedily around the mainland US until you exhausted the lower 48, then you'd probably fly over to Alaska, then catch another flight to Hawaii, and fly straight back to Maine. My guess is that direct flights between from Alaska to Hawaii, and Hawaii and Maine, if they existed, would be ruinously expensive, and so right there you've made a strategic blunder. It would have been much better to fly to Hawaii from a well-connected west coast city, and likewise to return from Hawaii to a well-connected west coast city, rather than making an Alaska->Hawaii->Maine trip.

Answer 8

I'm going to take a slight departure from the question as-asked to try to provide a more intuitive explanation of why TSP is hard. @matt_block's answer is excellent, but targeted at those with more experience and/or formal training in math than I hope mine to be.

But I am still looking for an example to explain to my friend - can someone please help me think of an obvious and simple example of the Travelling Salesperson Problem where it becomes evidently clear that the choice of the shortest path is not obvious? Every simple example I try to think of tends to be very obvious (e.g. Manhattan, Newark, Nashville) - I don't want to overwhelm my friend with an example of 1000 cities across the USA : just something simple with 4-5 cities in which it is not immediately clear (and perhaps even counterintuitive) which path should be taken?

It's those thousand-city scenarios that really hit home that the TSP is hard.

Humans aren't computers, and computers aren't humans

Humans can do things that computers can't do, yet. Among them is heuristically weeding out obviously-bad TSP paths; eg., when trying to "find the shortest route between Boston, Chicago and Los Angeles", it's easy to look at a map and "realize[] that the shortest path in this case is pretty obvious". Computers can't do that (at least, not yet). Rather, the computer has to check both B->C->LA and B->LA->C to know which one is better. Humans don't (think that they) have to do that for such an obvious case, so it's unintuitive how hard it is for a computer.

Start adding in more cities and it becomes more obvious that picking the right path is hard.

Of course, TSP asks for a circular route; it's entirely possible that both routes will have the same cost with the return trip factored in.

Humans have difficulty with extreme growth

It's easy to look at a map with 3, 5, or 11 dots and pick out the obviously-best path - or, at least, pick out 2 or 3 prime candidates for comparison. It seems intuitive that adding one more dot wouldn't make it that much more difficult to find the optimal path. And it isn't, right up until it is. There comes a point (where that is will vary from person to person and map to map) at which adding one more dot drastically increases the number of candidates - the heuristics the person is using to weed out bad paths (Boston to LA to Chicago) break down in the face of having too many options.

Until you see that breakdown in heuristics, it can be hard to wrap your head around how steep that cliff can be.

Computers are really dumb

Computers aren't smart, they just pretend to be smart by cheating. They cheat by being able to do basic math really fast, then pretending that everything in the universe is basic math (which, to be fair, works an astonishing amount of the time).

Most of the time, that cheating is good enough for us to think of computers as smart (or "magic") boxes - in goes some data, out comes an Excel file with pretty graphs; in goes some other data, out comes a CGI Gollum.

But, computers - even the fancy new machine-learning neural nets - don't have any idea about the context of the things they're being asked to do. They have no idea whether they're adding up numbers of ticket sales for the latest blockbuster movie, counting video rentals at the last Blockbuster, or piloting an airplane. They can just add, subtract, multiply, divide, and do bit-wise logic (sometimes emulating one via another); everything else is based on that.

So, computers can't look at a map (they have no eyes, nor any concept of what a "map" is) and have the shortest loop jump out at them (what's a loop? what's "short"?). They have to do the math, checking every possible route to see if it's the shortest.

Are you really sure that's the shortest?

As @matt_block pointed out, part of the problem with TSP (and related problems) is being 100% sure that you've found a shortest path (it's possible there are ties).

If you just care about distance (or can figure out some other good way of putting the dots on something map-like), humans can weed out some obvious bad plans (if you're trying to hit the state capitals, it makes zero sense to go straight from Boston to St. Paul), thus reducing the search space for "optimal". But: proving that there are no routes shorter than "this" one means looking at a whole bunch of variations in order (it's highly probable that Boston -> Concord -> Augusta -> Montpelier is part of the optimal route, but it's theoretically possible that there aren't any roads between Boston and Concord that don't go through Augusta, to torture this metaphor).

Computers can't even cut out the obviously bad trips (Boston to St. Paul) out of hand. They can stop considering a route when its current length is greater than the shortest known length, but they can't throw out the Boston to St. Paul option entirely. Thus, computers need to at least partially-examine all (n−1)!/2 routes.

The knapsack analogy

If I recall my CS101 class correctly, the knapsack problem is transformable into TSP. Basically: how efficiently can you pack a knapsack (given a set of items, what's the least unused capacity of the knapsack you can end up with).

Intuitively, TSP is a variant of the knapsack problem: given a set of cities, what's the smallest knapsack that can hold a circular route that visits each city? ... where the knapsack's capacity is "miles" or "dollars" or "hours" or even "dollar-miles per hour", depending on what we're optimizing for.

Greedy algorithms clearly don't work. Consider a knapsack that can hold 12 units, and a set of item costs [ 10, 3, 3, 3, 3 ] - a greedy algorithm would put in the 10-cost item and have 2 capacity left over, but it's clear that leaving out the 10-cost item would let the 4x3-cost items perfectly fill the knapsack.

"Anti-greedy" algorithms (that is, starting with the smallest numbers first) also clearly don't work. Consider that same 12-unit knapsack and item costs of [ 1, 12 ]: put in the 1-cost item and have 11 capacity left over, even though there's a 12-cost item that can perfectly fill the knapsack.

Again: many humans (to a rounding error, likely "all who are likely to see this answer") can look at those item cost sets and immediately see what the optimal choice is. But, start increasing the capacity of the knapsack and the count of items in the set, and that immediacy quickly falls off to "pretty quickly", then to "I've got 2 capacity left over and I don't see an obvious way to fill it, but I'm not positive there isn't one".

Circling back to TSP explicitly, that last case is "I've got the circuit down to a cost of 302, and I don't see an obvious way to reduce it, but I'm not positive there isn't one".

Answer 9

If you want a real-world demonstration of the difficulty of choosing a good travel path, get a 3D printer and print a complex model with lots of disconnected components in each layer. The software that slices it for printing (note: you can just slice stuff without a printer to see the results, but actually printing it "makes it real") has to choose the order to visit components and travel between them, and inevitably will do things that "seem wrong" and often that are wrong (suboptimal) because solving the problem optimally is not feasible.

Answer 10

The Traveling Salesperson Problem is not "Difficult" to realize. The problem is, it is very expensive in the count of search.

To get the best path, you have to visit each city from each start point and this count of visits grow very fast in a size you can't realize.

In faculty or n!

• Best path to visit 8 cities result in 40320 checks.
• For 12 cities this results in more then 4 billion checks.

In our time today what are 4 billion checks for computers with 4GHz, not really much. Some decades ago at time I began to study (1992) the computers are much slower (~486DX40 40mhz) that today (Alder Lake 12900 5.2ghz) we have today 130 times more mhz, but the number of calculable cities has grown by half. From 8 to 12 maybe 13 in the same calculation time.

Today it may be more helpful to find a "good enough for now" resolution.