Class 40 — Wednesday, December 1

Chrestomathics

Let's go on a tour – Travel city to city – Then come back to home

---

Look both ways

• Back or ahead

---

Agenda

• Review Test 2

• Continue work on TSP support

---

• Downloads

• Test 2 test-2-answers.py

• Module support.py

• Tester test_support.py

---

Computing grade

• If you do not take test 3

• Your grade will be computed with a denominator of 82.

• The numerator will be based on your homework average (16%), test 1 average (33%), and test 2 (33%).

• If you do take test 3

• Your grade will be computed with a denominator of 100.

• The numerator will be based on your homework average (16%), test 1 average (33%), test 2 (33%), and test 3 average (18%)

• You must tell by next Monday whether you will take test 3. A form will be posted next class.

---

TSP recap

• The Traveling Saleserson 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.

• 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 are of the mind that it is not possible to quickly guarantee an optimal tour.

 

---

Task

• Implement three 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 and i2 are indexes into cities.

• The function returns the Euclidean distance between cities i1 and i2.

• Suppose x1 and y1 are the coordinate values for city i1.

• Suppose x2 and y2 are the coordinate values for city i2.

• 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.4

---

Function swap( tour, i1, i2 )

• Parameter tour is an arrangement (list) of the integers in the range( 0, n ).

• The function swaps the values at tour[ i1 ] and tour[ 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 cost( cities, tour )

• Parameter cities is a list of points.

• Parameter tour is an arrangement of indices into cities.

• 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 of cities.

Initialize accumulator to 0.

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

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

  Add to the accumulator the distance between the a^th and b^th cities entries.

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

Add to the accumulator the distance between the a^th and b^th cities 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.7

 

---