Putting it all together!

We have all the functions we need to write our algorithm! With the theses functions in mind, look again at the steps of our brute-force algorithm:

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.

We can accomplish Step 1 with our path-generation functions, and we can accomplish Step 2 with our distance functions. All we have left to do is combine the results with a little more programming logic to accomplish Step 3! 

(Completed Step 1 and Step 2 can be found in Colab notebook) 

traveling salesman problem extension 

Now that you guys have followed along with the traveling salesman problem complete the extension 

Knapsack problem 

You are a robber and have a knapsack that can hold a max weight of W. There are n items available, each with a weight wᵢ and a value vᵢ. Your goal is to maximize the total value of items you can carry in the knapsack without exceeding its weight capacity.

build your own

• This practice is very open-ended and you are welcome to take it in any direction you would like!

• Your job is to come up with an example using the skills you have learned from this module!

• Your task is to design your own TSP scenario and solve it using what you’ve learned.

  1. Define Your Problem (Choose your theme)

  2. Map Your Nodes

  3. Set Weights for Paths

  4. Solve the Problem