#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




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: DGHIFCBADHEBDEFBEHF (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; 06092018 at 05:52 PM. Reason: grammar mistakes 
#3




Quote:
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




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; 06122018 at 01:18 PM. 
#5




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

«
Previous Thread

Next Thread
»
Thread Tools  
Display Modes  


All times are GMT. The time now is 08:46 PM.