Class 39 — Wednesday May 5
|
|
Look both ways
Agenda
- Answer questions
- Consider TSP project
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
- Departmental application
Consider 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.
Files
- Module tsp.py
- Tester test_tsp.py
Discussion
- The Traveling Salesperson Problem (TSP) is one of the most famous problems in Computer Science. See wikipedia for a good discussion.
- The input to the problem is a list of
n
city locations.
- The locations of the above points are given by the list
cities
.
cities = [ (281, 234), (515, 321), (738, 44), (530, 60), (410, 377), (135, 293),
(883, 158), (366, 307), (380, 166), (881, 34) ]
- A solution to the TSP problem determines the best tour of the cities.
- A tour indicates how to go from city to city in a way that never revisits any city except for finally going back to the start city.
- The distance between two cities is the length of the edge that directly connects them. This type of distance is known an Euclidean distance.
- The best tour is the one that has the least distance of all possible tours.
- A tour is stored as an arrangement of indices from 0 through
n-1
,
- What is intriguing about the TSP problem is that no one knows whether it is possible to quickly guarantee finding an optimal tour. Most Computer Scientists guess that it is not possible to quickly guarantee an optimal tour.
- The above tours are gotten using the below orderings.
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
- Implement six functions to assist someone who is trying come with a heuristic strategy to generate a good solution.
Function d( cities, i1, i2 )
- Parameter
cities
is a list of points; where a point is an pair of x-coordinate and y-coordinate values.
- Parameters
i1
andi2
are indexes intocities
.
- The function returns the Euclidean distance between cities
i1
andi2
.
- Suppose
x1
andy1
are the coordinate values for cityi1
.
- Suppose
x2
andy2
are the coordinate values for cityi2
.
- The distance between the two cities is
- The Python exponentiation operator
**
allows decimal operands. So, it can be used for both squaring and square rooting.
- The built-in tester should produce the following output
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 )
- Parameter
tour
is an arrangement (list) of the integers in therange( 0, n )
.
- The function swaps the values at
tour[ i1 ]
andtour[ i2 ]
- The built-in tester should produce the following output
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 )
- Parameter
w
is a width, and parameterh
is a height.
- The function returns a random coordinate
( x, y )
, wherex
is a random value from therange( 0, w )
andy
is a random value from therange( 0, h )
.
- The built-in tester should produce the following output
testing random_location()
w: 1000
h: 500
random_location( w, h ): (355, 250)
Function initialize_city_locations( n, w, h )
- The functions returns a list
cities
composed ofn
random locations, where
- The x-coordinate of every location is from the
range( 0, w )
.
- The y-coordinate of every location is from the
range( 0, h )
.
- The function uses a loop to accumulate the
n
locations.
- Each iteration the function makes use of function
random_location()
to generate another location.
- The new location is appended to the
cities
list.
- The built-in tester should produce the following output
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 )
- Parameter
cities
is a list of points.
- Parameter
tour
is an arrangement of indices intocities
.
- The function accumulates and returns the sum of distances from the first city to the second city, the second city to the third city, the third city to fouth city, and so on. Plus the distance from the last city to the first city.
- Suggested algorithm
Set
n
to number ofcities
.Initialize accumulator to
0
.For
i
in the interval0
...n-2
doSet
a
andb
to be respectively thei
th andi+1
thtour
entries.Add to the accumulator the distance between the
a
th andb
thcities
entries.Set
a
andb
to be respectively the0
th andn-1
thtour
entries.Add to the accumulator the distance between the
a
th andb
thcities
entries.
- The built-in tester should produce the following output
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 )
- Parameter
cities
is a list of points.
- Parameter
tour
is an arrangement of indices intocities
.
- Parameters
i1
andi2
and are indices.
- The function performs the following actions
- Computes the cost
c1
of the currenttour
.
- Performs a swap of the of
tour
elements at indicesi1
andi2
.
- Computes the cost
c2
of the newtour
.
- If
c2
is less thanc1
, the function returnsTrue
. Otherwise, the function reswapstour
elements at indicesi1
andi2
(thus, restoring the better solution) and returnsFalse
.
- The built-in tester should produce the following output
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
🦆 © 2022 Jim Cohoon | Resources from previous semesters are available. |