Editing 399: Travelling Salesman Problem
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 8: | Line 8: | ||
==Explanation== | ==Explanation== | ||
| − | The {{w|Travelling | + | The {{w|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 their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and then returns to the origin city. A naive 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. A more efficient {{w|Dynamic programming|dynamic programming}} approach 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, to which the travelling salesman angrily responds "shut the hell up". | |
| − | The | + | The title text wonders about the time complexity of the {{w|Cutting-plane method}}, which is sometimes used to solve optimization problems. |
| + | The last sentence suggests the down side for Randall of writing 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. | ||
| − | + | This is so far the only comic featuring the [[Brown Hat]] character. | |
| − | + | Also see previous strip [[287: NP-Complete]]. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | Also see | ||
==Transcript== | ==Transcript== | ||
| − | :[There is a linked black web, with a path in red; it | + | :[There is a linked black web, with a path in red; it may be a map of the USA.] |
| − | :Brute-force solution: O(n!) | + | :Brute-force solution:O(n!) |
| − | :[The web continues in this one. A man with a | + | :[The web continues in this one. A man with a hat and a case is drawing it.] |
:Dynamic programming algorithms: O(n<sup>2</sup>2<sup>n</sup>) | :Dynamic programming algorithms: O(n<sup>2</sup>2<sup>n</sup>) | ||
| − | :[Another man, with a | + | :[Another man, with a hat too, is at a computer, looking back over the chair.] |
:Selling on eBay: O(1) | :Selling on eBay: O(1) | ||
:eBay salesman: Still working on your route? | :eBay salesman: Still working on your route? | ||
| Line 36: | Line 31: | ||
{{comic discussion}} | {{comic discussion}} | ||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
| + | [[Category:Comics featuring Brown Hat]] | ||
[[Category:Math]] | [[Category:Math]] | ||
| − | |||
