CIT 590 Assignment 4: Cities

Spring 2010, David Matuszek

- To get you started pair programming
- To give you some experience with dictionaries and sets
- To give you more practice with writing tests
- To get you started thinking about how to solve problems with programs

Suppose there are a number of "cities," as in Figure 1 below. The distance between any
two cities is the standard Euclidian distance, that is,
√((x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}).
There are two problems to be solved.

Figure 1, Cities. |
Figure 2. A circuit. |
Figure 3. A spanning tree. |

A travelling salesman wishes to visit every city exactly once, then return to his starting point. (It doesn't matter what city is the starting point.) Such a path is called a circuit, as in Figure 2. However, the salesman also wishes to minimize the total distance that must be travelled.

A telegraph company wishes to put telegraph lines between cities, such that every city is connected (however indirectly) to every other city, with no circuits. Such a set of connections is called a spanning tree, as in Figure 3. To keep costs down, the company wishes to minimize the total distance that it must put wires.

(If you don't like telegraphs, call it electric power lines, or road building, or fiber optic cables.)

These are classic computer science problems, known as the **Travelling Salesman problem** and the **Minimum Spanning Tree problem**. You can find algorithms for solving them on the web, and you are welcome to look at those algorithms. However, I want you use a hill climbing approach, where you start with "any" solution, and try to progressively improve it until you can't improve it any more.

This should require *you* to think about how to solve the problem, rather than just copying some algorithm you may or may not understand. Your final solution is unlikely to be the optimal (best possible) solution, but that's okay, so long as it isn't obviously terrible.

There will be from 1 to 26 cities, with names` "a"`

, `"b"`

, `"c"`

, etc. Each city will have an x-y location, which is a 2-tuple of floating point numbers, such as `(743.02, 215.53)`

, where each number is between `0.0`

and `1000.0`

. When I use the term * directory* in the function descriptions below, it will refer to a

To represent either a circuit or a spanning tree, use a **dictionary** whose **keys** are city names, and whose **values** are a **set** of the names of the directly connected cities. In the function descriptions below, I will call this kind of dictionary a * road_map*. For a circuit, each set will contain exactly two city names; for a spanning tree, each set will contain one or more city names.

While I will require these particular data representations as function parameters and function results, this does not imply that you have to work with these representations as you solve the problems. Python makes it easy to convert from one kind of sequence to another.

`cities.py`

)`def create_cities(how_many)`

- Given a number between 1 and 26, inclusive, creates that many cities, and returns them as a
.`directory`

`def print_cities(`

*directory*)- Prints a list of cities, along with their locations. Print only one or two digits after the decimal point.
`def create_cycle(`

*directory*)- Returns a
that describes an initial (probably not very good) cycle.`road_map`

`def create_spanning_tree(`

*directory*)- Returns a
that describes an initial (probably not very good) spanning tree.`road_map`

`def compute_cost`

~~(~~(*map*)*road_map*,*directory*)- Returns, as a floating point number, the sum of the distances of all the connections in the
`road_map`

`.`

`def improve_cycle`

~~(~~(*map*)*road_map*,*directory*)- Tries to modify the
to be slightly better (have a lower cost) and returns`road_map`

`True`

if it succeeds,`False`

if no further improvement can be found. This may involve trying many small changes, until one is found that reduces the total cost of the cycle. It is*your*job to figure out how to do this. (You do not have to return the; since it is an object, any changes you make will be seen in the calling function.)`road_map`

`def improve_spanning_tree`

~~(~~(*map*)*road_map*,*directory*)- Tries to modify the
to be slightly better (have a lower cost) and returns`road_map`

`True`

if it succeeds,`False`

if no further improvement can be found. This may involve trying many small changes, until one is found that reduces the total cost of the spanning tree. It is*your*job to figure out how to do this. (You do not have to return the; since it is an object, any changes you make will be seen in the calling function.)`road_map`

`def find_best_cycle`

~~(~~(*map*)*road_map*,*directory*)- Improves the given
until you can find no further improvements. This does not need to be the best possible solution; it only needs to be "reasonably good." (You do not have to return the`road_map`

; since it is an object, any changes you make will be seen in the calling function.)`road_map`

`def find_best_spanning_tree`

~~(~~(*map*)*road_map*,*directory*)- Improves the given
until you can find no further improvements. This does not need to be the best possible solution; it only needs to be "reasonably good." (You do not have to return the`road_map`

; since it is an object, any changes you make will be seen in the calling function.)`road_map`

`def print_map`

~~(~~(*map*)*road_map*,*directory*)- Prints, in an easily understandable format, the cities and their connections, along with the cost for each connection and the total cost.
`def main()`

- Creates some number of cities (ask the user how many) and prints them out, creates the "best" cycle and prints it out, and creates the "best" spanning tree and prints it out.

`cities_test.py`

)All functions, except the `main()`

function and the two `print`

functions, should be tested. This includes any additional functions you might write.

**TDD**, **Test Driven Design**, *really is* a good idea. Here is the general approach:

- Write a stub for each function. (A stub is a function that does nothing or, if it must return a value, returns a value that is unlikely to be correct.)
- Pick a function--if possible, one that does not depend on any other functions you haven't yet written--and write a test for it. Run the test and make sure it fails.
- Improve the function just enough to make it pass the test.
- If the function needs to do more, then expand the test (or add another test) to test the new functionality. Run the test and make sure it fails. Then return to step 3. Repeat as many times as necessary until the function is complete.
- If any functions remain to be written, return to step 2.

Put both names (yours and your partner's) in a comment at the top of both files. You may, if you wish, put your name in a comment in the major functions you have written; but you will both get the same grade for the assignment.

This assignment has been written to have a common part, and two easily separable problems. You should work with your partner as much as possible; but if you must work apart, one of you should work on the travelling salesman problem, and the other should work on the spanning tree problem.

In the past, some students have tried the following: One partner writes the functions, and the other partner writes the test. Those students have told me, in no uncertain terms, that* this is a bad idea. *Learn from their mistakes. Whoever writes a function should also write the tests for that function.

- Import random at the top of your program; then
`number = 1000 * random.random()`

will give you a floating-point number in the range`0.0 <= number < 1000.0`

. - Figure out what happens when you convert a dictionary to a list.
- The
`%`

operator (check your textbook) is a good way to print out floating-point numbers, for example, with the format`%6.2f`

. `ord('a')`

is`97`

;`chr(97)`

is`'a'`

; and similarly for other letters.- If you haven't yet read my Unit testing and TDD handout (linked to from the course home page), now would be a good time to do so.

The assignment will be graded on the basis of 100 points total. You and your partner will receive the same grade. Grading will be based on:

**Correctness.**We will have*our own unit tests,*which your functions must pass. This means that (1) the above functions must take parameters and produce results*exactly*as specified, or our test will fail and cost you points, and (2) your own unit tests should be good enough to catch any errors before we do.**Style.**Use proper indentation (4 spaces) and proper spacing. Use good, self-explanatory variable and function names. Don't repeat code if you can put it in a function and just call the function. Don't use "magic numbers" (unexplained constants in your code); give them names. Try to avoid redundancy (such as the beginner's`if better == True`

).