data留学生程序讲解、辅导c/c++，Java编程语言、system辅导
- 首页 >> Matlab编程 26 (100 pts.) DynCraft
You’re in charge of setting up some gold mining infrastructure within an underground cave system.
The cave system can be modeled as a directed tree. It consists of N chambers. The root is the
entrance to the cave system, the chamber s. Each chamber is connected to at most 3 subtrees (a
ternary rooted tree!).
The quantity of gold in each chamber u is denoted by a function g(u).
To mine for gold and bring it up to the entrance, you need to place conveyor belts in the corridors
connecting the cave chambers. You have a limited number of L conveyor belts, L = O(N). If you
place a conveyor belt in a corridor connecting u to v, then it can carry gold from v to u towards
the entrance. You can mine all the gold from all of the chambers that can reach the entrance
through a path of conveyor belts.
The following is an example with three belts, and two dierent
solutions. Here, the root has value
0 associated with it. Here, the first solution has a better value than the second solution.
Give a dynamic programming algorithm that determines the optimal way to place the L conveyor
belts in order to mine the largest amount of gold.
Solution:
This is a standard dynamic programming problem on trees.
We can define each subproblem as F(u, `), which denotes the amount of gold that can be
brought up to chamber u by placing exactly ` conveyor belts, one of them has to connect u with
its parent.
At each tree, we have to choose how to allocate conveyor belts to the subtrees, that is we
have to choose among `1, `2, `3 such that `1 + `2 + `3 `. There are O(`2) such choices. We get
the recurrence:
Assume the vertices of the tree are numbered 1 to N, and s = 1. Let NULL = 0. Let
child(v, i) be a function that returns the ith child of the node v. If no such node exists, it
returns NULL.
otherwise.
Here is a pseudo-code for solving this using explicit-memoization:
return
The total number of subproblems is LN = O(N2). The time to compute each subproblem
will be O(N2) due to searching over `1 + `2 + `3 = `. As such, the overall running time is
O
⇣
(# subproblems) · (time per subproblem)
⌘
= O(N2 · N2
) = O(N4
).
The desired optimal solution value is ↵ = F(s, L + 1).
After computing all the optimal values, V [·, ·], recovering the optimal solution is easy.
continue
if V [v, `] = g(v) + V [child(v, 1), `1] + V [child(v, 2), `2)] + V [child(v, 3), `3] then
recoverOpt(v, child(v, 1), `1)
recoverOpt(v, child(v, 2), `2)
recoverOpt(v, child(v, 3), `3)
return
5
We call recoverOpt(NULL, v, `) to recover the optimal solution.
A faster solution is possible by rewriting the tree as a binary tree, with new fake edges being
“free”. The running time then improves to O(N3). An even faster algorithm should follow by
using separator node in the tree, but this is outside the scope for this class (and the analysis
looks messy in this case, but it probably leads to a near quadratic time algorithm in this case).
27 (100 pts.) Max Norm Suppose you have a directed graph with n vertices and m edges, where
each edge e has weight w(e), and no two edges have the same weight. Here, you can assume that
the graph is sparse, say, m = O(n log n). For a cycle C with edges e1e2 ··· e`, define the max-norm
of C to be
f(C) = max{w(e1), w(e2), ..., w(e`)}/`.
27.A. (20 pts.) Let f ⇤ be the maximum max-norm of any closed walk W in the graph. Show that
there is a simple cycle C such that f(C) = f ⇤. A simple cycle can visit a vertex at most
once.
Solution:
Let C be a cycle with the maximum f(C). If there is more than one such optimal
cycle, pick the one with the smallest number of edges. Let e1, e2,...,e`, e1 be its edge
sequence, where without loss of generality e1 is the edge with the most weight (the cycle
is the same if we simply rotate the indexes around). Suppose that a vertex is repeated.
Then the end vertex of ei is equal to the start vertex of ej for some j>i + 1. The cycle
e1,...,ei, ej , ej+1,...,e`, e1 has the same maximum edge weight, but fewer nodes, hence it
is has a greater max-norm, a contradiction.
27.B. (80 pts.) Give an algorithm that finds the cycle with largest max-norm as quickly as possible.
6
Solution: We compute for every pair of vertices u, v 2 V(G) their hop distance h(u, v)
– that is, the minimal number of edges in a path from u to v. This can be computed in
O(n(n + m)) time, by doing BFS from each vertex of the graph. Here h(u, v) = NULL, if
there is not path from u to v, where NULL is a special value indicator.
Now, for each edge u ! v in the graph, we compute the candidate value
(u,
v) = w(u ! v)
h(v, u)+1.
Here if h(u, v) = NULL, then we set (u,
v) = NULL.
The algorithm returns the maximum value h(u, v) computed that is not NULL, overall
vertices u, v 2 V(G). If all the computed values of h(·, ·) are NULL, the algorithm prints
“Oh no”, apologizes, throw a tantrum, and then do a core dump.
The running time of the algorithm is O(n2 + nm).
Lemma 9.2. The above algorithm returns the correct value.
Proof: If there is no cycle in the graph, then the algorithm detects it, and apologizes.
Otherwise, observe that any (u,
v) that is not NULLis a valid value of some cycle. Consider
the optimal cycle C, with e = u ! v be its heaviest edge. Clearly, h(v, u) = |C|
1,
which readily implies that the algorithm computes the right value.
7
You’re in charge of setting up some gold mining infrastructure within an underground cave system.
The cave system can be modeled as a directed tree. It consists of N chambers. The root is the
entrance to the cave system, the chamber s. Each chamber is connected to at most 3 subtrees (a
ternary rooted tree!).
The quantity of gold in each chamber u is denoted by a function g(u).
To mine for gold and bring it up to the entrance, you need to place conveyor belts in the corridors
connecting the cave chambers. You have a limited number of L conveyor belts, L = O(N). If you
place a conveyor belt in a corridor connecting u to v, then it can carry gold from v to u towards
the entrance. You can mine all the gold from all of the chambers that can reach the entrance
through a path of conveyor belts.
The following is an example with three belts, and two dierent
solutions. Here, the root has value
0 associated with it. Here, the first solution has a better value than the second solution.
Give a dynamic programming algorithm that determines the optimal way to place the L conveyor
belts in order to mine the largest amount of gold.
Solution:
This is a standard dynamic programming problem on trees.
We can define each subproblem as F(u, `), which denotes the amount of gold that can be
brought up to chamber u by placing exactly ` conveyor belts, one of them has to connect u with
its parent.
At each tree, we have to choose how to allocate conveyor belts to the subtrees, that is we
have to choose among `1, `2, `3 such that `1 + `2 + `3 `. There are O(`2) such choices. We get
the recurrence:
Assume the vertices of the tree are numbered 1 to N, and s = 1. Let NULL = 0. Let
child(v, i) be a function that returns the ith child of the node v. If no such node exists, it
returns NULL.
otherwise.
Here is a pseudo-code for solving this using explicit-memoization:
return
The total number of subproblems is LN = O(N2). The time to compute each subproblem
will be O(N2) due to searching over `1 + `2 + `3 = `. As such, the overall running time is
O
⇣
(# subproblems) · (time per subproblem)
⌘
= O(N2 · N2
) = O(N4
).
The desired optimal solution value is ↵ = F(s, L + 1).
After computing all the optimal values, V [·, ·], recovering the optimal solution is easy.
continue
if V [v, `] = g(v) + V [child(v, 1), `1] + V [child(v, 2), `2)] + V [child(v, 3), `3] then
recoverOpt(v, child(v, 1), `1)
recoverOpt(v, child(v, 2), `2)
recoverOpt(v, child(v, 3), `3)
return
5
We call recoverOpt(NULL, v, `) to recover the optimal solution.
A faster solution is possible by rewriting the tree as a binary tree, with new fake edges being
“free”. The running time then improves to O(N3). An even faster algorithm should follow by
using separator node in the tree, but this is outside the scope for this class (and the analysis
looks messy in this case, but it probably leads to a near quadratic time algorithm in this case).
27 (100 pts.) Max Norm Suppose you have a directed graph with n vertices and m edges, where
each edge e has weight w(e), and no two edges have the same weight. Here, you can assume that
the graph is sparse, say, m = O(n log n). For a cycle C with edges e1e2 ··· e`, define the max-norm
of C to be
f(C) = max{w(e1), w(e2), ..., w(e`)}/`.
27.A. (20 pts.) Let f ⇤ be the maximum max-norm of any closed walk W in the graph. Show that
there is a simple cycle C such that f(C) = f ⇤. A simple cycle can visit a vertex at most
once.
Solution:
Let C be a cycle with the maximum f(C). If there is more than one such optimal
cycle, pick the one with the smallest number of edges. Let e1, e2,...,e`, e1 be its edge
sequence, where without loss of generality e1 is the edge with the most weight (the cycle
is the same if we simply rotate the indexes around). Suppose that a vertex is repeated.
Then the end vertex of ei is equal to the start vertex of ej for some j>i + 1. The cycle
e1,...,ei, ej , ej+1,...,e`, e1 has the same maximum edge weight, but fewer nodes, hence it
is has a greater max-norm, a contradiction.
27.B. (80 pts.) Give an algorithm that finds the cycle with largest max-norm as quickly as possible.
6
Solution: We compute for every pair of vertices u, v 2 V(G) their hop distance h(u, v)
– that is, the minimal number of edges in a path from u to v. This can be computed in
O(n(n + m)) time, by doing BFS from each vertex of the graph. Here h(u, v) = NULL, if
there is not path from u to v, where NULL is a special value indicator.
Now, for each edge u ! v in the graph, we compute the candidate value
(u,
v) = w(u ! v)
h(v, u)+1.
Here if h(u, v) = NULL, then we set (u,
v) = NULL.
The algorithm returns the maximum value h(u, v) computed that is not NULL, overall
vertices u, v 2 V(G). If all the computed values of h(·, ·) are NULL, the algorithm prints
“Oh no”, apologizes, throw a tantrum, and then do a core dump.
The running time of the algorithm is O(n2 + nm).
Lemma 9.2. The above algorithm returns the correct value.
Proof: If there is no cycle in the graph, then the algorithm detects it, and apologizes.
Otherwise, observe that any (u,
v) that is not NULLis a valid value of some cycle. Consider
the optimal cycle C, with e = u ! v be its heaviest edge. Clearly, h(v, u) = |C|
1,
which readily implies that the algorithm computes the right value.
7