## Class 40 — Friday May 7

#### One more chance to be a class

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

### Project — Traveling Salesperson Problem assistance

#### 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.

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

• 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` 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.3880386967452

#### 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 function does not do a return.
• 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 parameter `h` is a height.
• The function returns a random coordinate `( x, y )`, where `x` is a random value from the `range( 0, w )` and `y` is a random value from the `range( 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 of `n` 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 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 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.652320335747

#### 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` and are indices.
• 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]

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