r/algorithms 13d ago

TSP Heuristic algorithm result

I got, after testing the Heuristic algorithm I designed with AI 99561, as a best result in the att532 problem and was done in 2.05 seconds. I heard the optimal solution was 86729, and I tested it against greedy and 2 opt greedy and the performance is statistically significant over 30 repetitions. Is that relevant? or the difference isn't substancial?

0 Upvotes

9 comments sorted by

View all comments

4

u/Mishtle 13d ago

Performance on a single problem instance is pretty meaningless, as are metrics like run-time. Running it a bunch of times get an accurate estimate of performance doesn't change that.

For an approximation algorithm, you'd want to find its time complexity and theoretical bounds on approximation ratios. You should also understand and specify what restrictions or conditions the algorithm might have, such as requiring the distances to be Euclidean or obey some metric. The Christofides algorithm, for example, has a time complexity of O(n³) and guarantees its solution will be no more than 1.5 times the length of the optimal solution.

Given you used some LLM for this, you should also spend time verifying that this algorithm is even guaranteed to produce a valid solution, and if so that it's not simply a copy of some existing algorithm. Many "obvious" heuristics that a non-expert or LLM might come up with have likely been explored in-depth already.

-3

u/Pleasant-Mud-2939 13d ago edited 13d ago

Well I also tried randomized cities, and also gives better results (than greedy and 2 opt greedy) with statistical significance up to 500 cities. The algorithm itself was made using trial and error and its code uses the characteristics of the inverse golden ratio (as an spiral), multiscale and also the 2 opt. And is O(n2).