Timeline for Heuristic for optimising the traveling salesman problem (tsp) in under O(n²)
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 12, 2017 at 22:42 | comment | added | whatsisname | @FSMaxB: The travelling salesman problem is one of the most studied challenges in computer science. You need to review the scientific literature. | |
| Oct 12, 2017 at 18:36 | comment | added | FSMaxB | @Philipp: Good enough. | |
| Oct 12, 2017 at 18:19 | comment | added | Philipp | Do you need the provable best solution or would a "good enough" solution be sufficient? | |
| Oct 12, 2017 at 16:45 | comment | added | FSMaxB | @whatsisname: I understand that I was very vague. In the end all I can do is to try different ways to handle the data and analyze the result. But I can't do that if I don't find any way to finish the computation in let's say a few hours at max. Think of the dataset as arrays of 32bit integers on a regular x86_64 CPU (with 4-32 cores). | |
| Oct 12, 2017 at 16:41 | vote | accept | FSMaxB | ||
| Oct 12, 2017 at 15:27 | comment | added | whatsisname | What algorithms have you found, especially in academic journals? Also you haven't defined "too slow", as big-O complexity and real world speed are unrelated when looking at a single dataset size. There are algorithms out there that can process datasets of several millions of points in "reasonable" timeframes, but you haven't defined what reasonable is. | |
| Oct 12, 2017 at 15:12 | answer | added | TheCatWhisperer | timeline score: 0 | |
| Oct 12, 2017 at 14:54 | history | edited | FSMaxB | CC BY-SA 3.0 | added 952 characters in body |
| Oct 12, 2017 at 14:45 | comment | added | FSMaxB | Preferably better than randomly choosing two points and swapping them if it improves the total distance. (which would be one approach that is O(1), but maybe not really desirable) | |
| Oct 12, 2017 at 14:43 | comment | added | FSMaxB | @BobDalgleish I know that I can not calculate the distance between every pair of points, because that would be O(n²). I'm asking for a heuristic that produces a lower distance for the entire roundtrip than just randomly choosing points, but with a time complexity of less than O(n²). | |
| Oct 12, 2017 at 13:29 | comment | added | BobDalgleish | You are asking if you can compute the hamming distance matrix between each pair of points in less than O(n^2). The matrix will n rows and n columns. You have to fill half the entries in the matrix. The best you can do isn ^ 2 / 2 - n, which is O(n^2). | |
| Oct 12, 2017 at 8:31 | review | First posts | |||
| Oct 12, 2017 at 8:46 | |||||
| Oct 12, 2017 at 8:28 | history | asked | FSMaxB | CC BY-SA 3.0 |