The Traveling Salesman Problem

The TSP is simply stated: - You have a collection of points. - What is the shortest route to visit all of them?

The name derives from the scenario of a salesperson seeking to minimize travel distances between cities.

In trivial cases, such as two points, the shortest route is a straight line connecting them. With three points, it’s evident that straight segments are still optimal (a little exercise for the reader: why?), and one can easily check all arrangements to find the shortest one.

While the historical context and complexity of the problem are rich, numerous articles delve into these aspects well, such as:

• Why The Travelling Salesman Problem Matters

  Discover a concise explanation of this challenging computer science problem in just three minutes.

The crux of the issue is its difficulty. The TSP is classified as NP-complete, indicating that no algorithm can resolve it quickly—a term that requires more detailed exploration than this article can provide.

Infinite Sets

Given that the traditional TSP has been a subject of study for over a century, one might presume that transitioning to an infinite set of points would be hopeless. However, it turns out this variation can be essentially addressed! The following sections will clarify what this entails.

To illustrate that generalization is feasible, consider an infinite collection of points located along the line segment from (0,0) to (1,0). Whether you contemplate all points (which are uncountably infinite) or any subset, the segment itself encompasses them all, retaining a length of 1. This might seem like a loophole, yet it forms the basis for generalizing the problem.

Two key questions arise regarding any bounded set ( E ) in ( mathbb{R}^2 ): - Is there a finite-length (rectifiable) curve that includes every point of ( E )? - If such a curve exists, what is the shortest path?

The first question essentially revolves around classification: which sets allow for the discovery of a shortest path?

Rephrased mathematically, can we formulate necessary and sufficient conditions based on the properties of the set to determine if a finite-length curve can traverse every point?

The second question pertains to "solving" the TSP for these sets, meaning we need to actually compute the shortest distance.

At this stage, we make few assumptions about set ( E ); it could even be a complex fractal.

Some Preliminary Examples

Numerous examples illustrate the need for stricter criteria. For instance, consider a filled square. While there are peculiar "space-filling curves" that touch every point, they lack finite length.

The positive area of the square disqualifies it as a viable set. This leads us to an initial criterion: we will focus only on sets with a dimension of at most 1.

Let’s construct the four-corner Cantor set (previously mentioned in my last article).

Starting with a square, divide it into a 4x4 grid and remove all but the four corner squares. Repeating this process with the remaining squares leads to a limit where the resulting set maintains a Hausdorff dimension of 1, classifying it as a purely unrectifiable set.

The generation of corners throughout the process complicates the definition of tangents. If a rectifiable curve were to pass through all points, the set itself would need to be rectifiable.

These conditions on ( E ) are necessary, but they do not resolve the problem. Moreover, the Hausdorff dimension can be misleading, as there exist 0-dimensional sets for which the problem remains unsolved!

Flatness When Zoomed In

Our goal is to establish a metric that quantifies how “non-flat” a set appears at various magnifications.

Initially, consider the simplest sets. A finite-length differentiable curve will directly resolve the TSP for that set. Such curves exhibit the desirable property of being flat (with tangent lines) upon close inspection.

However, flatness is not a prerequisite. A curve may exhibit infinite jaggedness yet still provide a solution to the problem. Imagine a scenario where jagged features emerge infinitely but converge in a specific manner.

If this concept resonates with you, you are nearing the definition necessary for solving the problem in a general context.

Beta Numbers

What signifies that a set is not flat? When analyzing a segment of the set, any line traversing that section will reveal distant points.

For example, let ( E ) be an actual line (the black one), and focus on a portion of it contained within a box. Consider every possible line through this area (only two red lines are illustrated, but there are infinitely more).

Our set/black line is indeed flat. However, the selected red lines may still highlight distant points; the issue arises from poorly chosen lines for flatness testing. As we refine our line selection, the number of distant points approaches 0.

When we align one of the lines precisely with the black line, all points are at a distance of 0.

This notion leads us to the beta number of ( E ) concerning square ( Q ). By evaluating all lines through square ( Q ), one will identify the line that minimizes the distance from ( E ).

We normalize the minimum distance by dividing it by the side length of ( Q ) to accommodate zoom levels.

Before formalizing this concept, let’s deepen our understanding. This measure indeed reflects flatness; a larger beta signifies a more pronounced lack of flatness.

For a straight line, the beta equals 0.

In the case of a tangent line, the numerator of beta represents the "error" in using the tangent line as an approximation for the curve. A foundational principle of calculus states that this error diminishes as we zoom in.

Consequently, beta approaches 0 in the limit when using tangent lines (denoting flatness).

Error Terms

Let’s condense the preceding discussion into a more succinct format for future reference.

The beta number of a set ( E ) on square ( Q ) involves identifying the line that best approximates ( E ) and determining the worst "error" of this approximation, normalized by the side length of ( Q ).

The formal definition may be more complex due to the absence of a clear best-fitting line or exact worst error. Thus, we consider the infimum over the set of all such lines.

From this point forward, we will refer to these as error terms, denoted by ( e ). The side length of square ( Q ) is represented as ( l(Q) ).

Thus, we establish ( phi(Q) = e(Q) / l(Q) ).

The Fundamental Concept

If all of this feels overwhelming, let’s pause to clarify why any of this relates to the Traveling Salesman Problem.

First fundamental concept: Beta is close to 0 on ( Q ) when the set is flat and approximately 1 when it is not flat. This relationship may not be immediately apparent, but it connects to our division by ( l(Q) ) in the definition of ( phi ).

Second fundamental concept: The Pythagorean Theorem is an underlying principle that supports this framework.

Consider a scenario where the set ( E ) consists of three points ( A, B, ) and ( C ) that are nearly flat.

The optimal line is the one connecting ( A ) and ( C ), while the error is represented by ( e ), the length of the perpendicular dropped from ( B ).

The goal is to minimize the path from ( A ) to ( C ), but we must detour to include ( B ). The question arises: how much additional length does this detour introduce?

By definition, the excess length is ( a + b - (c + d) ). Rearranging gives ( (a - c) + (b - d) ).

From the Pythagorean Theorem, we know ( a^2 = c^2 + e^2 ). Rearranging leads to:

( a^2 - c^2 = e^2 )

Factoring gives:

( (a - c)(a + c) = e^2 )

Thus:

( (a - c) = e^2 / (a + c) )

Assuming relative flatness implies ( phi ) is small, hence ( a ) and ( c ) are closely sized. This allows us to approximate:

( (a - c) sim e^2 / (2c) )

Likewise, similar calculations yield ( (b - d) sim e^2 / (2d) ). If ( B ) is centrally located, then ( 2c sim 2d sim (c + d) ).

This suggests the detour adds approximately ( e^2 / (c + d) ). If we employ a square ( Q ) minimized to encapsulate the three points, its side length ( l(Q) ) equals ( c + d ), which becomes our denominator.

In notation, the detour contributes a length of ( e(Q)^2 / l(Q) ) or, in beta terms, ( phi(Q) cdot l(Q) ).

More sophisticated methods exist for tracking error terms without numerous assumptions, yet you should now appreciate how these metrics relate to the straight-line solution for the Traveling Salesman Problem.

P.S. For greater precision, if you’re versed in calculus, consider applying the square root at the Pythagorean Theorem step and utilize Taylor’s approximation. You’ll find a similar outcome, albeit with rigor.

Dyadic Squares

As we proceed, you may see the direction this is taking. Let’s expedite to the conclusion to maintain engagement.

If ( E ) is simply a flat line, we can traverse seamlessly from one end to the other. In the previous section, we noted that the detour length was approximately ( e(Q)^2 / l(Q) ).

We may hypothesize that if the aggregate of all detours is finite, then we can indeed resolve the TSP for ( E ) (discovering a finite-length rectifiable curve that covers all points in ( E )), and this hypothesis is accurate!

To achieve this, we need a systematic way to partition ( mathbb{R}^2 ) into squares. The ingenious method involves using dyadic squares—squares with side lengths of ( 2^n ), where ( n ) can be any integer, with the corner located at (0,0).

For any bounded ( E ), consider the following facts: - There exists a singular dyadic square with a side length of ( 2^n ) that encompasses the entire set for sufficiently large ( n ) (this aligns with the definition of boundedness). Beyond this, the error term remains consistent. - When we analyze all dyadic squares, we obtain increasingly smaller squares that encapsulate the concept of zooming in to assess flatness.

The Analyst Traveling Salesman Theorem

The Analyst Traveling Salesman Theorem for ( mathbb{R}^2 ) was established by Peter Jones in 1990, published in a leading mathematics journal, underscoring its significance.

Theorem: For a bounded set ( E ), a finite length (rectifiable) curve exists through ( E ) if and only if ( sum Q left( phi(3Q)^2 / l(Q) right) ) is finite (where the summation encompasses all dyadic squares intersecting ( E )).

Essentially, the TSP can be resolved for ( E ) if the cumulative detours caused by its non-flatness can be aggregated across all zoom levels to yield a finite additional length.

There are nuances omitted here for clarity, such as the rationale behind the appearance of ( 3Q ) and the specifics of the summation which may diverge from those noted on Wikipedia.

While the summation extends infinitely, the larger squares converge (the error is constant, though the side lengths are ( 2^n ), and calculus assures that ( sum (1/2^n) ) converges).

This indicates that only the smaller squares hold significance, as they evaluate how "non-flat" the set is or, equivalently, how problematic the detours will be.

This revelation is remarkable! It offers a singular numerical criterion to ascertain the solvability of the TSP for complex, potentially fractal sets. This criterion provides both necessary and sufficient conditions for resolution.

We suspected that well-behaved sets with tangents would yield solutions, and that summation will converge in those cases (though it is trickier than it appears—try computing it for the unit circle, which is a challenging yet feasible exercise).

Interestingly, many non-locally flat structures also possess finite-length curves as long as the beta number/error term behaves appropriately within the summation.

Jones proved further results related to the length of the curve that resolves the problem, but that falls outside the scope of this discussion.

Thus, we conclude that this classical, intricate problem has indeed been addressed within this broader framework!