3 ms·

Looking at the BOTW solution is doesn't seem to take into account the fact that a straight line is not the fastest solution. Climbing is incredibly slow, swimm

Looking at the BOTW solution is doesn't seem to take into account the fact that a straight line is not the fastest solution. Climbing is incredibly slow, swimming is slow and perilous, in some places such as the dark forest you can only enter/exit in one place, not randomly, you can travel faster on roads. I guess later in the game one doesn't mind randomly walking right by the castle just because it is the shortest path, just going to eat some time dealing with each guardian of course. Same for swimming across a the river twice around a bend rather than just following the coastline. Also there are 226 waypoints, the linked map is missing a lot... I am not sure what it is trying to show. Was this the waypoints you had not done at the end of the game?

chottocharaii 6y ago
Hey man, this is just a person’s fun and imaginative side project. Is there a reason you’re offering such serious and negative critical commentary on this?
- fjfaase 6y ago
  I think the parent wanted to point out that this is about a completely different problem. The algorithm mentioned works on cities that are defined with coordinates in some plane and where the distances between two points is defined as the geometric distance. The article talks about the problem where the distances between cities are given (and not based on their coordinates). The later is a much harder problem.
  - mousebaiker 6y ago
    The original paper mentioned in the article [1] deals with metric TSP, so a triangle inequality must be satisfied. This means that you can actually find a space where the points will be the coordinates. Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it. [1] https://arxiv.org/abs/2007.01409 https://arxiv.org/abs/2007.01409

chottocharaii 6y ago

Hey man, this is just a person’s fun and imaginative side project. Is there a reason you’re offering such serious and negative critical commentary on this?

fjfaase 6y ago
I think the parent wanted to point out that this is about a completely different problem. The algorithm mentioned works on cities that are defined with coordinates in some plane and where the distances between two points is defined as the geometric distance. The article talks about the problem where the distances between cities are given (and not based on their coordinates). The later is a much harder problem.
- mousebaiker 6y ago
  The original paper mentioned in the article [1] deals with metric TSP, so a triangle inequality must be satisfied. This means that you can actually find a space where the points will be the coordinates. Anyway, the grandparent solves the Euclidean TSP which is still an NP-complete problem. I will be reluctant to say that it is an easier problem in a general sense. I agree though that there are better and easier approximations for it. [1] https://arxiv.org/abs/2007.01409 https://arxiv.org/abs/2007.01409