 We can think of a computer network as a undirected graph where nodes
represent routers and edges represent connections between the routers.
In this network, there are a number of packets, each of which has a
source and a target. Over a number of discrete time steps, each
packet must travel from its source to its target. During one time
step, a packet at router u may move to router v, if
there is a link between u and v. However, only one
packet may use a link between u and v during a
particular time step (if one packet uses a link to go from u
to v, no other packet can use that link to go from v
to u during the same time step). The problem is to figure
out the best way to route the packets through the network so that they
get to their destinations as soon as possible.
You will be given an int, 2<=N<=100,
representing the number of nodes in the graph. A
String[], g will specify the edges (up to 4950
of them), where each element is of the form "u v",
where u and v are distinct integers between 0 and
N1, inclusive, indicating an edge between node u and node
v. There will be at most one edge between a pair of nodes. A
String[], packets, will specify the packets to be
sent in the network, where
10<=packets<=2,000. Each element
will be formatted as "s t", indicating a packet
with source s and target t, where s does not equal t. These graphs will be
randomly generated as described at the end of the problem
statement. Furthermore, the graphs will be connected.
Your task is to come up with a routing plan for the packets through the
network. You should return a String[], each element of
which represents the locations of the packets after each time step. Each
element of the String[] should be a space delimited list
of the packets' locations at a time step corresponding to the index of
the element (the first element of the return corresponds to the
locations of the packets after the first time step). The list should
give the locations in the same order that the packets are given to
you.
For example, consider the simple network with 2 nodes and 2
packets:
N=2
g={"0 1"}
packets={"0 1","1 0"}
In this case, there are two packets trying to go in opposite
directions along the one link. One possible return would be:
{"0 0","1 0"}
This indicates that in the first time step, the second packet moves
along the link from node 1 to node 0. Since that link is in use, the
first packet cannot also use it, so during the second time step, the
first packet moves from node 0 to node 1, and at this point all
packets have reached their destinations. Another valid return would
be {"0 1","1 1","1 0"}. In this return, none of the packets moved
during the first time step. While valid, this is clearly
suboptimal.
Your program will be scored based on the quality of your method's return, and
the time it takes your method to execute. If your method's return is
invalid in any way or if not all the packets reach their destinations,
you will get a 0. Otherwise, your score for a test case will be given
by:
quality^{2}  10 * execution time (quality is defined below, time is in seconds)
If the quality or the above formula turns out to be negative, the score is set to 0. Your overall score will be the sum over all test cases
of SCORE/OPT, where OPT is the highest score anyone has achieved on a
test case (0/0 = 1 here). Thus, if you score 10 on one test case, and someone else
scores 20 on the same test case, you will get 10/20 = 0.5 towards your
final score for that test case.
The quality term used above will be the percent improvement
of your solution over a naive solution that routes packets over a
random shortest path. In the naive solution, if a packet is being routed
to node v, and is currently at node u, then a node
is chosen at random out of all nodes that are on some shortest path
from u to v and are also connected to u. The packet will eventually be sent
from u to that node, with conflicts along the link resolved
by letting a random packet use the link.
Finally, there are dozens of realistic and interesting classes of
graphs that could be randomly generated and used here. One class that has drawn a
great deal of interest in recent years is adhoc networks. To simulate these
graphs, we will first select a random value for N, the number
of nodes. Each node will then be assigned a random x and y value in a
cartesian plane, at a distance of no more than 50 from the origin.
Then, we will select random values for the lower and upper bounds on
each node's range (5<=lower<upper<30). Each node will be
assigned a range uniformly between these bounds. Two nodes will be
able to communicate if their distance from each other is less than both their ranges. If
the network generated is not connected, it will be scrapped and a new attempt will be made.
Otherwise, a random number of packets will be generated, the sources
and sinks of which are random. Here is pseudocode to generate a graph. The notation [x,y] indicates a random value between x and y, inclusive (the value is floating point unless an integer is clearly required). Roughly 30% of generated graphs are connected.
N = [2,100]
lower = [5,30]
upper = [5,30]
if(upper < lower)swap(lower,upper)
for(i = 0 to N1){
do{
x[i] = [50,50]
y[i] = [50,50]
}while(x[i]*x[i]+y[i]*y[i] > 50*50);
r[i] = [lower,upper]
}
for(i = 0 to N  1){
for(j = 0 to i1){
if(dist(i,j) < range[i] && dist(i,j) < range[j]){
connected(i,j) = connected(j,i) = true
}
}
}
M = [10,2000]
for(i = 0 to M1){
do{
packets(i,0) = [0,N1]
packets(i,1) = [0,N1]
}while(packets(i,0) == packets(i,1));
}
