Editing 399: Travelling Salesman Problem

{{comic
| number    = 399
| date      = March 21, 2008
| title     = Travelling Salesman Problem
| image     = travelling_salesman_problem.png
| titletext = What's the complexity class of the best linear programming cutting-plane techniques? I couldn't find it anywhere. Man, the Garfield guy doesn't have these problems...
}}

==Explanation==
The {{w|Travelling salesman problem|travelling salesman problem}} is a classic problem in computer science. An intuitive way of stating this problem is that given a list of cities and the distances between pairs of them, the task is to find the shortest possible route that visits each city exactly once and then returns to the origin city. A naïve solution solves the problem in {{w|Factorial|O(n!) time}} (where n is the size of the list), simply by checking all possible routes, and selecting the shortest one. However, this approach will take a long time as the number of possible routes increases superexponentially as more nodes are included.

A more efficient {{w|Dynamic programming|dynamic programming}} approach, the {{w|Held-Karp algorithm}}, yields a solution in O(n<sup>2</sup>2<sup>n</sup>) time. These times are given using {{w|Big O notation}}, which is commonly used in computer science to show the efficiency or complexity of a solution or algorithm.

The joke is that the salesman selling online (say on {{w|eBay}}, {{w|Amazon Marketplace}}, or other virtual marketplace) does not have to worry about this problem since he does not need to travel (which makes the time to find the best solution O(1)), to which the travelling salesman angrily responds, "Shut the hell up."

The title text wonders about the time complexity of the {{w|Cutting-plane method|cutting-plane method}}, which is sometimes used to solve optimization problems.

The last sentence suggests the downside for Randall of drawing comics about computer science; he sometimes encounters problems to which he cannot find the answer, whereas authors of simpler comics such as {{w|Garfield}} do not have this problem. This is also likely a reference to [[78: Garfield]], which parodies Garfield's simplicity.

The map almost certainly depicts the United States, with the locations highlighted suspected to be (from left to right): Seattle, San Francisco, Los Angeles, Phoenix, Denver, Minneapolis, Dallas, San Antonio, Houston, Chicago (cut off), Detroit, Atlanta, Miami, Washington D.C. Philadelphia, New York and Boston.

This is so far the only comic featuring the Brown Hat character.

Also see earlier strip [[287: NP-Complete]].

==Transcript==
:[There is a linked black web, with a path in red; it appears to be a map of the United States.]
:Brute-force solution: O(n!)
:[The web continues in this one. A man with a brown hat and a case is drawing it.]
:Dynamic programming algorithms: O(n<sup>2</sup>2<sup>n</sup>)
:[Another man, with a brown hat too, is at a computer, looking back over the chair.]
:Selling on eBay: O(1)
:eBay salesman: Still working on your route?
:Drawing salesman: Shut the hell up.

{{comic discussion}}
[[Category:Comics with color]]
[[Category:Math]]
[[Category:Programming]]