<jupyter_start><jupyter_text>Travelling Salesperson Problem (Backtracking)> A solution to the travelling salesperson problem using backtracking.- toc: true- badges: true- comments: true- categories: [algorithm, graphs]- permalink: /2022/06/02/travelling_salesperson_problem_backtracking/  Dependencies<jupyter_code>import math
import collections
import random as rand
import networkx as nx<jupyter_output><empty_output><jupyter_text>NotesThe **Travelling Salesperson Problem** is defined as:> *Given a set of cities and distances between every pair of cities, the [***Travelling Salesperson***] problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.*>> *[Traveling Salesman Problem (TSP) Implementation](https://www.geeksforgeeks.org/traveling-salesman-problem-tsp-implementation/)* (GeeksForGeeks)In this implementation, we use recursiive backtracking, which is generally more efficient then generating permutations.  Function<jupyter_code>def backtracking_tsp(G: nx.Graph, start: object) -> float | int:
    """Return the shortest route that visits every city exactly once and
    ends back at the start.

    Solves the travelling salesperson problem using backtracking.

    Preconditions:
    - G is a complete weighted graph
    - 'start' in G
    - G[u, v]['weight'] is the distance u -> v
    """
    def _tsp(G, visited, u, dist, min_dist):
        if visited.total() == (len(G.nodes) - 1):
            min_dist = min(min_dist, dist + G.edges[u, start]['weight'])
        else:
            for v in G.nodes:
                if visited[v] == 0 and v != start:
                    visited[v] += 1
                    next_dist = dist + G.edges[u, v]['weight']
                    if next_dist < min_dist:
                        min_dist = _tsp(G, visited, v, next_dist, min_dist)
                    visited[v] -= 1

        return min_dist

    return _tsp(G, collections.Counter(), start, 0, math.inf)<jupyter_output><empty_output><jupyter_text>Example usage Initialise the graph<jupyter_code>cg = nx.complete_graph(['origin', 'a', 'b', 'c', 'd'])
g = nx.Graph((u, v, {'weight': rand.randint(1, 10)}) for u, v in cg.edges)
print(f"g = {g}")<jupyter_output>g = Graph with 5 nodes and 10 edges<jupyter_text>Find the shortest path from the origin<jupyter_code>print(f"Shortest path from the origin = {backtracking_tsp(g, 'origin')}")<jupyter_output>Shortest path from the origin = 18<jupyter_text>Performance<jupyter_code>for n in [4, 6, 8, 10]:
    cg = nx.complete_graph(n)
    g = nx.Graph((u, v, {'weight': rand.randint(1, 10)}) for u, v in cg.edges)
    print(f"|nodes(g)| = {n}")
    %timeit backtracking_tsp(g, 1)<jupyter_output>|nodes(g)| = 4
24.1 µs ± 379 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
|nodes(g)| = 6
588 µs ± 2.06 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
|nodes(g)| = 8
6.23 ms ± 26.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
|nodes(g)| = 10
110 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
{'fraction_non_alphanumeric': 0.12213490504256712, 'fraction_numerical': 0.024885396201702686, 'mean_word_length': 3.607843137254902, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 24, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '199059', 'license': 'MIT', 'n_tokens_mistral': 1090, 'n_tokens_neox': 988, 'n_words': 340, 'path': '_notebooks/2022-06-02-tsp_backtracking.ipynb', 'repo_name': 'ljk233/blog', 'size': '3054'}