-1
$\begingroup$

I'm not sure if this is something new or if I'm just not getting previous efforts. TSP can be thought of as a list of weighted links and nodes. If one takes the Nearest Neighbor (NN) of every node and adds them all up, that is a theoretical minimum. It's not a solution, but any solution can't be less than that. It will produce n/2 pairs of unconnected cycles. Label all of the nodes in the cycle with the cycle's label. Next, connect the nearest adjacent cycle. Relabel the cycles. When the cycle count reaches 1, you have a solution. It's probably not optimal, but it might be better than NN. Just thought I'd ask. Any help is appreciated. I did try to look it up, but all the solutions looked top down to me, so hopefully, I haven't wasted everyone's time.

Response,

Thanks for the responses, they've been very helpful. This truly is a question and not a proposal masquerading as one, so the answer to many of your questions is, I don't know.

Your example struck me as odd for something on a plane, but a simple circle with r=1 radian demonstrates it. It comes down to 1r vs 1.23 approx.

My thinking was using something like a parallel merge sort. I think of NN more like a sequential bubble sort. So the goal is to create small cycles and then merge them into larger ones. In cases of ties, instead of going to the runner, they go to the node with the fewest good options. Each node could be represented as a table with all it's links sorted by weight. Each link would also have a cycle ID associated with it. This was more like a component labeling problem from imagine processing. Once a link is in the same cycle, they would be deactivated. The goal here is to try to decrease the run time to log2(n) but more likely log2(n)*log2(n). It's the type of problem that should, in theory, run well on SIMD grid of processors, although I suspect they will need local memory decode. It would also require some sort of higher level routing, in days gone by a hypercube or butterfly switch was used. Decades ago I did some research on a pyramid topology system for component labeling and saw some improvement. A single spiral was the worse case, which was < log2(n)*log2(n) if memory serves.

$\endgroup$
3
  • 1
    $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Oct 11, 2023 at 16:47
  • 1
    $\begingroup$ A similar way is to find a min-weight disjoint (vertex) cycle cover (en.wikipedia.org/wiki/Vertex_cycle_cover), contract each cycle in it, and recurse on the contracted graph. (Finding the min-wt cover is poly-time by reduction to min-weight bipartite matching.) Each step at least halves the number of vertices, so there are at most $\log n$ steps. The cost of the cover at each step is a lower-bound on OPT, so the total cost of the resulting edges (which connect the graph) is at most $\log(n)\times$ OPT. In a metric graph shortcutting the edges gives a tour. There are better algs. $\endgroup$
    – Neal Young
    Oct 15, 2023 at 16:43
  • $\begingroup$ Ah if your goal is to devise a heuristic that will run well on SIMD processors, then your ideas very well might lead to such an algorithm. I think it could be interesting to implement such an algorithm, run it on a database of standardized tsp instances, and see how it stacks up to other methods. However, as @NealYoung mentioned your algorithm is likely to not be as good as existing algorithms in the ways that theoretical computer scientists care about. The simple 2-approximation based on the minimum spanning tree already has a run time of $O(n\log n)$. $\endgroup$ Oct 15, 2023 at 22:15

2 Answers 2

1
$\begingroup$

"If one takes the 2 nearest neighbors of every node and adds them all up, that is a theoretical minimum." This isn't true. You are adding up 2 edges per vertex, where a TSP solution has one edge per vertex. Unless I am misunderstanding what you mean.

However, nearest-neighbor is a classic heuristic for TSP. Arbitrarily pick a vertex to start, connect it to its nearest neighbor. Connect that vertex to its nearest neighbor that hasn't yet been connected. However, the length of a tour returned by this heuristic can be arbitrarily bigger than the optimal length.

You could modify this heuristic so it connects a vertex to its nearest neighbor, even if it has already been found, and that could be the starting point of your "bottom up solution". However, I still don't think this will necessarily be a lower bound of the optimal solution (or at least it isn't obvious to me that it would be).

Finally, you say, "it might be better than NN." What is "NN"? Also are you interested in solving the problem in theory or practice? Because in practice TSP can be solved to optimality relative quickly using integer programming techniques.

$\endgroup$
0
$\begingroup$

I noticed you made an edit to your question so I now better understand your proposed algorithm. My misunderstanding was large enough that I think it makes more sense to post a new answer.

First, I have a question. What do you mean by "n/2 pairs of unconnected cycles"? My interpretation was "n/2 disconnected cycles of length 2". If my interpretation is correct, I think you've made a small mistake in reasoning though. One vertex could be the nearest neighbour for several vertices. For example if you have 6 vertices, one at the origin and the other 5 evenly spaced on the unit disk, then the vertex at the origin is the nearest neighbour for each of the other 5.

Also, when connecting cycles to their nearest neighbour cycles, you need to describe what procedure you would be using to do that. I assume you are measuring the distance between two cycles $C_1$ and $C_2$ as the minimum distance between a vertex $v_1 \in C_1$ and a vertex $v_2 \in C_2$. Let us say that $C_1$'s nearest neighbour is $C_2$ and the vertices $v_1 \in C_1$ and $v_2 \in C_2$ are the closest vertices. Given this info, how do you connect $C_1$ and $C_2$ to get a new cycle?

To answer the high-level question of why no one has studied a "bottom up" approach to TSP we should first make sure we mean the same thing by "bottom up". I thought you meant a method where we make locally optimal decisions for each vertex, and mentioned that such methods have been studied. I specifically mentioned the Nearest-Neighbour Heuristic, which has been very extensively studied, but there are others as well. If that isn't what you mean, could you please clarify?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.