Hacker News Reader

Comment by molticrystal | Hacker News Reader

While it is wonderful they are getting closer to solving it, if your problem is a simple and practical you can try some alternative algorithms. For fun, I used pytspsa [0] which uses the simulated annealing method to solve the TSP and applied it to BOTW.

Simulated annealing was inspired by thermodynamic free energy involved in crystal formation from annealing metal. [1]

I combined it with a Breath of the Wild waypoint generator [2] to make my way around the map [3] in a mostly optimal fashion for my trip about Hyrule.

If you ever have a toy problem or even a real one, I suggest experimenting with pytspsa to see and understand in a concrete way the problem is solved.

[0] https://github.com/ildoonet/simulated-annealing-for-tsp

[1] https://en.wikipedia.org/wiki/Simulated_annealing

[2] https://github.com/MrCheeze/botw-waypoint-map

[3] https://user-images.githubusercontent.com/2829875/28661246-0...

View on HN

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?

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?

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.

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

Ah, I used Ant Colony Optimization to solve it a long time ago. I love simulated annealing, but in many cases the swarm based methods seem to perform better.

This is great, thanks for sharing!

I had good results with genetic algorithms as well.

There are also TSP-specific heuristics that work well in practice on a lot of large instances, often finding the optimal solution pretty quickly (but with no guarantees of optimality). The first I believe was the Lin-Kernighan heuristic from 1973 (the same Kernighan as the 'K' in K&R C, incidentally). There are fast implementations of some modern improved versions, e.g.: http://akira.ruc.dk/~keld/research/LKH/

I coded a version of SA for TSP in the early 90s. I iterated until the probability of a hardware error was greater than having a sub-optimal solution. It took just a couple of seconds, and that speed was due to visually displaying the algorithm as it executed.

I believe that this is about a different type of TSP problem, where the distances between cities are defined by the geometric distance from their coordinates in some plane (or on a sphere). This is a simpler problem than when the distances are specified as (whole) numbers.

Geometric distance implies symmetry, asymmetric TSP can be converted to symmetric by doubling the number of vertices.

Reply on news.ycombinator.com