Traveling Salesman Probelm (TSP)

• Imagine you work for a package delivery company. What is the Shortest Path to fly to each of these cities exactly one time and then return to your starting point?

• The TSP is a classic example of an optimization problem where the goal is to find the most efficient route.

Element of the Traveling Salesman Problem

Edges

• Represent the direct paths between nodes. Each edge has an associated cost or weight, such as the distance, time, or expense required to travel between two nodes.

Path 

• A path is a sequence of edges connecting the nodes. 

• Number of paths for n nodes? (n – 1)! / 2

Sequence

• A sequence is an arrangement of nodes. 

• Here, we walk through a programmed solution to the traveling salesman problem problem.

• The algorithm is as follows:

1. Generate all unique round-trip paths that can be taken across our cities.

2. Calculate the distances of all our generated paths.

3. Select the path with the shortest distance.

• The algorithm may seem simple, but there are many parts to break down to describe this in code! We'll walk you through section by section, **function by function**, and show you how this is done.

Step 1: Generate All Unique Possible Paths

• We will organize our code from here on out into functions. A function is simply a reusable piece of code, a routine that is defined once but can be called many times! This allows us to separate our code into reusable chunks, a technique known as modularizing our code.

• Like in math, a function in code can have inputs and outputs. Outputs are indicated with the return keyword. Function definitions in Python are indicated with the def keyword.

• Let's look at our first couple of functions below: the path-generation functions!

• Before we find the shortest path, our algorithm first finds all the possible paths there are (this technique is known as brute force). Our main function in this section, getUniquePaths, does just that: given a collection of n cities, it returns a collection of  (𝑛−1)!/2  unique paths.

• Our other function, isUnique, is what's called a helper function--our getUnique function uses the isUnique subroutine to determine if a given path is unique (our first reusable piece of code!).

Step 2: Distance functions

• Let's look at our next couple of functions below: The Distance Functions!

• Besides having to generate all possible paths, we need routines to calculate the distances of those paths. We have two functions: one that will calculate the total distance of a path (getTotalDistance) and one that calculates the distance just between two cities (getDistance). 

  • We use getDistance repeatedly as a helper function for getTotalDistance--another reusable piece of code! :)

• One thing you may notice while reading this code is that programming and mathematics are intricately related. The distance function is a prime example of this--getDistance uses the distance formula in its implementation! Just think about it: how fascinating it is that we can get electrons to do our math for us...