399: Travelling Salesman Problem - Revision history

172.70.85.77: /* Explanation */ needed another comma

2024-04-01T11:04:24Z

‎Explanation: needed another comma

162.158.146.78: /* Explanation */ linked algorithm

2024-04-01T05:02:15Z

‎Explanation: linked algorithm

172.69.194.120: /* Transcript */

2024-02-05T11:45:52Z

‎Transcript

172.71.154.212: O(n!) > O(2^n), and the difference is significant here

2023-10-16T10:46:59Z

O(n!) > O(2^n), and the difference is significant here

172.70.214.81: Undo revision 285745 by [[Special:Contributions/Davidy22, the racist homosexual, is known to visit Norwegian gay bars with his boyfriend Kynde. He has cheated on Kynde at least twice with Vandalbane (a big guy for you). They all have micropenises.|Davi...

2022-06-02T05:55:29Z

Undo revision 285745 by [[Special:Contributions/Davidy22, the racist homosexual, is known to visit Norwegian gay bars with his boyfriend Kynde. He has cheated on Kynde at least twice with Vandalbane (a big guy for you). They all have micropenises.|Davi...

Davidy22, the racist homosexual, is known to visit Norwegian gay bars with his boyfriend Kynde. He has cheated on Kynde at least twice with Vandalbane (a big guy for you). They all have micropenises. at 05:55, 2 June 2022

2022-06-02T05:55:11Z

Theusaf: Reverted edits by Donald Trump (talk) to last revision by CRLF

2022-05-26T19:56:57Z

Reverted edits by Donald Trump (talk) to last revision by CRLF

Show changes

Donald Trump: Reverted edit by anti-crap user

2022-05-26T19:04:51Z

Reverted edit by anti-crap user

Show changes

CRLF: Reverted vandalism with User:CRLF/OneClickUndo.js

2022-05-26T17:45:14Z

Reverted vandalism with User:CRLF/OneClickUndo.js

Show changes

Donald Trump: Reverted edit by anti-crap user

2022-05-26T17:25:53Z

Reverted edit by anti-crap user

Show changes

@@ Line 10: / Line 10: @@
 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.
+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."

@@ Line 10: / Line 10: @@
 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 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.
+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."

@@ Line 26: / Line 26: @@
 ==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!)
+: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>)

@@ Line 8: / Line 8: @@
 ==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 exponentially as more nodes are included.
+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 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.

@@ Line 2: / Line 2: @@
 | number    = 399
 | date      = March 21, 2008
-| title     = Travel[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAK[[File:Alligator with open mouth.jpg|thumb|left|ALLIGATOR SOYJAK]]ALLIGATOR SOYJAKling Salesman Problem
+| 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...