Class 39 — Monday, November 29

Chrestomathics

WWAHD — A strategy to embrace — I know that I do

---

Look both ways

• Back or ahead

---

Agenda

• Problem solving

• Computer Science

---

• Downloads

• Module setup.py

• Supports the generating of a random Traveling Salesperson (TSP) instance

• Tester test_setup.py

---

Discussion

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

• 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 are of the mind 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 ]

---

Your task

• Provide two functions that help with the creation of a random TSP instance.

---

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 time through the loop, 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)]

 

---