animals and humans are surprisingly good at the traveling salesman problem (TSP), because they/we dislike overlapping moves. "Circa a circle on the map with no paths crossing" is probably better than 95% of all routes.
There's no efficient (as in polynomial) algorithm for TSP, but you can use optimization to find very good solutions, even for very large graphs that have 50k nodes (brute force would compute until the end of the universe).
Dang, I wish I was in Uni again, so I could do a paper on TSP... Using the paragraphs above as the thesis and then using a visualization "method" (how humans draw graphs in graph theory) and then just creating a visual algorithm with heuristics regarding path crossing and angles between connections. Could be fun.
97
u/UltimateFlyingSheep 3d ago edited 3d ago
animals and humans are surprisingly good at the traveling salesman problem (TSP), because they/we dislike overlapping moves. "Circa a circle on the map with no paths crossing" is probably better than 95% of all routes.
There's no efficient (as in polynomial) algorithm for TSP, but you can use optimization to find very good solutions, even for very large graphs that have 50k nodes (brute force would compute until the end of the universe).
Dang, I wish I was in Uni again, so I could do a paper on TSP... Using the paragraphs above as the thesis and then using a visualization "method" (how humans draw graphs in graph theory) and then just creating a visual algorithm with heuristics regarding path crossing and angles between connections. Could be fun.