[102] Travelling Salesman
Back to Problem Solutions forum
Hi all,
I've attempted the problem by looping all possibilities then realized thats too much to load for the actual problem so I found a method online called mlrose. but it seems this method is "taking a best guess"? And there will not be a definite answer. Is that why whenever I've failed, the page does not generate a set of expected results? Is mlrose the right approach?
Thanks in adv.
any help please? I've been stuck on this for very long
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.
I've implemented a depth-first search with backtracking and branch pruning. Rust implementation solved the problem in about 10 seconds. The general idea is to maintain the best tour (and its cost) so far and on every step of tours traversal to compare current tour cost to that best cost. If current cost is greater, we don't need to traverse this tour, just discard it and try another one.
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.
I computed cost of your solution at 654. Cost of my solution is 999. Your solution is more optimal. Thank you for responding.
This is the input data:
0 1:96 3:86 17:18 2:87 4:57 7:57 1 0:96 7:92 17:10 8:53 10:36 12:98 2 18:13 0:87 10:49 4:49 6:59 15:63 17:53 3 0:86 12:47 6:17 8:71 19:12 4 2:49 0:57 14:21 5:57 8:17 15:27 16:17 5 12:27 10:23 4:57 6 3:17 2:59 16:39 12:95 7 1:92 10:31 0:57 14:71 9:24 11:22 12:40 18:86 8 1:53 3:71 4:17 10:79 17:56 14:27 9 7:24 13:40 15:96 11:92 10 2:49 5:23 7:31 8:79 1:36 19:32 13:50 16:97 17:53 18:23 11 7:22 9:92 19:96 12 3:47 5:27 6:95 1:98 7:40 13:10 16:91 18:93 13 9:40 10:50 12:10 15:78 17:96 18:23 19:76 14 4:21 7:71 8:27 18:85 16:77 15 9:96 13:78 18:63 4:27 2:63 16 6:39 14:77 4:17 10:97 12:91 17:71 17 0:18 1:10 8:56 13:96 10:53 2:53 16:71 19:36 18 2:13 13:23 14:85 15:63 10:23 12:93 7:86 19 10:32 11:96 13:76 3:12 17:36
My answer was: 0 17 1 8 14 16 6 3 19 11 7 9 13 12 5 10 18 2 4 15
What's the right answer given the input data above?
Thank you gardengnome.