友情提示 递归算法简单但速度慢
请在两天内作答。
Elixent’s Placement Problem
Write a program (in C or C++) that places an arbitrary netlist represented as a directed graph G = (V, E) with vertices V and edges E over a 1D array of N processors:
p_1 p_2 p_3 ... p_N
Each vertex should be placed on a single processor and no processor can hold more than one vertex (you can assume there are as many processors as you need). For example vertex v_1 might be placed on processor p_1 and v_2 on p_4:
-----------
v_1 v_2
p_1 p_2 p_3 p_4 ... p_N
If there were an edge between v_1 and v_2, then it would automatically be routed along the 'shortest' path between the respective processors (as shown). The distance of this edge is 4-1 = 3. The cost of an overall placement is simply the sum of all edge distances. Placements with lower cost as these are 'better', but the computational complexity of your placement algorithm also matters (you might need to place very large netlists).
The graph should be read in from standard input in the form
10
1,3 2,4 4,5 ...
In the first line '10' gives the number of vertices, the second line defines which pairs of vertices are connected by edges (the first vertex is numbered 1).
The program should output the placement cost and results on standard output, giving the vertex allocated to each processor in turn, or - if a processor is empty. For example:
21
2 4 - 3 1 ...
would mean the placement cost was 21 and vertex 2 was allocated to p_1, 4 to p_2, p_3 was empty, 3 to p_4 etc.
You might optionally want to consider a more complex problem with a non-linear notion of cost that accounts for congestion in the case when there are multiple overlapping edges. For example, the cost function could be redefined as the sum of the squares of the number of edges spanning each pair of neighbouring processors. In this case the following configuration of edges:
--- ---
-----------
p_1 p_2 p_3 p_4 p_5 .... p_N
would have cost:
1 edge spanning p_1 to p_2
2^2 edges spanning p_2 to p_3
1 edge spanning p_3 to p_4
1 edge spanning P_4 to p_5
---
7
Again, lower cost is better, but computational complexity also matters.
