#1  
Old 05-08-2018, 03:51 AM
TheFallen018 TheFallen018 is offline
Junior Member
 
Join Date: May 2018
Posts: 1
Default 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.
Reply With Quote
  #2  
Old 06-09-2018, 05:52 PM
charlieabranches charlieabranches is offline
Junior Member
 
Join Date: Jun 2018
Posts: 2
Default Answer using logic and empirism

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
Reply With Quote
  #3  
Old 06-10-2018, 09:17 PM
fiddleback fiddleback is online now
Junior Member
 
Join Date: May 2013
Posts: 8
Default

Quote:
Originally Posted by charlieabranches View Post
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.)
Reply With Quote
  #4  
Old 06-12-2018, 01:08 PM
uigrad's Avatar
uigrad uigrad is offline
Senior Member
 
Join Date: Jan 2014
Posts: 110
Default

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.
Reply With Quote
  #5  
Old 06-12-2018, 04:53 PM
fiddleback fiddleback is online now
Junior Member
 
Join Date: May 2013
Posts: 8
Default

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

Thread Tools
Display Modes

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


All times are GMT. The time now is 02:33 PM.


Powered by vBulletin® Version 3.7.2
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.

About Puzzle Baron

The Puzzle Baron family of web sites has served millions and millions of puzzle enthusiasts since its inception in 2006. From cryptograms to acrostics, logic puzzles to drop quotes, patchwords to wordtwist and even sudoku, we run the gamut in word puzzles, printable puzzles and logic games.