Travelling Salesperson Problem Lecture Notes

Vocabulary flashcards covering key terms, algorithms, and concepts from the lecture on the Travelling Salesperson Problem.

Travelling Salesperson Problem (TSP)

An optimisation problem that seeks the shortest possible tour that visits each of n cities exactly once and returns to the starting city.

NP-Hard

A class of problems for which no known algorithm can guarantee a polynomial-time solution; the TSP belongs to this class.

Tour

A complete cycle that starts at one city, visits every other city exactly once, and returns to the starting city.

Permutation Representation

Encoding a TSP tour as an ordered list of the integers 1…n, each appearing exactly once.

Search Space of TSP

All n! possible permutations (tours) of n cities; grows factorially with n.

Distance Notation d(i,j)

Symbol representing the distance between city i and city j, with d(i,j)=d(j,i) and d(i,i)=0.

Distance Matrix D

An n×n matrix where entry dij equals d(i,j), used to store all pairwise city distances.

Euclidean Distance

The straight-line distance between two points (xi,yi) and (xj,yj), computed as sqrt((xi−xj)^2+(yi−yj)^2).

Fitness Function f(T)

The total length of a tour T, calculated by summing distances between consecutive cities and returning to the start; objective is to minimise f(T).

Random Permutation (RandPerm)

Algorithm that constructs a random TSP tour by repeatedly selecting and removing random elements from a list of remaining cities.

Swap Operator

A small-change operator that exchanges two randomly chosen cities in a tour to produce a neighbouring solution.

Random-Mutation Hill Climbing (RMHC)

A heuristic search method that iteratively applies small changes (e.g., Swap) and accepts improvements to minimise tour length.

Simulated Annealing

A heuristic search technique that probabilistically accepts worse solutions early on to escape local optima; often applied to the TSP.

Minimum Spanning Tree (MST)

A spanning tree of minimum possible total edge weight that connects all nodes of a graph without cycles.

MST Lower Bound

The property that the length of any TSP tour is at least the cost of the corresponding MST: f(TSP) ≥ MST(D).

Efficiency Measure

A ratio used to evaluate solution quality: (MST(D) / f(TSP(D))) × 100%, always ≤ 100%.

Vehicle Routing

A practical application of the TSP where optimal routes for delivery or service vehicles are determined.

Heuristic Search

Approach that uses approximate methods (e.g., Hill Climbing, Simulated Annealing) to find good—but not necessarily optimal—TSP solutions in reasonable time.