A problem about trees

Правка en2, от haleyk100198, 2017-02-15 09:42:07

Recently I have came across thinking about this question, and this is the formal version of the problem:

Given a tree, with some of the nodes labelled with a group number. If we start from the root of the tree, what is the minimum amount of edge that we have to come across to visit at least one node from each group? In case if you are traversing an edge more than once, it must be counted multiplely.

For a better understanding, this is the scenario that I have came acrossed IRL. During a physics experiment related to centripetal force, I have to place a different amount of mass (which is guaranteed to be a combination of some weight provided by the lab, but the combination is not guaranteed to be unique) in order to test the relation between mass and force. Since I am a clumsy person and adjusting the amount of mass may affect the radius of the circular motion and induce more errors to the experiment result, I want to reduce the amount of times that I have to replace the weights to minimize the error while still able to get all required combination of mass for my lab report. In particular, the mass holder holds mass in a stack style, so I can't just reach a state and then just jump back to the root state.

I know this problem could be solved by bitmask dp, but the exponential time complexity is rather disgusting, so I am thinking if using tree algorithms could help improve it (Though generating the tree also has a poor time complexity — but at least now solving how to reach at least one node from each group sounds engaging and useful). I've been thinking about LCA but it doesn't seem to get too much better. Would someone share some thoughts on how to solve the problem in a "faster" way?

I am also thinking about variations about this question such as not requiring to go back the root node (heck, I will just leave the mass on the holder for the lab workers to pack them), or starting from an arbitary root node (The last group may just be as lazy as me and decides to leave the mass on the holder, but now I am just considering that I am starting with the zero state). In case if someone solved the original version of the problem in polynomial time complexity, I would also like to learn how to solve the problem for these variations of the problem.

Теги randomthoughts, tree, dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский haleyk100198 2017-02-15 09:42:07 31
en1 Английский haleyk100198 2017-02-15 09:40:51 2297 Initial revision (published)