Class 41 — Friday, December 3

Another chance to be a class

Dream big and work hard — Celebrate diversity — Always pay forward

---

Look both ways

• Back and ahead

---

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 into cities.

• Parameters i1 and i2 are indices to tour

• The function performs the following actions

• Computes the cost c1 of the current tour.

• Performs a swap of the of tour elements at indices i1 and i2.

• Computes the cost c2 of the new tour.

• If c2 is less than c1, the function returns True. Otherwise, the function reswaps tour elements at indices i1 and i2 (thus, restoring the better solution) and returns False.

• 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]

 

---