How does the classical travelling salesman problem differ from the practical version?

Classical TSP requires each non-start vertex to be visited exactly once before returning to the start. Practical TSP only requires each vertex to be visited at least once, so repeats may occur. This difference determines whether you can work directly with Hamiltonian cycles or need preprocessing like a least-distance table.

What is the difference between a general tour and a Hamiltonian cycle in routing networks?

A tour is any closed walk that returns to the starting vertex and may repeat vertices or edges. A Hamiltonian cycle is stricter because it visits each vertex exactly once apart from the repeated start/end. TSP methods targeting exact classical solutions rely on the Hamiltonian condition.

How does nearest neighbour differ from Prim's algorithm when solving TSP-related tasks?

Nearest neighbour chooses the nearest unvisited vertex from the current position, producing a cycle candidate. Prim's algorithm grows a minimum spanning tree by choosing the smallest connecting edge from any visited vertex frontier. The first gives an upper-bound tour, while the second supports bound construction rather than a Hamiltonian cycle directly.

What goes wrong if you use direct edge lengths instead of true shortest-path distances in a least-distance table?

You can overestimate pairwise travel costs and distort the complete-network model used for TSP analysis. That breaks the assumptions behind comparing candidate cycles and computing meaningful bounds. As a result, a route may appear suboptimal or optimal for the wrong numerical reasons.

Why is it an error to claim a nearest-neighbour cycle is automatically optimal?

Nearest neighbour is greedy and only optimizes each local move, not the entire route structure. A locally short edge can force an expensive final closure or block better later choices. Therefore it provides a feasible upper bound, not a proof of global optimality.

What common mistake occurs when students mix up tree methods and cycle methods?

Students sometimes present an MST as if it were a valid TSP tour, but trees do not form a single closed Hamiltonian cycle. This confuses a bounding structure with a feasible salesman route. Always verify the output has exactly one cycle visiting all required vertices and returning to start.

What does the optimization expression $\min \sum c_{ij}x_{ij}$ represent in TSP?

It represents minimizing total travel cost across selected edges in the route. Here $c_{ij}$ is the weight between vertices $i$ and $j$, and $x_{ij}$ indicates whether that edge is included. The expression captures the objective but must be paired with route-feasibility constraints.

What is the key bound relationship used in TSP reasoning?

The core inequality is lower bound <= optimal tour <= upper bound. A lower bound proves no valid tour can be cheaper, while an upper bound is the cost of a known feasible tour. This interval guides search quality and can certify optimality when both ends coincide.

Why is the triangle inequality important in many TSP methods?

Triangle inequality ensures indirect detours are never better than a direct shortest distance between two vertices in the metric model. This supports shortcutting repeated paths when improving upper bounds and stabilizes greedy heuristics. Without it, some common approximation intuitions become unreliable.

Why does TSP become hard as the number of vertices grows?

The number of possible Hamiltonian cycles grows factorially with vertex count, so exhaustive checking quickly becomes infeasible. Even moderate-size instances can have too many candidates to test directly. That is why bounding and heuristics are central in practical workflows.

The Travelling Salesman Problem | Pearson Edexcel International A-Level Maths

Q: Why is the triangle inequality important in many TSP methods?

Triangle inequality ensures indirect detours are never better than a direct shortest distance between two vertices in the metric model. This supports shortcutting repeated paths when improving upper bounds and stabilizes greedy heuristics. Without it, some common approximation intuitions become unreliable.

Q: Why does TSP become hard as the number of vertices grows?

The number of possible Hamiltonian cycles grows factorially with vertex count, so exhaustive checking quickly becomes infeasible. Even moderate-size instances can have too many candidates to test directly. That is why bounding and heuristics are central in practical workflows.

1. Definition & Core Concepts

Travelling Salesman Problem (TSP): TSP is the task of finding a closed route of least total weight in a weighted network while visiting required vertices. In the classical form, each non-start vertex is visited exactly once, so the route is a Hamiltonian cycle. In the practical form, vertices may be revisited, but all required vertices must be visited at least once before returning to the start.
Tour vs Hamiltonian cycle: A tour is any closed walk that returns to its starting vertex, so it may repeat vertices or edges. A Hamiltonian cycle is stricter because it visits each vertex exactly once (except the start/end repetition). This distinction matters because many TSP methods target Hamiltonian cycles in complete graphs.
Least-distance table as model transformation: A least-distance table stores the shortest path between every pair of vertices, not just direct edges. This transforms a sparse practical network into a complete weighted network where Hamiltonian-cycle methods can be applied. The transformation is valid when each entry truly represents the minimum available path cost.

A weighted network with a highlighted Hamiltonian cycle representing a candidate travelling salesman tour.

2. Underlying Principles

Optimization objective: The TSP objective is to minimize total route weight, often written as the sum of chosen edge weights. A common expression is $\min \sum c_{ij}x_{ij}$ , where $c_{ij}$ is travel cost and $x_{ij}\in\{0,1\}$ indicates whether edge $(i,j)$ is used. This formal view clarifies that the problem is about global route structure, not local shortest moves.
Triangle inequality and metric structure: If the network satisfies $d(i,k) \le d(i,j)+d(j,k)$ for all vertices, direct movement is never worse than detouring through an intermediate vertex. This property justifies shortcutting repeated paths when building upper bounds and supports nearest-neighbour reasoning on complete metric graphs. It also underpins least-distance tables because shortest-path distances naturally satisfy this inequality.
Bounding logic: For TSP, useful reasoning often starts with $\text{Lower bound} \le \text{Optimal tour} \le \text{Upper bound}.$ A lower bound proves no feasible tour can be cheaper than a threshold, and an upper bound comes from any concrete feasible tour. When both match, optimality is certified without checking every Hamiltonian cycle.

3. Methods & Techniques

Constructing a least-distance table: Build a matrix of shortest pairwise distances, place dashes on the diagonal, and enforce symmetry for undirected networks. For each vertex pair, confirm whether a direct edge or an indirect path is shorter, then record the minimum value. This turns an incomplete practical network into a complete one suitable for classical TSP techniques.
Upper bound from minimum spanning tree (MST): Find an MST using Prim's or Kruskal's algorithm, then double its weight to get an initial feasible closed walk upper bound. Replacing repeated segments with valid shortcuts can reduce this value while preserving feasibility. This method is strong when structure is sparse but edge weights satisfy metric behavior.
Lower bound via deleted-vertex method: Remove one vertex, compute a residual MST on the remaining vertices, then add the two smallest edges reconnecting the deleted vertex. The result is a valid lower bound because any Hamiltonian cycle must connect each vertex with degree two. Repeating for different deleted vertices and taking the maximum gives a tighter bound.
Nearest neighbour heuristic: Start from a chosen vertex and repeatedly move to the nearest unvisited vertex until all are visited, then return to start. The produced Hamiltonian cycle gives an upper bound, but not necessarily the optimum because greedy local choices can block better global routes. Running from multiple starting vertices usually improves the best-found bound.

4. Key Distinctions

Core Comparisons

Method-selection table: Choose the method by problem representation and goal, not by habit. Prim and Kruskal optimize a tree structure, while nearest neighbour directly constructs a cycle. TSP solving by full enumeration is exact but only practical on small complete graphs.

Feature	Classical TSP	Practical TSP
Visit rule	Each vertex once	Each vertex at least once
Typical graph use	Complete graph	Often incomplete graph
Common preprocessing	Usually none	Build least-distance table

Feature	Prim/Kruskal (MST)	Nearest Neighbour
Output	Tree (no cycle)	Hamiltonian cycle
Main use in TSP	Bounds construction	Feasible upper bound
Guarantee	Minimum tree weight	No optimality guarantee

Tour quality vs proof of optimality: A short route is not automatically optimal unless it matches a proven lower bound or is established by exhaustive exact search. Bounding methods separate "good candidate" from "mathematically certified best." This distinction is central in exam reasoning and in real optimization workflows.
Complete vs incomplete network reasoning: Hamiltonian-cycle enumeration assumes every required pair connection is available as an edge in the working model. In incomplete practical networks, least-distance completion embeds multi-edge travel into single effective distances so classical reasoning can proceed. Without this step, feasible cycle comparisons can be invalid or inconsistent.

5. Exam Strategy & Tips

Choose the correct framework first: Identify whether the question asks for an exact optimum, an upper bound, a lower bound, or a heuristic cycle. This prevents using Prim's algorithm when a Hamiltonian cycle is required, or using nearest neighbour when a tree-based bound is requested. Most lost marks come from selecting the wrong method before any arithmetic begins.
Track constraints explicitly: Keep a clear visited/unvisited record, enforce return to start, and avoid revisiting vertices in classical TSP unless the method temporarily allows it for a bound. Write edge choices in order and keep a running total to catch arithmetic drift. A disciplined ledger makes final checks much faster and more reliable.
Use symmetry and sanity checks: In undirected distance tables, verify $d(i,j)=d(j,i)$ and diagonal cells are excluded. If a shortcut violates triangle inequality intuition, recheck the route logic because a supposed improvement may be infeasible. Always compare your final cycle weight against known bounds to validate reasonableness.
Memorize certifying statements: A powerful exam conclusion is that a feasible route equal to the lower bound is optimal.

Key certification rule: if a valid tour has weight $W$ and a proven lower bound is also $W$ , then $W$ is the optimal TSP value. This concise statement often earns method and reasoning marks together.

6. Common Pitfalls & Misconceptions

Confusing nearest neighbour with Prim's algorithm: Both use local minimum edges, but nearest neighbour grows a path from the current vertex while Prim grows a tree from any visited vertex frontier. Mixing them leads to structurally invalid outputs for the requested task. Always state the object you are constructing: tree or Hamiltonian cycle.
Assuming every greedy cycle is optimal: A greedy choice can be locally best yet globally poor because it may force expensive closing edges later. This is why nearest neighbour yields an upper bound, not a proof. Treat greedy output as a candidate to compare, not a final certificate.
Using non-shortest pair distances in completion tables: If a table entry is not the true shortest path, subsequent TSP reasoning can overestimate or distort feasible cycle weights. The least-distance table must represent genuine shortest pairwise travel costs. Otherwise, both bound calculations and cycle comparisons become unreliable.

The Travelling Salesman Problem

Summary

1. Definition & Core Concepts

2. Underlying Principles

3. Methods & Techniques

4. Key Distinctions

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

The Travelling Salesman Problem

Summary

1. Definition & Core Concepts

2. Underlying Principles

3. Methods & Techniques

4. Key Distinctions

Core Comparisons

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

Core Comparisons