<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 The Traveling Salesman problem
Names of group members
// put your names here!
Goals of this assignment
The main goal of this assignment is to use Monte Carlo methods to find the shortest path between several cities - the "Traveling Salesman" problem.  This is an example of how randomization can be used to optimize problems that would be incredibly computationally expensive (and sometimes impossible) to solve exactly.
The Traveling Salesman problem
The Traveling Salesman Problem is a classic problem in computer science where the focus is on optimization.  The problem is as follows
Step1:  This code sets up everything we need
Given a number of cities, set up random x and y positions and calculate a table of distances between pairs of cities (used for calculating the total trip distance).  Then set up an array that controls the order that the salesman travels between cities, and plots out the initial path.
Step2:  Put your code below this!
Your code should take some number of steps, doing the following at each step
<ASSISTANT_TASK:>
Python Code:
import numpy as np
%matplotlib inline
import matplotlib.pyplot as plt
from IPython.display import display, clear_output
def calc_total_distance(table_of_distances, city_order):
    '''
    Calculates distances between a sequence of cities.
    
    Inputs: N x N table containing distances between each pair of the N
    cities, as well as an array of length N+1 containing the city order,
    which starts and ends with the same city (ensuring that the path is
    closed)
    Returns: total path length for the closed loop.
    '''
    total_distance = 0.0
    # loop over cities and sum up the path length between successive pairs
    for i in range(city_order.size-1):
        total_distance += table_of_distances[city_order[i]][city_order[i+1]]
    return total_distance
def plot_cities(city_order,city_x,city_y):
    '''
    Plots cities and the path between them.
    
    Inputs: ordering of cities, x and y coordinates of each city.  
    
    Returns: a plot showing the cities and the path between them.
    '''
    
    # first make x,y arrays
    x = []
    y = []
    # put together arrays of x and y positions that show the order that the
    # salesman traverses the cities
    for i in range(0, city_order.size):
        x.append(city_x[city_order[i]])
        y.append(city_y[city_order[i]])
    # append the first city onto the end so the loop is closed
    x.append(city_x[city_order[0]])
    y.append(city_y[city_order[0]])
    #time.sleep(0.1)  
    clear_output(wait=True)
    display(fig)            # Reset display
    fig.clear()             # clear output for animation
    plt.xlim(-0.2, 20.2)    # give a little space around the edges of the plot
    plt.ylim(-0.2, 20.2)
    
    # plot city positions in blue, and path in red.
    plt.plot(city_x,city_y, 'bo', x, y, 'r-')
Explanation: The Traveling Salesman problem
Names of group members
// put your names here!
Goals of this assignment
The main goal of this assignment is to use Monte Carlo methods to find the shortest path between several cities - the "Traveling Salesman" problem.  This is an example of how randomization can be used to optimize problems that would be incredibly computationally expensive (and sometimes impossible) to solve exactly.
The Traveling Salesman problem
The Traveling Salesman Problem is a classic problem in computer science where the focus is on optimization.  The problem is as follows: Imagine there is a salesman who has to travel to N cities.  The order is unimportant, as long as he only visits each city once on each trip, and finishes where he started.  The salesman wants to keep the distance traveled (and thus travel costs) as low as possible.  This problem is interesting for a variety of reasons - it applies to transportation (finding the most efficient bus routes), logistics (finding the best UPS or FedEx delivery routes for some number of packages), or in optimizing manufacturing processes to reduce cost.
The Traveling Salesman Problem is extremely difficult to solve for large numbers of cities - testing every possible combination of cities would take N! (N factorial) individual tests.  For 10 cities, this would require 3,628,800 separate tests.  For 20 cities, this would require 2,432,902,008,176,640,000 (approximately $2.4 \times 10^{18}$) tests - if you could test one combination per microsecond ($10^{-6}$ s) it would take approximately 76,000 years!  For 30 cities, at the same rate testing every combination would take more than one billion times the age of the Universe.  As a result, this is the kind of problem where a "good enough" answer is sufficient, and where randomization comes in.
A good local example of a solution to the Traveling Salesman Problem is an optimized Michigan road trip calculated by a former MSU graduate student (and one across the US).  There's also a widely-used software library for solving the Traveling Salesman Problem; the website has some interesting applications of the problem!
End of explanation
# number of cities we'll use.
number_of_cities = 30
# seed for random number generator so we get the same value every time!
np.random.seed(2024561414)
# create random x,y positions for our current number of cities.  (Distance scaling is arbitrary.)
city_x = np.random.random(size=number_of_cities)*20.0
city_y = np.random.random(size=number_of_cities)*20.0
# table of city distances - empty for the moment
city_distances = np.zeros((number_of_cities,number_of_cities))
# calculate distnace between each pair of cities and store it in the table.
# technically we're calculating 2x as many things as we need (as well as the
# diagonal, which should all be zeros), but whatever, it's cheap.
for a in range(number_of_cities):
    for b in range(number_of_cities):
        city_distances[a][b] = ((city_x[a]-city_x[b])**2 + (city_y[a]-city_y[b])**2 )**0.5
# create the array of cities in the order we're going to go through them
city_order = np.arange(city_distances.shape[0])
# tack on the first city to the end of the array, since that ensures a closed loop
city_order = np.append(city_order, city_order[0])
Explanation: This code sets up everything we need
Given a number of cities, set up random x and y positions and calculate a table of distances between pairs of cities (used for calculating the total trip distance).  Then set up an array that controls the order that the salesman travels between cities, and plots out the initial path.
End of explanation
fig = plt.figure()
# Put your code here!
# number of steps we'll take
N_steps = 1000
step = [0]
distance = [calc_total_distance(city_distances,city_order)]
for i in range(N_steps):
    
    swap1 = np.random.randint(1,city_order.shape[0]-2)
    swap2 = np.random.randint(1,city_order.shape[0]-2)
    
    orig_distance = calc_total_distance(city_distances,city_order)
    
    new_city_order = np.copy(city_order)
    hold = new_city_order[swap1]
    new_city_order[swap1] = new_city_order[swap2]
    
    new_city_order[swap2] = hold
    
    new_distance = calc_total_distance(city_distances,new_city_order)
    if new_distance < orig_distance:
        city_order = np.copy(new_city_order)
     
        step.append(i)
        distance.append(new_distance)
    
    plot_cities(city_order,city_x,city_y)
    
    
plt.plot(step,distance)
Explanation: Put your code below this!
Your code should take some number of steps, doing the following at each step:
Randomly swap two cities in the array of cities (except for the first/last city)
Check the total distance traversed by the salesman
If the new ordering results in a shorter path, keep it.  If not, throw it away.
Plot the shorter of the two paths (the original one or the new one)
Also, keep track of the steps and the minimum distance traveled as a function of number of steps and plot out the minimum distance as a function of step!
End of explanation
<END_TASK>