https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&user=69.193.7.67&feedformat=atomexplain xkcd - User contributions [en]2019-09-18T03:48:45ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=399:_Travelling_Salesman_Problem&diff=50046399: Travelling Salesman Problem2013-10-05T18:02:09Z<p>69.193.7.67: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 399<br />
| date = March 21, 2008<br />
| title = Travelling Salesman Problem<br />
| image = travelling_salesman_problem.png<br />
| 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...<br />
}}<br />
<br />
==Explanation==<br />
The {{w|Travelling 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 {{w|Big O notation|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 {{w|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".<br />
<br />
The title text wonders about the time complexity of the {{w|Cutting-plane method}}, which is sometimes used to solve optimization problems.<br />
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.<br />
<br />
This is so far the only comic featuring the [[Brown Hat]] character.<br />
<br />
Also see previous strip [[287: NP-Complete]].<br />
<br />
==Transcript==<br />
:[There is a linked black web, with a path in red; it may be a map of the USA.]<br />
:Brute-force solution:O(n!)<br />
:[The web continues in this one. A man with a hat and a case is drawing it.]<br />
:Dynamic programming algorithms: O(n<sup>2</sup>2<sup>n</sup>)<br />
:[Another man, with a hat too, is at a computer, looking back over the chair.]<br />
:Selling on eBay: O(1)<br />
:Computer salesman: Still working on your route?<br />
:Drawing salesman: Shut the hell up.<br />
<br />
{{comic discussion}}<br />
[[Category:Comics with color]]<br />
[[Category:Comics featuring Brown Hat]]<br />
[[Category:Math]]</div>69.193.7.67https://www.explainxkcd.com/wiki/index.php?title=Talk:399:_Travelling_Salesman_Problem&diff=50045Talk:399: Travelling Salesman Problem2013-10-05T18:01:00Z<p>69.193.7.67: </p>
<hr />
<div>Does anyone remember if the Brown Hat appears in any other comics?<br />
: I'm not sure, so I created a category and page for him, let's see if that catches any others. --[[User:Jeff|<b><font color="orange">Jeff</font></b>]] ([[User talk:Jeff|talk]]) 22:04, 29 March 2013 (UTC)<br />
<br />
*It's probably not in the least important, but the network appears to be a collection of key cities in the US arranged by geographical location. [[Special:Contributions/130.160.145.185|130.160.145.185]] 23:07, 9 March 2013 (UTC)<br />
<br />
<br />
- added a better explanation of the title text. -- Nick,5 Oct 2013</div>69.193.7.67https://www.explainxkcd.com/wiki/index.php?title=399:_Travelling_Salesman_Problem&diff=50044399: Travelling Salesman Problem2013-10-05T17:50:42Z<p>69.193.7.67: /* Explanation */</p>
<hr />
<div>{{comic<br />
| number = 399<br />
| date = March 21, 2008<br />
| title = Travelling Salesman Problem<br />
| image = travelling_salesman_problem.png<br />
| 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...<br />
}}<br />
<br />
==Explanation==<br />
The {{w|Travelling 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 {{w|Big O notation|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 {{w|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".<br />
<br />
The title text wonders about the time complexity of the {{w|Cutting-plane method}}, which is sometimes used to solve optimization problems.<br />
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 the Garfield's simplicity.<br />
<br />
This is so far the only comic featuring the [[Brown Hat]] character.<br />
<br />
Also see previous strip [[287: NP-Complete]].<br />
<br />
==Transcript==<br />
:[There is a linked black web, with a path in red; it may be a map of the USA.]<br />
:Brute-force solution:O(n!)<br />
:[The web continues in this one. A man with a hat and a case is drawing it.]<br />
:Dynamic programming algorithms: O(n<sup>2</sup>2<sup>n</sup>)<br />
:[Another man, with a hat too, is at a computer, looking back over the chair.]<br />
:Selling on eBay: O(1)<br />
:Computer salesman: Still working on your route?<br />
:Drawing salesman: Shut the hell up.<br />
<br />
{{comic discussion}}<br />
[[Category:Comics with color]]<br />
[[Category:Comics featuring Brown Hat]]<br />
[[Category:Math]]</div>69.193.7.67