[102] Travelling Salesman
source link: https://www.codeabbey.com/index/forum_topic/f32ee1673bac1a3fc4e8f4f842a6b52a
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[102] Travelling Salesman |
Back to Problem Solutions forum
Hi! This took me a very long time, too. I did a lot of research. I read the Wikipedia article on the traveling salesman problem, downloaded several research papers and failed miserably several times with various approaches.
I was finally able to implement a branch-and-bound algorithm. I used a depth-first search to avoid some of the traps I had set for myself by trying to employ some sort of heuristic to limit possible answers. Much of this stuff is WAY OVER MY HEAD.
Don't be discouraged. It took me a long time, but I finally understood it, got the program working without bugs, and managed to solve the puzzle without the computer blowing up or the universe ending first.
Research branch-and-bound algorithm. And, of course Traveling Salesman Problem. And be patient and gentle with yourself. The last two are the most important, I think.
This is the input data I tried solving:
0 16:97 6:13 8:53 1:43 5:71 7:57 1 6:69 0:43 18:17 13:58 15:72 16:32 2 16:47 15:16 13:72 7:51 18:85 3 19:46 13:14 11:56 14:88 17:40 4 9:74 15:16 13:92 5 7:64 14:19 0:71 10:40 6 0:13 1:69 18:99 8:75 10:83 12:71 13:81 7 5:64 8:23 2:51 0:57 15:80 16:30 17:96 18:26 19:40 8 0:53 6:75 7:23 18:17 16:15 17:94 11:63 9 4:74 11:20 17:30 15:84 16:12 10 6:83 5:40 19:78 14:53 12:93 11 3:56 9:20 16:17 14:85 8:63 15:20 19:76 12 6:71 16:69 10:93 13 2:72 3:14 4:92 16:11 6:81 1:58 17:66 14 5:19 10:53 11:85 16:41 3:88 17:64 15 2:16 4:16 9:84 7:80 1:72 11:20 16 0:97 2:47 8:15 11:17 12:69 13:11 14:41 1:32 7:30 9:12 18:95 17 8:94 9:30 14:64 3:40 13:66 7:96 19:52 18 1:17 6:99 8:17 7:26 2:85 16:95 19 3:46 10:78 11:76 17:52 7:40
The optimum tour I submitted is:
0 7 19 17 14 3 13 16 2 18 1 15 4 9 11 8 6 12 10 5
The feedback I got for the answer was it was not optimal.
Can I get the right answer so I can check my work and try another solution.
Recommend
-
41
-
26
psr-http-message-tracy-panel A panel for Tracy, that traces PSR HTTP messages travelling between your PHP backend and other HTTP servers.
-
37
Ant Colony Optimization visualization for the Travelling Salesman Problem This small experiment stands as a way for visualizing the Travelling Salesman Problem (TSP) solution, using the Ant Colony Optimization st...
-
37
Have you ever heard of the Travelling Salesman Problem? I'm pretty sure you do, but let's refresh our mind looking at its formulation: "Given a list of points and the distances between each pair of points, what is the sho...
-
11
Travelling Salesman Problem (TSP) with PythonImplementing Dynamic Programming, ILP, Simulated Annealing and Genetic algorithms for TSP, 2-OPT Approximation Algorithm for Metric TSP and Polynomial-time DP algorithm for Bit...
-
12
How to Code the Travelling Particles Animation from “Volt for Drive” A coding session where you'll learn how to implement Volt for Drive's travelling particles animation with Three.js.
-
8
PAT A1150 Travelling Salesman Problem(C++) 发表于 2019-12-04...
-
9
Business TravelTop 10 countries where people think of travelling more sustainably in the futureSustainable tourism is evolving in a new trend, especially...
-
57
Bitonic Travelling Salesman ProblemGiven a 2D array, arr[][] denoting a list of coordinates of N vertices on 2D space that i...
-
5
Travelling Salesman ProblemSkip to content
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK