The Travelling Salesman Problem (TSP) is a classic optimization challenge that has intrigued researchers and professionals alike for decades. It involves finding the shortest possible route that visits a given set of cities and returns to the original city. This problem is NP-hard, making it a tough nut to crack as the number of cities grows. In this detailed guide, we will explore various methods to solve the TSP using the C programming language, known for its efficiency and control over system resources.
1. Introduction to the Travelling Salesman Problem
The Travelling Salesman Problem (TSP) asks: given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? This problem is highly relevant in fields such as logistics, manufacturing, and genetics, where optimal routing is crucial.
2. Exact Algorithms
Brute Force Method
The brute force approach to solving TSP involves generating all possible permutations of the cities and calculating the total distance for each permutation. The shortest route among all permutations is the solution. While this method guarantees finding the optimal solution, its time complexity is (O(n!)), making it impractical for large datasets.
Implementation in C
#include <stdio.h>
#include <limits.h>
#define N 4 // Number of cities
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int minPath(int path[], int dist) {
int sum = 0;
for (int i = 0; i < N - 1; i++) {
sum += graph[path[i]][path[i + 1]];
}
sum += graph[path[N - 1]][path[0]];
return sum;
}
void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}
void permute(int *a, int l, int r, int *minDist) {
if (l == r) {
int dist = minPath(a, N);
if (dist < *minDist) {
*minDist = dist;
}
} else {
for (int i = l; i <= r; i++) {
swap((a + l), (a + i));
permute(a, l + 1, r, minDist);
swap((a + l), (a + i)); // backtrack
}
}
}
int main() {
int cities[N] = {0, 1, 2, 3};
int minDist = INT_MAX;
permute(cities, 0, N - 1, &minDist);
printf("The minimum distance is %d\n", minDist);
return 0;
}Dynamic Programming
The dynamic programming approach to TSP, specifically the Held-Karp algorithm, uses memoization to store intermediate results, reducing redundant calculations. Its time complexity is (O(n^2 \cdot 2^n)), which is significantly better than the brute force method.
Implementation in C
#include <stdio.h>
#include <limits.h>
#define N 4
#define VISITED_ALL ((1 << N) - 1)
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int dp[1 << N][N];
int tsp(int mask, int pos) {
if (mask == VISITED_ALL) return graph[pos][0];
if (dp[mask][pos] != -1) return dp[mask][pos];
int minDist = INT_MAX;
for (int city = 0; city < N; city++) {
if ((mask & (1 << city)) == 0) {
int newDist = graph[pos][city] + tsp(mask | (1 << city), city);
if (newDist < minDist) {
minDist = newDist;
}
}
}
return dp[mask][pos] = minDist;
}
int main() {
for (int i = 0; i < (1 << N); i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
int minCost = tsp(1, 0);
printf("The minimum distance using DP is %d\n", minCost);
return 0;
}3. Approximation Algorithms
Nearest Neighbor Algorithm
The nearest neighbor algorithm is a simple heuristic that starts from an arbitrary city and repeatedly visits the nearest unvisited city until all cities have been visited. While it does not guarantee the optimal solution, it provides a reasonably good approximation in a relatively short time.
Implementation in C
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define N 4
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
void tspNearestNeighbor() {
bool visited[N] = {false};
int path[N + 1];
int minDistance = 0;
int currentCity = 0;
visited[currentCity] = true;
path[0] = currentCity;
for (int i = 1; i < N; i++) {
int nearestCity = -1;
int minDist = INT_MAX;
for (int city = 0; city < N; city++) {
if (!visited[city] && graph[currentCity][city] < minDist) {
nearestCity = city;
minDist = graph[currentCity][city];
}
}
visited[nearestCity] = true;
path[i] = nearestCity;
minDistance += minDist;
currentCity = nearestCity;
}
minDistance += graph[currentCity][0];
path[N] = 0;
printf("Path using Nearest Neighbor: ");
for (int i = 0; i <= N; i++) {
printf("%d ", path[i]);
}
printf("\nMinimum distance: %d\n", minDistance);
}
int main() {
tspNearestNeighbor();
return 0;
}Genetic Algorithm
A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. It uses techniques such as selection, crossover, and mutation to evolve a population of candidate solutions toward better solutions over generations.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define N 4
#define POP_SIZE 10
#define MUTATION_RATE 0.1
#define GENERATIONS 100
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
typedef struct {
int path[N];
int fitness;
} Individual;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int calculateDistance(int *path) {
int distance = 0;
for (int i = 0; i < N - 1; i++) {
distance += graph[path[i]][path[i + 1]];
}
distance += graph[path[N - 1]][path[0]];
return distance;
}
void initializePopulation(Individual *population) {
for (int i = 0; i < POP_SIZE; i++) {
for (int j = 0; j < N; j++) {
population[i].path[j] = j;
}
for (int j = 0; j < N; j++) {
int r = rand() % N;
swap(&population[i].path[j], &population[i].path[r]);
}
population[i].fitness = calculateDistance(population[i].path);
}
}
int compareIndividuals(const void *a, const void *b) {
return ((Individual *)a)->fitness - ((Individual *)b)->fitness;
}
void selectParents(Individual *population, Individual *parent1, Individual *parent2) {
qsort(population, POP_SIZE, sizeof(Individual), compareIndividuals);
*parent1 = population[0];
*parent2 = population[1];
}
void crossover(Individual *parent1, Individual *parent2, Individual
*child) {
int start = rand() % N;
int end = start + rand() % (N - start);
bool visited[N] = {false};
for (int i = start; i <= end; i++) {
child->path[i] = parent1->path[i];
visited[child->path[i]] = true;
}
int currentIndex = 0;
for (int i = 0; i < N; i++) {
if (!visited[parent2->path[i]]) {
while (currentIndex >= start && currentIndex <= end) {
currentIndex++;
}
child->path[currentIndex++] = parent2->path[i];
}
}
child->fitness = calculateDistance(child->path);
}
void mutate(Individual *individual) {
if ((rand() / (double)RAND_MAX) < MUTATION_RATE) {
int index1 = rand() % N;
int index2 = rand() % N;
swap(&individual->path[index1], &individual->path[index2]);
individual->fitness = calculateDistance(individual->path);
}
}
void geneticAlgorithm() {
Individual population[POP_SIZE];
initializePopulation(population);
for (int generation = 0; generation < GENERATIONS; generation++) {
Individual parent1, parent2;
selectParents(population, &parent1, &parent2);
Individual newPopulation[POP_SIZE];
newPopulation[0] = parent1;
newPopulation[1] = parent2;
for (int i = 2; i < POP_SIZE; i++) {
Individual child;
crossover(&parent1, &parent2, &child);
mutate(&child);
newPopulation[i] = child;
}
for (int i = 0; i < POP_SIZE; i++) {
population[i] = newPopulation[i];
}
}
Individual bestIndividual = population[0];
for (int i = 1; i < POP_SIZE; i++) {
if (population[i].fitness < bestIndividual.fitness) {
bestIndividual = population[i];
}
}
printf("Best path using Genetic Algorithm: ");
for (int i = 0; i < N; i++) {
printf("%d ", bestIndividual.path[i]);
}
printf("\nMinimum distance: %d\n", bestIndividual.fitness);
}
int main() {
srand(time(0));
geneticAlgorithm();
return 0;
}4. Heuristic Methods
Simulated Annealing
Simulated annealing is a probabilistic technique for approximating the global optimum of a given function. It is inspired by the annealing process in metallurgy.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define N 4
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
int calculateDistance(int *path) {
int distance = 0;
for (int i = 0; i < N - 1; i++) {
distance += graph[path[i]][path[i + 1]];
}
distance += graph[path[N - 1]][path[0]];
return distance;
}
double probability(int oldCost, int newCost, double temperature) {
if (newCost < oldCost) return 1.0;
return exp((oldCost - newCost) / temperature);
}
void simulatedAnnealing() {
int currentPath[N];
for (int i = 0; i < N; i++) currentPath[i] = i;
int currentDistance = calculateDistance(currentPath);
int bestDistance = currentDistance;
int bestPath[N];
memcpy(bestPath, currentPath, sizeof(currentPath));
double temperature = 10000.0;
double coolingRate = 0.999;
srand(time(0));
while (temperature > 1.0) {
int newPath[N];
memcpy(newPath, currentPath, sizeof(currentPath));
int i = rand() % N;
int j = rand() % N;
int temp = newPath[i];
newPath[i] = newPath[j];
newPath[j] = temp;
int newDistance = calculateDistance(newPath);
if (probability(currentDistance, newDistance, temperature) > (rand() / (double)RAND_MAX)) {
memcpy(currentPath, newPath, sizeof(newPath));
currentDistance = newDistance;
}
if (currentDistance < bestDistance) {
bestDistance = currentDistance;
memcpy(bestPath, currentPath, sizeof(currentPath));
}
temperature *= coolingRate;
}
printf("Best path using Simulated Annealing: ");
for (int i = 0; i < N; i++) {
printf("%d ", bestPath[i]);
}
printf("\nMinimum distance: %d\n", bestDistance);
}
int main() {
simulatedAnnealing();
return 0;
}Ant Colony Optimization
Ant Colony Optimization (ACO) is inspired by the behavior of ants finding paths to food sources. It uses pheromones to build solutions incrementally and favors solutions that have worked well in the past.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#define N 4
#define NUM_ANTS 10
#define MAX_ITER 100
#define ALPHA 1.0
#define BETA 5.0
#define EVAPORATION_RATE 0.5
int graph[N][N] = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
typedef struct {
int path[N];
int pathLength;
} Ant;
void initializeAnts(Ant *ants) {
for (int i = 0; i < NUM_ANTS; i++) {
for (int j = 0; j < N; j++) {
ants[i].path[j] = -1;
}
ants[i].pathLength = 0;
}
}
bool visited(int *path, int city) {
for (int i = 0; i < N; i++) {
if (path[i] == city) return true;
}
return false;
}
void updatePheromones(double pheromones[N][N], Ant *ants) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
pheromones[i][j] *= (1.0 - EVAPORATION_RATE);
}
}
for (int k = 0; k < NUM_ANTS; k++) {
for (int i = 0; i < N - 1; i++) {
pheromones[ants[k].path[i]][ants[k].path[i + 1]] += 1.0 / ants[k].pathLength;
}
pheromones[ants[k].path[N - 1]][ants[k].path[0]] += 1.0 / ants[k].pathLength;
}
}
void antColonyOptimization() {
double pheromones[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
pheromones[i][j] = 1.0;
}
}
Ant ants[NUM_ANTS];
int bestPath[N];
int bestPathLength = INT_MAX;
srand(time(0));
for (int iter = 0; iter < MAX_ITER; iter++) {
initializeAnts(ants);
for (int k = 0; k < NUM_ANTS; k++) {
int startCity = rand() % N;
ants[k].path[0] = startCity;
int currentCity = startCity;
for (int step = 1; step < N; step++) {
double probabilities[N];
double sumProbabilities = 0.0;
for (int city = 0; city < N; city++) {
if (!visited(ants[k].path, city)) {
double probability = pow(pheromones[currentCity][city], ALPHA) * pow(1.0 / graph[currentCity][city], BETA);
probabilities[city] = probability;
sumProbabilities += probability;
} else {
probabilities[city] = 0.0;
}
}
double randProb = (rand() / (double)RAND_MAX) * sumProbabilities;
double cumulativeProbability = 0.0;
int nextCity = -1;
for (int city = 0; city < N; city++) {
cumulativeProbability += probabilities[city];
if (randProb <= cumulativeProbability && probabilities[city] > 0) {
nextCity = city;
break;
}
}
ants[k].path[step] = nextCity;
ants[k].pathLength += graph[currentCity][nextCity];
currentCity = nextCity;
}
ants[k].pathLength += graph[currentCity][start
City];
if (ants[k].pathLength < bestPathLength) {
bestPathLength = ants[k].pathLength;
for (int i = 0; i < N; i++) {
bestPath[i] = ants[k].path[i];
}
}
}
updatePheromones(pheromones, ants);
}
printf("Best path using Ant Colony Optimization: ");
for (int i = 0; i < N; i++) {
printf("%d ", bestPath[i]);
}
printf("\nMinimum distance: %d\n", bestPathLength);
}
int main() {
antColonyOptimization();
return 0;
}Also read
Solving the Travelling Salesman Problem in Java: A Comprehensive Guide
Solving the Travelling Salesman Problem in Python: A Comprehensive Guide
Solving the Travelling Salesman Problem in C++: A Comprehensive Guide
Conclusion
The Travelling Salesman Problem is a fundamental problem in computer science and operations research. While exact algorithms like brute force and dynamic programming guarantee optimal solutions, their high computational complexity makes them impractical for large datasets. Approximation algorithms and heuristic methods, including nearest neighbor, genetic algorithms, simulated annealing, and ant colony optimization, offer practical alternatives for finding near-optimal solutions efficiently. Implementing these algorithms in C provides a powerful way to tackle TSP, leveraging the language’s performance and control over system resources.
By understanding and implementing these various approaches, developers and researchers can choose the most suitable method for their specific requirements, balancing between solution optimality and computational efficiency.
