Travelling Salesman Problem (TSP) is one of the most famous and studied problems in computer science and optimization. It involves finding the shortest possible route that visits each city exactly once and returns to the origin city.
What is the Travelling Salesman Problem (TSP)?
“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?”
The TSP has practical applications in various fields such as logistics, transportation, manufacturing, and network design. It’s used to optimize routing and scheduling problems where minimizing distance or time is crucial.
Approaches to Solve Travelling Salesman Problem
Brute Force: The brute force approach involves trying out all possible permutations of city routes and calculating the total distance for each permutation. While this approach guarantees the optimal solution, it becomes impractical for large numbers of cities due to its exponential time complexity.
Heuristic Methods: Heuristic methods aim to find near-optimal solutions in a reasonable amount of time. Some popular heuristic algorithms for TSP include:
- Nearest Neighbour Algorithm
- Greedy Algorithms
- Genetic Algorithms
- Ant Colony Optimization
Exact Algorithms: Exact algorithms provide provably optimal solutions but may be computationally intensive. Dynamic Programming and Integer Linear Programming (ILP) are examples of exact algorithms used for TSP.
In this post, we’ll be discussing Nearest Neighbor Algorithm for Travelling Salesman Problem
Nearest Neighbour Algorithm
The nearest neighbor algorithm is a greedy approach to the TSP. It starts from an arbitrary city and repeatedly selects the nearest unvisited city until all cities have been visited. Finally, it returns to the starting city to complete the tour.
It is important to note that Nearest neighbor algorithm does not guarantee to find the optimal solution. It can produce suboptimal tours that are longer than the shortest possible tour. The time complexity of the nearest neighbor algorithm is O(n2), where n is the number of cities. However, it is more efficient than dynamic programming approaches for large instances of the problem.
Approach
1. Start at a random city.
2. Mark the current city as visited.
3. Repeat until all cities have been visited:
- Find the nearest unvisited city to the current city.
- Move to the nearest unvisited city and mark it as visited.
4. Return to the starting city to complete the tour.
Example
The graph represents distances between cities, where graph[i][j] denotes the distance from city i to city j. The algorithm starts from a given starting city and repeatedly chooses the nearest unvisited city until all cities have been visited, forming a tour.
Let’s start with an example where the starting city is city 1:
a) Start from city 1 b) Nearest unvisited city from city 1 is city 2 (distance = 10). Move to city 2. c) Nearest unvisited city from city 2 is city 3 (distance = 9). Move to city 3. d) Nearest unvisited city from city 3 is city 4 (distance = 12). Move to city 4. e) Nearest unvisited city from city 4 is city 1 (distance = 8). Move back to city 1 to complete the tour.
The resulting tour is:
1 -> 2 -> 3 -> 4 -> 1
The length of the path is the sum of distances between consecutive cities in the tour:Length = 1->2 (10) + 2->3 (9) + 3->4 (12) + 4->1 (8) = 39 units.
Pseudocode
nearestNeighbour(graph):
startCity = randomCity()
tour = [startCity]
mark startCity as visited
while cities remain unvisited:
currentCity = last city in tour
nearestCity = findNearestUnvisitedCity(currentCity)
add nearestCity to tour
mark nearestCity as visited
return tour
Code Implementation
//
// main.cpp
// Travelling Salesman Problem Nearest Neighbour
//
// Created by Himanshu on 01/03/24.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;
const int INF = INT_MAX;
// Function to find the nearest unvisited city
int findNearestCity(int currentCity, vector<bool>& visited, vector<vector<int>>& graph) {
int nearestCity = -1;
int minDistance = INF;
int n = (int) graph.size();
for (int i = 0; i < n; i++) {
if (!visited[i] && graph[currentCity][i] < minDistance) {
minDistance = graph[currentCity][i];
nearestCity = i;
}
}
return nearestCity;
}
// Function to perform nearest neighbour algorithm
vector<int> nearestNeighbour(vector<vector<int>>& graph) {
int n = (int) graph.size();
vector<bool> visited(n, false);
vector<int> tour;
// Start from a random city
int startCity = 0; // Change this to select a different starting city
tour.push_back(startCity);
visited[startCity] = true;
// Perform nearest neighbour algorithm
while (tour.size() < n) {
int currentCity = tour.back();
int nearestCity = findNearestCity(currentCity, visited, graph);
tour.push_back(nearestCity);
visited[nearestCity] = true;
}
// Return to the starting city to complete the tour
tour.push_back(startCity);
return tour;
}
// Function to calculate the total distance of the tour
int calculateTourDistance(const vector<int>& tour, const vector<vector<int>>& graph) {
int distance = 0;
for (int i = 0; i < tour.size() - 1; i++) {
distance += graph[tour[i]][tour[i + 1]];
}
return distance;
}
int main() {
vector<vector<int>> graph = {
{0, 10, 15, 20},
{5, 0, 9, 10},
{6, 13, 0, 12},
{8, 8, 9, 0}
};
vector<int> tour = nearestNeighbour(graph);
// Output the tour
cout << "Tour: ";
for (int city : tour) {
cout << city << " ";
}
cout << endl;
// Calculate and output the length of the path
int tourDistance = calculateTourDistance(tour, graph);
cout << "Length of the path: " << tourDistance << endl;
return 0;
}
Output
Tour: 0 1 2 3 0 Length of the path: 39
This code implements the Nearest Neighbour Algorithm to solve the Travelling Salesman Problem. It starts from a random city, repeatedly visits the nearest unvisited city, and returns to the starting city to complete the tour. The time complexity of the nearest neighbor algorithm is O(n2), where n is the number of cities.
The output is the sequence of cities visited (with 0-based indexing), representing the shortest possible route that visits each city exactly once and returns to the original city.