I need help with an example of a traveling salesman problem. I have a 2D array. Where the vertices are 0-9. The numbers represent places. So if I choose a row value of 5 and a column value of 4 the corresponding value the array gives me is 3. So it would cost me $3 to get from place 4 to 5 or vice versa. So I need to write a function that determines (and prints) the lowest and the highest costs for all of the possible rearrangments of the vertices. Note that if you use 9 as your starting and ending point in a path (which is fine since when thinking about a cycle, any starting point will do) then you can generate all of the cycles by generating permutations of nine digits between 0 and 8 inclusive as lists and prepending and appending 9 to said lists. # 0 1 2 3 4 5 6 7 8 9 adj_matrix = [[ 0, 4, 3, 3, 4, 3, 2, 3, 1, 2], # 0 [ 4, 0, 5, 3, 2, 5, 4, 1, 5, 4], # 1 [ 3, 4, 0, 2, 5, 2, 2, 4, 2, 2], # 2 [ 3, 3, 2, 0, 3, 2, 3, 2, 2, 1], # 3 [ 4, 2, 5, 3, 0, 3, 4, 3, 3, 2], # 4 [ 3, 5, 2, 2, 3, 0, 2, 4, 2, 1], # 5 [ 2, 4, 2, 3, 4, 2, 0, 5, 1, 2], # 6 [ 3, 1, 4, 2, 3, 4, 5, 0, 4, 3], # 7 [ 1, 5, 2, 2, 3, 2, 1, 4, 0, 1], # 8 [ 2, 4, 2, 1, 2, 1, 2, 3, 1, 0]] # 9
I need help with an example of a traveling salesman problem. I have a 2D array. Where the vertices are 0-9. The numbers represent places. So if I choose a row value of 5 and a column value of 4 the corresponding value the array gives me is 3. So it would cost me $3 to get from place 4 to 5 or vice versa. So I need to write a function that determines (and prints) the lowest and the highest costs for all of the possible rearrangments of the vertices. Note that if you use 9 as your starting and ending point in a path (which is fine since when thinking about a cycle, any starting point will do) then you can generate all of the cycles by generating permutations of nine digits between 0 and 8 inclusive as lists and prepending and appending 9 to said lists.
# 0 1 2 3 4 5 6 7 8 9
adj_matrix = [[ 0, 4, 3, 3, 4, 3, 2, 3, 1, 2], # 0
[ 4, 0, 5, 3, 2, 5, 4, 1, 5, 4], # 1
[ 3, 4, 0, 2, 5, 2, 2, 4, 2, 2], # 2
[ 3, 3, 2, 0, 3, 2, 3, 2, 2, 1], # 3
[ 4, 2, 5, 3, 0, 3, 4, 3, 3, 2], # 4
[ 3, 5, 2, 2, 3, 0, 2, 4, 2, 1], # 5
[ 2, 4, 2, 3, 4, 2, 0, 5, 1, 2], # 6
[ 3, 1, 4, 2, 3, 4, 5, 0, 4, 3], # 7
[ 1, 5, 2, 2, 3, 2, 1, 4, 0, 1], # 8
[ 2, 4, 2, 1, 2, 1, 2, 3, 1, 0]] # 9
Thank you!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
