Using circular permutations to reduce Traveling Salesman complexity

Optimizing Traveling Salesman Problem Complexity with Circular Permutations

The Traveling Salesman Problem (TSP) is a classic optimization problem that involves finding the shortest possible route for a traveling salesperson to visit a set of cities and return to the starting city. While TSP has several variants, the most common is the symmetric TSP, where the distance between two cities is the same in both directions.

One approach to solving symmetric TSP is to use the brute-force algorithm, which evaluates all possible routes and selects the shortest one. However, this approach has a time complexity of O(n!), which quickly becomes intractable as the number of cities increases.

To reduce the complexity of the brute-force algorithm, we can leverage circular permutations, which are rotations of a given permutation. By considering circular permutations as equivalent, we can significantly reduce the number of routes that need to be evaluated.

Eliminating Mirror Solutions

Further optimization can be achieved by eliminating mirrored solutions. Mirrored solutions are pairs of routes that are reflections of each other. By eliminating one of the mirrored solutions from consideration, we can halve the number of routes that need to be evaluated.

Efficient Generation of Circular Permutations

There are various methods for generating circular permutations. One efficient approach is to enumerate all possibilities of 1 ... N-1 where 1 is before 2 (forcing direction) and appending N. This method has a time complexity of O((N-1)!/2), which is significantly lower than the brute-force approach.

def generate_circular_permutations(n):
    """Generate circular permutations of a given length."""
    permutations = []
    visited = set()

    def generate(permutation, remaining):
        if remaining == 0:
            permutations.append(permutation + [1])  # Append 1 to complete the circle.
            return

        for i in range(2, n + 1):
            if i not in visited and (permutation[-1] < i or i == 2):
                visited.add(i)
                generate(permutation + [i], remaining - 1)
                visited.remove(i)

    generate([1], n - 1)
    return permutations

Conclusion

By utilizing circular permutations and eliminating mirrored solutions, we can significantly reduce the complexity of solving the Traveling Salesman Problem using the brute-force algorithm. Additionally, efficient methods for generating circular permutations, such as the one presented in this article, can further improve the performance of the algorithm.