Tree Matching solved with dynamic programming
Let's define :
$dp(P,0)$ : The max matching number that DOES NOT INCLUDE node P.
$dp(P,1)$ : The max matching number that INCLUDES node P.
Therefore, the max matching set size at node P will be $max[ dp(P,0) , dp(P,1) ]$
Then, let's go more deeper. How can we define $dp(P, 0)$?
It will be the max matching number of all the trees starting at the children nodes ($C_1, C_2...$) of node P. That is:
$$dp(P,0) = \sum_{i \in children}max[ dp(C_i, 0), dp(C_i, 1)]$$
$dp(P, 1)$ will be selecting a children node and calculate its optimal, then loop through all the children nodes and compare which children node picked will be the maximum.
$$dp(P,1) = \underset{t \in children}{max}\left ( \left \{ \sum_{i \in children}max[ dp(C_i, 0), dp(C_i, 1)]\right \} - max[ dp(C_t, 0), dp(C_t, 1) ] + dp(C_t,0) + 1 \right )$$
$$=\underset{t \in children}{max}\left ( dp(P,0) - max[ dp(C_t, 0), dp(C_t, 1) ] + dp(C_t,0) + 1 \right ) $$
No comments:
Post a Comment