This problem will solve the Traveling Salesman Problem for a small number of cities N$=11.$

Your tsp$.$py code must record how long it takes to compute a solution.

The method chosen is the brute force method.

Your code will compute ALL possible paths and find the path that minimizes the total distance.

Your code must create a $(2$D list$)$ matrix called distance and fill the elements with the

distance between any $2$ locations as explained in lecture.

Codes must be submitted to the slurm queuing system on either fry or owens.

You may not use the module itertools to find all permutations. You must do this in nested lops as was done in quiz$04$ in the createData.py code

NOT ALLOWED BELOW

import itertools

list$($itertools$.$permutations$([1,2,3]))$

NOT ALLOWED ABOVE

Overview:

$*)$ Deliver these $5$ files $($tsp$.$py$,$ tspDist.py$,$ proj$02.$slurm, proj$02.$output, distance.pickle$)$

On the remote system place these and only these $5$ files in a folder called proj$02$

On the remote system tar the entire folder as

tar zcvf proj$02.$tgz proj$02/$

$*)$ Python code to find best TSP path $($tsp$.$py$)$

This must be run only as given below:

For the OSC systems:

singularity exec ~nehrbajo$/$python$3.$sif python$3$ tsp$.$py combined.pickle $11$

on osc systems

~nehrbajo$/$proj$02\_$grade proj$02.$tgz

Input files or codes needed:

$-------------------$

Located on Owens

~nehrbajo$/$combined$.$pickle # you may copy this file to $HOME

~nehrbajo$/$python$3.$sif # don't copy this. Run from my directory

~nehrbajo$/$proj$02\_$grade # don't copy this. Run from my directory

Steps:

$1.)$ Write a python code to read in the pickle file.

Keep only the first N cities and keep them in this order.

The first city is home.... Wright State University.

address$[0]$

$2.)$ Implement the TSP algorithm.

This python code will find the optimal solution from home

to the next N$-1$ cities and back to home.

You $**$MUST$**$ calculate all possible paths.

$3.)$ Test$/$debug your code on a smaller number of cities

before submitting to the testing code.

You are not allowed to run your code interactively, but rather

You $**$MUST$**$ submit your code to the slurm queuing system.

This can be done on either owens or fry.

$4.)$ Keep track of how long it takes for your tsp code to

finish. Include this information in your output as defined below.

$--------------------------------------------$

Syntax for singularity:

singularity $--$silent exec containerName list$\_$of$\_$commands$\_$to$\_$run

In our case the list$\_$of$\_$commands$\_$to$\_$run are

python$3$ python$\_$code.py $[$python parameters$]$

Grading criteria:

$--------------------------------------------$

# Format of first $7$ lines of both python codes MUST follow.

Header on python codes $($tsp$.$py$,$ tspDist.py$)$

$($ Do not include header for the proj$02.$slurm, proj$02.$output files$)$

#$!/$ the path to your python$3$ code within the singularity container

# Name: John Smith

# wNumber: w$123$abc Never put your UIDnumber

# Project name: proj$02$

# Assigned: Oct $03$

# Due date: Oct $17$

# Tested on: $($fry$,$ pitzer, owens$)$ pick one and ONLY one of these

# example format for the above line:

# Tested on: fry

# Header lines $4,5$ and $6$ should be exactly as above

For proj$02.$slurm

Properly formatted slurm header using $(1$ Node and $1$ task per node$)$

Include bash commands to run your codes

The slurm script will first run just one tspDist.py test

that will use the list of $0419378562100$

Then it will run the tsp$.$py test with the

inputPickleFile set to the combined.pickle file and N$=11$

Both of these shall be done in one slurm script... not $2$ different ones.

For tspDist.py

This shall be run as $($ example on fry $)$

singularity exec ~w$006$jwn$/$python$3.$sif python$3$ tspDist.py $0419378562100$

I will however test your code against other orders and sizes of lists but you may assume

that I will use the combined.pickle file as an input.

Output is exclusively one number $($ddddd$)$ which is the integer distance in miles

For tsp$.$py

run as $($ example on OSC$)$

singularity exec ~