Class 41 — Friday, December 3
Another chance to be a class
Dream big and work hard — Celebrate diversity — Always pay forward
Look both ways
Agenda
- Chrestomathics
Downloads
- Module heuristic.py
- Tester test_heuristic.py
Test 3
- Form to indicate your intention to take Test 3
- The default is you are not taking Test 3. Students who want to take test 3 must indicate their intention before class on Monday, December 6.
Consider being a TA for CS 1112
- Departmental application
- All new TAs must take CS 2190 — an overview of computer science education. Topics include ethics, diversity, tutoring and teaching techniques, and classroom management.
Your task
- Implement a greedy stragegy that attempts to improve an existing TSP solution
Function consider( cities, tour, i1, i2 )
- Parameter
cities
is a list of points.
- Parameter
tour
is an arrangement of indices intocities
.
- Parameters
i1
andi2
are indices totour
- 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]