20-CS-122-001 | Computer Science II | Spring 2012 |
---|---|---|
Homework Assignment 2 |
Minimum Cost Network
Due: April 14, 2012
(submit instructions: here)
It may seem to some of you that this problem is asking too much given your limited programming skills at this point. Please try it anyway. You should be able to produce some kind of solution, even if it is not efficient, based on a simple use of arrays. Later in the course we will revisit this problem to show how many different ways it can be solved and to investigate the efficiency of each approach. You will be amazed how much faster one version is than another. We will probably do a fair amount of programming this quarter and I thought this would be a great problem to start out with.
If you feel over-challenged by the problem below, read In Case of
Trouble at the end of this page.
Use class objects in a meaningful way. Use
arrays in a non-trivial way to represent data elements that can be
used to make tests on the structure of a dynamic data base. Read
input data from a file; make multiple passes through the data file
to avoid using constants to establish memory for data structures. Use
qsort; implement a function required as input to
qsort for comparison.
Write a program to solve the Minimum Cost Network Problem. This
problem and an outline of the code you can write are as follows:
Given a collection of n cities and the cost of routing cable
between every pair of cities, find the minimum cost network of cables
that allows a person in one city to connect with a person in any other
city. Network cost is the sum of the costs of all cables used.
Cables must be laid between cities. Cables connect only at cities
(splicing of a crossing pair of cables between cities is not allowed).
A person in city x can connect with a person in city y
only if there is a sequence of distinct cities c_{1} ,
c_{2} , ..., c_{j} , none of which are
either x or y, such that cables are laid between x and
c_{1} , between c_{1} and
c_{2} , ... , between c_{j} and y.
Such a sequence is called a path between x and y.
The following is a table showing fictitious costs of laying cable between pairs of four familiar cities.
Cleveland | Columbus | Cincinnati | Chicago | |
Cleveland | - | 120 | 96 | 300 |
Columbus | 120 | - | 43 | 178 |
Cincinnati | 96 | 43 | - | 200 |
Chicago | 300 | 178 | 200 | - |
For the above example, the minimum cost network consists of three
cables: one connecting Cleveland to Cincinnati, one connecting
Cincinnati to Columbus and one connecting Columbus to Chicago, for a
total cost of 317. In general, there are n-1 cables in a
minimum cost network connecting n cities.
input: A collection of cable costs between pairs of cities
output: A network of cables of minimum cost
1. Order the cables by increasing cost. 2. Let N represent the network of cables to be output and make it empty. 3. Repeat the following until all the cables are considered. 3a. Choose the next cable c in the ordered list. 3b. Check whether including c in the solution N allows you to trace more than one path between some pair of cities using only cables already placed in N. 3c. If it does, forget c and continue the loop. 3d. Otherwise, include c in N. 4. Return N.
class Cable { public: int city1, city2, cost; };For purposes of this homework the Cable class will have the same effect as
typedef struct { int city1; int city2; int cost; } Cable;
class Cable { public: int city1, city2, cost; }; ... const int MAX_CABLES = 1000; ... Cable cables[MAX_CABLES];to make a Cable array. Instead use something like this:
class Cable { public: int city1, city2, cost; }; ... fstream fin; fin.open(argv[1],ios::in); ... int ncables = findNumberCablesInFile(fin); Cable *cables = new Cable[ncables];
Here is more detail. Suppose the first chosen cable connects cities c_{i} and c_{j} and these cities are assigned numbers i and j, respectively, and i < j. Then, as part of step 3a., change the number assigned to c_{j} to be i. The fact that cities c_{i} and c_{j} have the same number means they are connected by a path (namely the cable). The fact that they have a number different from all other cities means there is no path from either of these two to any of the other cities.
For each cable remaining in the list, as it is chosen in step 3a., determine the numbers assigned to each of the cities the cable connects. If the numbers are the same, the cities are already connected by at least one path through cables in N. Hence, in this case, in step 3c. this cable is not added to N. However, if the numbers are different, then the two cities are not connected by the cables in N so, in step 3c. this cable is added to N. This fact can be recorded as follows. Some cities are assigned the same number as that of the highest numbered city the cable connects. Reassign the numbers of those cities to equal the number of the lowest numbered city the cable connects. Thus, at the beginning of step 3a., each time through the loop, all same numbered cities are connected and different numbered cities are not connected by paths through cables in N.
If the above idea is too much for you at the moment, use some brute force search that considers all possible networks (there are n! such networks - that is, n factorial, not n!), keeps track of the total costs, then outputs the lowest cost network considered. If you run such a program on all the cities in the USA, go for coffee, rather to lunch...do not wait for a result - you will die first.