Blog

The traveling salesman problem (TSP) is a classic optimization problem that 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 NP-hard, which means that there is no known polynomial-time algorithm to find the optimal solution. However, there are many heuristics and exact algorithms that can solve the problem for small or medium-sized instances, or approximate the solution for large instances.

In this blog post, we will explore some of these methods and how to implement them in Kotlin, a modern and concise programming language that is widely used by Android developers and interoperable with Java.²³

Brute Force

The simplest way to solve the TSP is to generate all possible permutations of the cities and calculate the cost of each one. Then, we can return the permutation with the minimum cost as the optimal solution.

This method is guaranteed to find the optimal solution, but it is very inefficient. The number of permutations grows factorially with the number of cities, so for n cities, there are n! possible routes. For example, if we have 10 cities, there are 10! = 3,628,800 possible routes. If we have 20 cities, there are 20! = 2.43 x 10^18 possible routes.

To implement this method in Kotlin, we can use a vector to store all the cities except the starting city. Then, we can use the nextPermutation function from the Kotlin standard library to generate all possible permutations of this vector. For each permutation, we can calculate the cost by adding up the distances between consecutive cities and between the last city and the starting city. We can keep track of the minimum cost and the corresponding permutation using two variables. Finally, we can return the permutation with the minimum cost as the optimal solution.

Here is an example of how this method looks like in code:

// A function that calculates the cost of a route fun calculateCost(graph: Array<IntArray>, route: List<Int>, start: Int): Int { var cost = 0 var current = start for (city in route) { cost += graph[current][city] current = city } cost += graph[current][start] return cost } // A function that solves the TSP using brute force fun solveTSPBruteForce(graph: Array<IntArray>, start: Int): List<Int> { // Create a vector of all cities except the start val cities = mutableListOf<Int>() for (i in graph.indices) { if (i != start) { cities.add(i) } } // Initialize the minimum cost and the optimal route var minCost = Int.MAX_VALUE var optimalRoute = listOf<Int>() // Generate all permutations of cities do { // Calculate the cost of the current permutation val cost = calculateCost(graph, cities, start) // Update the minimum cost and the optimal route if needed if (cost < minCost) { minCost = cost optimalRoute = cities.toList() } } while (cities.nextPermutation()) // Return the optimal route return optimalRoute }

Nearest Neighbor

A more efficient way to solve the TSP is to use a heuristic that builds a route by choosing the nearest city at each step. This method is not guaranteed to find the optimal solution, but it is much faster than brute force.

The idea is to start from any city and mark it as visited. Then, find the nearest unvisited city and move to it. Repeat this process until all cities are visited. Finally, return to the starting city to complete the route.

This method has a time complexity of O(n^2), where n is the number of cities. This is because we need to loop through all cities and find the nearest unvisited city at each step.

To implement this method in Kotlin, we can use a boolean array to keep track of which cities are visited. Then, we can use a loop to iterate through all cities and find the nearest unvisited city using a nested loop. We can add each city to a list as we visit them. Finally, we can return the list as the solution.

Here is an example of how this method looks like in code:

// A function that solves the TSP using nearest neighbor heuristic fun solveTSPNearestNeighbor(graph: Array<IntArray>, start: Int): List<Int> { // Create an array of visited cities val visited = BooleanArray(graph.size) { false } // Mark the start city as visited visited[start] = true // Create a list to store the route val route = mutableListOf<Int>() // Add the start city to the route route.add(start) // Initialize the current city as start var current = start // Loop until all cities are visited while (route.size < graph.size) { // Initialize the minimum distance and the nearest city var minDistance = Int.MAX_VALUE var nearestCity = -1 // Loop through all cities for (i in graph.indices) { // Skip if the city is visited or same as current if (visited[i] || i == current) continue // Update the minimum distance and nearest city if needed if (graph[current][i] < minDistance) { minDistance = graph[current][i] nearestCity = i } } // Mark the nearest city as visited visited[nearestCity] = true // Add it to the route route.add(nearestCity) // Update current city as nearest city current = nearestCity } // Return route return route }

Dynamic Programming

A more advanced way to solve the TSP is to use a dynamic programming algorithm that exploits the overlapping subproblems and optimal substructure of the problem. This method can find the optimal solution in polynomial time, but it requires a lot of memory.

The idea is to use a two-dimensional array to store the minimum cost of visiting a subset of cities and ending at a specific city. The array is indexed by a bitmask that represents the subset of cities and an integer that represents the last city. The base case is when the subset contains only one city, which is the starting city. The cost is zero in this case. The recursive case is when the subset contains more than one city. The cost is the minimum of the cost of visiting the previous subset and ending at any other city plus the distance from that city to the current city.

This method has a time complexity of O(n^2 * 2^n), where n is the number of cities. This is because we need to fill up the array for all possible subsets of cities and all possible last cities. The array has a size of 2^n * n.

To implement this method in Kotlin, we can use a nested function that takes a bitmask and a last city as parameters and returns the minimum cost. The function can use memoization to avoid repeated calculations. Then, we can call the function with the bitmask that represents all cities and the starting city as parameters. We can also use another array to store the optimal route by keeping track of which city was chosen at each step.

Here is an example of how this method looks like in code:

// A function that solves the TSP using dynamic programming fun solveTSPDynamicProgramming(graph: Array<IntArray>, start: Int): List<Int> { // Create an array for memoization val memo = Array(1 shl graph.size) { IntArray(graph.size) { -1 } } // Create an array for storing the route val route = Array(1 shl graph.size) { IntArray(graph.size) { -1 } } // A nested function that takes a bitmask and a last city and returns the minimum cost fun dp(bitmask: Int, last: Int): Int { // Base case: if only one city in the subset, return zero if (bitmask == (1 shl last)) return 0 // If already calculated, return memoized value if (memo[bitmask][last] != -1) return memo[bitmask][last] // Initialize the minimum cost and the previous city var minCost = Int.MAX_VALUE var prevCity = -1 // Loop through all cities for (i in graph.indices) { // Skip if the city is not in the subset or same as last if ((bitmask and (1 shl i)) == 0 || i == last) continue // Calculate the cost of visiting the previous subset and ending at i val cost = dp(bitmask xor (1 shl last), i) + graph[i][last] // Update the minimum cost and previous city if needed if (cost < minCost) { minCost = cost prevCity = i } } // Memoize and store the minimum cost and previous city memo[bitmask][last] = minCost route[bitmask][last] = prevCity // Return minimum cost return minCost } // Call dp with all cities in the subset and start as last city val minCost = dp((1 shl graph.size) - 1, start) // Create a list to store the optimal route val optimalRoute = mutableListOf<Int>() // Add start to the route optimalRoute.add(start) // Initialize bitmask and last city var bitmask = (1 shl graph.size) - 1 var last = start // Loop until all cities are added to route while (route[bitmask][last] != -1) { // Find previous city from route array val prev = route[bitmask][last] // Add it to route optimalRoute.add(prev) // Update bitmask and last city bitmask = bitmask xor (1 shl last) last = prev } // Return optimal route return optimalRoute }