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 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 | + | 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. |
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. | ||
