Logic Puzzle Forums Variation of Travelling Salesman
 FAQ Members List Calendar Search Today's Posts Mark Forums Read

#1
05-08-2018, 03:51 AM
 TheFallen018 Junior Member Join Date: May 2018 Posts: 1
Variation of Travelling Salesman

Came across this puzzle, and I couldn't really find a good way to solve it. I would be interested if someone could come come up with a good formula for doing this one.
#2
06-09-2018, 05:52 PM
 charlieabranches Junior Member Join Date: Jun 2018 Posts: 2

Any aspect that you can to consider:
a) we have 9 points
b) we have 8 triangles
C)we have so 1 big square and 4 little squares
d) we have a diamond
e) we have two lines crossing in the center of the big square

Isn't possible to walk all path's with 0 and 1 repetion, I concluse that because I try a lot times, but i can't prove with a formula. So in this case you can do the best path with you take all path's one time and take the two little paths one more time. Therefore, the little path is equal to:
D-G-H-I-F-C-B-A-D-H-E-B-D-E-F-B-E-H-F (the path point by point in the order)
Total path =150+200+200+150+150+200+200+150+250+150+150+250+2 00+200+250+150+150+250=3400m
I search a little about "how to make the little path formula" and i discovery an method, but I don't know use because it's hard, but you maybe can, so try read Dijkstra Algorithm.
I try my best, but this problem is much complex because we have much possibilites.

Last edited by charlieabranches; 06-09-2018 at 05:52 PM. Reason: grammar mistakes
#3
06-10-2018, 09:17 PM
 fiddleback Junior Member Join Date: May 2013 Posts: 8

Quote:
 Originally Posted by charlieabranches Any aspect that you can to consider: Isn't possible to walk all path's with 0 and 1 repetion, I concluse that because I try a lot times, but i can't prove with a formula.
Count the number of paths connected to each point. Whenever a walker approaches a point, he takes one path; he leaves by another. If a point has an even number of connected paths, it may be possible to visit (and revisit) it without reusing a path. If a point has an odd number of connected paths, the walker will be forced to reuse one.

If you consider the entrance and exit arrows to be paths, all points have an even number of connected paths except B and H. So you'll be required to reuse one path for each of those points. Your solution reuses the shortest path in both cases, and has no other repetitions. So it's the best possible result. (I think.)
#4
06-12-2018, 01:08 PM
 uigrad Senior Member Join Date: Jan 2014 Posts: 110

I agree with both people above me. The solution given is minimal.

The logic that fiddleback explained is the same as the logic that Euler used to prove that the Seven Bridge problem had no answer:

https://en.wikipedia.org/wiki/Seven_...%C3%B6nigsberg

Since there are 2 vertices with odd numbers of paths, we know that the shortest solution will have at least 2 repeated paths. The shortest paths are 150m, so we know that the shortest minimum amount of extra walking will be 300m.

The solution by charlieabranches contains only 300m of extra walking. So, we can conclude that it is minimal.

Sometimes I've seen questions like this with a part 2, which to make a path that is minimal that doesn't cross itself. An example that is minimal that doesn't cross itself is here:

Last edited by uigrad; 06-12-2018 at 01:18 PM.
#5
06-12-2018, 04:53 PM
 fiddleback Junior Member Join Date: May 2013 Posts: 8

You always post solid references with your explanations. Thanks for the Konigsberg link!

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Logic-Puzzles.org Discussion     Questions About Logic-Puzzles.org     Comments, Bugs and Feature Requests Other Logic Puzles     Logic Puzzles and Brain Benders Puzzle Baron's Logic Puzzles - The Book!

All times are GMT. The time now is 09:57 PM.