Friday, January 09, 2026
the shortest route visiting all US states
I think this is the classic problem, which basically cannot be proved in that there are too many possible routes to test out. Thus it is easy to see that all you have to do is list the finite number of possible combinations, and you then find the smallest one, but the list is incredibly long.
It seems that quantum computers are almost ready to do this counting in some ridiculously short time. I guess this will happen in the next ten years. Twenty if you want to be conservative.
I guess you don't have to be ultra accurate about the positions, but you would need to investigate the second shortest route to check the sensitivity of the results, and then check if further accuracy is needed.
This general problem of sorting objects to get the shortest distances is what my PhD was about, and instead of struggling at the hundred object level, would be trivially solved with the quantum computers shortly to emerge.
M
M
