2 opt algorithm to solve the travelling salesman problem in python

The travelling salesman problem is a classic optimization problem in computer science. Given a list of cities and the distances between each pair of cities, the task is to find the shortest possible route that visits each city exactly once and returns to the starting city.

Option 1: Brute Force

One way to solve the travelling salesman problem is to use a brute force approach. This involves generating all possible permutations of the cities and calculating the total distance for each permutation. The shortest route is then selected as the solution.

import itertools

def tsp_brute_force(cities, distances):
    shortest_route = None
    shortest_distance = float('inf')
    
    for permutation in itertools.permutations(cities):
        distance = calculate_distance(permutation, distances)
        
        if distance < shortest_distance:
            shortest_distance = distance
            shortest_route = permutation
    
    return shortest_route, shortest_distance

def calculate_distance(route, distances):
    total_distance = 0
    
    for i in range(len(route) - 1):
        city1 = route[i]
        city2 = route[i + 1]
        total_distance += distances[city1][city2]
    
    return total_distance

This brute force approach has a time complexity of O(n!), where n is the number of cities. This means that the algorithm becomes impractical for large numbers of cities, as the number of permutations grows exponentially.

Option 2: Dynamic Programming

A more efficient approach to solving the travelling salesman problem is to use dynamic programming. This involves breaking down the problem into smaller subproblems and solving them in a bottom-up manner.

def tsp_dynamic_programming(cities, distances):
    n = len(cities)
    dp = [[float('inf')] * n for _ in range(2 ** n)]
    dp[1][0] = 0
    
    for mask in range(1, 2 ** n):
        for last_city in range(n):
            if mask & (1 << last_city):
                for current_city in range(n):
                    if current_city != last_city and mask & (1 << current_city):
                        dp[mask][last_city] = min(dp[mask][last_city], dp[mask ^ (1 << last_city)][current_city] + distances[current_city][last_city])
    
    shortest_distance = float('inf')
    last_city = None
    
    for i in range(n):
        if dp[2 ** n - 1][i] + distances[i][0] < shortest_distance:
            shortest_distance = dp[2 ** n - 1][i] + distances[i][0]
            last_city = i
    
    shortest_route = reconstruct_route(dp, distances, last_city)
    
    return shortest_route, shortest_distance

def reconstruct_route(dp, distances, last_city):
    n = len(dp[0])
    mask = 2 ** n - 1
    route = [0]
    
    while mask != 1:
        for i in range(n):
            if i != last_city and mask & (1 << i) and dp[mask][last_city] == dp[mask ^ (1 << last_city)][i] + distances[i][last_city]:
                route.append(i)
                mask ^= (1 << last_city)
                last_city = i
                break
    
    route.append(0)
    return route

This dynamic programming approach has a time complexity of O(n^2 * 2^n), which is much more efficient than the brute force approach. It can handle larger numbers of cities, but still becomes impractical for very large instances of the problem.

Option 3: Approximation Algorithm

If an exact solution is not required, an approximation algorithm can be used to find a good solution to the travelling salesman problem in a reasonable amount of time. One such algorithm is the 2-opt algorithm.

def tsp_2_opt(cities, distances):
    n = len(cities)
    route = list(range(n))
    improved = True
    
    while improved:
        improved = False
        
        for i in range(1, n - 2):
            for j in range(i + 1, n):
                if j - i == 1:
                    continue
                
                new_route = route[:i] + route[i:j][::-1] + route[j:]
                new_distance = calculate_distance(new_route, distances)
                
                if new_distance < calculate_distance(route, distances):
                    route = new_route
                    improved = True
    
    return route, calculate_distance(route, distances)

The 2-opt algorithm repeatedly swaps two edges in the current route to try to improve it. This process continues until no further improvements can be made. While the 2-opt algorithm does not guarantee an optimal solution, it often produces good results in practice.

Among the three options, the dynamic programming approach is the best choice for solving the travelling salesman problem in Python. It provides an exact solution and can handle larger instances of the problem compared to the brute force approach. The approximation algorithm can be used as a faster alternative when an exact solution is not required.

Rate this post

7 Responses

Leave a Reply

Your email address will not be published. Required fields are marked *

Table of Contents