TSP
After totally misjudging the cost of fuel I realized that we’re going to have to do our tour on a budget. I think we can pull it off without skipping any destinations if we can find a shorter route. One thing that could help is if we eliminate crossings in the tour. If there are two segments that cross, we can swap the ends of the segments and reverse everything in between to get a new tour that’s shorter and still visits all the same places. To pull this off, we’re going to want to have a data structure that stores an ordered list, but can easily reverse a sublist. A doubly linked list could be a good choice here. We’d like our Tour class to support the new operation fixcrossing that takes two cites as input, checks if there is a crossing at the tour segments starting at those cities, and uncrosses them if so. Be careful that you reconnect the tour in the right order.
To make it easier to test (both for you and for me), we’ll add a public method twist that takes two cities as input and swaps their end points reversing the list between them. This should preserve all the nodes, only changing their order. For example, if we have a list of city names such as [A,B,C,D,F,G,H,I,J] , then calling twist(‘C’,’G’) results in the list being reordered to look like [A,B,C,G,F,D,H,I,J] .
Getting the desired stop
On their own, linked lists don’t have fast direct access to the specified node, as opposed to lists which can access items in O(1) time from an index or dictionaries, which can access values in O(1) time from a key. Consider augmenting your Tour or your Doubly Linked List class with a dictionary to quickly access a tour stop from the name of the city. You may assume that we will not be revisiting any city more than once (not counting the return to the starting city at the very end of the tour).
Lazy Reversal
Notice that we made a rather glaring omission when we designed our Tour class. Although it’s possible to add stops to the tour, we didn’t give any way to access the cities
in the tour. Let’s fix that. Let’s add a generator that allows one to iterate through the cities in the tour. Let’s also make it so that this is the only public way to access the stops on the tour.
Recall that a simple iterator for a linked list would look like the following.
def __iter__(self):
current = self._head
while current is not None:
yield current.data()
Make such an iterator for the Tour class that iterates through the cities in the stops.
Once implemented, your Tour iterator will allow code such as the following.
tour = Tour() for citystring in ['Albuquerque,NM,35.08,106.65',
'Amarillo,TX,35.18,101.83',
'Anchorage,AK,61.22,149.90']
city = City(citystring)
tour.addpossible_stop(city)
tour.addstop(city.name())
for city in tour:
if city.longitude() > 75:
print("Too West!")
Notice that if you implement the tour with a doubly linked list, you can do the reversal in a lazy way. It’s possible to store a variable in the nodes that indicates if there is a change in which link points forward and which link points backwards. As a challenge, see if you can figure out this trick to implement twist in constant time.
A Classic Problem
The problem of finding the shortest tour that visits a set of places and returns back to the start is a classic problem call The Traveling Salesman Problem or TSP for short. It’s a notoriously hard problem in computer science and is in a class of computational problems we call NP-Hard. You will study such problems in both Theory of Computation (3502) and
Algorithms (3500). These are some problems where we do not expect to find solutions where the running time is bounded by a polynomial in the size of the input. This means, that not only do we not expect to find an O(n) or O(n^2) algorithm, we don’t even expect to find an O(n^{100}) algorithm. Actually, if you found an algorithm that runs in O(n^{100}) time and finds the shortest possible tour, you would win a million dollars courtesy of the Clay Mathematics Insitute (http://www.claymath.org/millennium-problems). Still, that shouldn’t stop us from looking for good heuristics (or approximations) that often do well.
Summary of things to do (not necessarily in the order to do them)
- Implement fixcrossing and twist on the Tour class. You will probably want to implement the twist operation first on your doubly linked list and then call that method from the Tour.twist method. Feel free to edit or even rewrite the
DoublyLinkedList class I provided if it helps you.
- Use a dictionary to make sure the operations run in time proportional to the length of
the reversed portion of the list.
- Write an iterator for the Tour class to iterate through the cities on the tour.
- As an extra challenge, see if you can make twist work in constant time by modifying
the iterator.
- As a fun puzzle, see if you can prove that removing a crossing always reduces the
length of the total tour. This would mean that repeatedly removing crossings would eventually terminate.