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 4: | Line 4: | ||
| title = Travelling Salesman Problem | | title = Travelling Salesman Problem | ||
| image = travelling_salesman_problem.png | | 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... | + | | 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== | ==Explanation== | ||
− | The {{w| | + | The {{w|Traveling salesman problem}} is a classic problem in computer science 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 returns to the origin city. A naive solution solves the problem in order of N! time (where N is the size of the list). The best algorithms can solve the problem in (N<sup>2</sup>2<sup>N</sup>) order time, which is better but still extremely slow. The joke is that the computer salesman selling on eBay 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". |
− | + | This is one of the few comics 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) | ||
− | : | + | :Computer salesman: Still working on your route? |
:Drawing salesman: Shut the hell up. | :Drawing salesman: Shut the hell up. | ||
{{comic discussion}} | {{comic discussion}} | ||
+ | [[Category:Comics featuring Cueball]] | ||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
− | [[Category: | + | [[Category:Comics featuring Brown Hat]] |
− |