Class 39 — Wednesday May 5

I know that you know that

Programming basics — You achieved this semester — Bask in the success

I say thanks to you — Your presence is a great gift — Brings me happiness

Love is all you need — Enjoy family and friends — Lead lives pay forward

       

39 steps wikimedia


Look both ways


Agenda


Thanks to the TAs for making the course successful

Katherine Brickley Ann Hoang Rachel McNamara MaryJeanine Seaman
Simona Brkic Hallie Khoung Jimmy Njuguna Jacob St. Martin
Ryan Green Kevin Luk


Want to be a TA for CS 1112


Consider CS 2501

lou's list CS 2501



Project — Traveling Salesperson Problem assistance

Due Saturday May 8

Will be available on Friday during class time

In the below Wikipedia figure, the red dots represent city locations and the tour of edges connecting them is the least length of all tours.

from wikipedi Travelling_salesman_problem/media

Files


Discussion

3 TSP tours

cities = [ (281, 234), (515, 321), (738, 44), (530, 60), (410, 377), (135, 293),

  (883, 158), (366, 307), (380, 166), (881, 34) ]

3 TSP tours

start_tour = [ 0, 7, 4, 8, 1, 3, 9, 6, 2, 5 ]

mid_tour = [ 0, 7, 5, 4, 1, 2, 9, 6, 3, 8 ]

end_tour = [ 0, 5, 4, 1, 7, 8, 3, 2, 9, 6 ]



Your task

Function d( cities, i1, i2 )

testing d()

cities: [(281, 468), (515, 643), (738, 88), (530, 120), (410, 754)]

a: 2

b: 4

d( cities, a, b ): 742.3880386967452



Function swap( tour, i1, i2 )

testing swap()

i1: 2

i2: 4

tour before swapping at indices i1 and i2: [4, 3, 1, 0, 2]

tour after swapping at indices i1 and i2: [4, 3, 2, 0, 1]



Function random_location( w, h )

testing random_location()

w: 1000

h: 500

random_location( w, h ): (355, 250)



Function initialize_city_locations( n, w, h )

testing initialize_city_locations()

n: 4

w: 1000

h: 500

initialize_city_locations( n, w, h ): [(281, 234), (515, 321), (738, 44), (530, 60)]



Function cost( cities, tour )

Set n to number of cities.

Initialize accumulator to 0.

For i in the interval 0 ... n-2 do

  Set a and b to be respectively the ith and i+1th tour entries.

  Add to the accumulator the distance between the ath and bth cities entries.

Set a and b to be respectively the 0th and n-1th tour entries.

Add to the accumulator the distance between the ath and bth cities entries.

testing cost()

cities: [(281, 468), (515, 643), (738, 88), (530, 120), (410, 754)]

tour: [4, 2, 0, 3, 1]

cost( cities, tour ): 2440.652320335747



Function consider( cities, tour, i1, i2 )

testing consider()

cities: [(281, 468), (515, 643), (738, 88), (530, 120), (410, 754)]

starting tour: [1, 0, 4, 3, 2]

i1: 2

i2: 4

consider( cities, tour, i1, i2 ): True

current tour: [1, 0, 2, 3, 4]


cities: [(281, 468), (515, 643), (738, 88), (530, 120), (410, 754)]

starting tour: [1, 0, 4, 3, 2]

i1: 1

i2: 3

consider( cities, tour, i1, i2 ): False

current tour: [1, 0, 4, 3, 2]



Now it's time to say good bye

sunset


 


  🦆 © 2022 Jim Cohoon   Resources from previous semesters are available.