Homework 31 — Traveling Salesperson Problem support
Due Friday December 3
Files
- Module support.py
- Tester test_support.py
Your 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
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.4
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 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 inclusive 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.7