We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this-

$A[i', i, j', j] = \min \begin{cases} B[i', i-1, j', j] + c(i) \\ \min_{j_1 \le k \le j} \{A[i', p(i), j_1, k] + B[p(i) +1, i-1, k+1, j] + d \} \end{cases}$

$B[i', i, j', j] = min\begin{cases} B[i', i-1, j', j-1] + c(i,j) \\ A[i', i, j', j] \end{cases}$

We start at $B[0, 0, 0, 0]$ and finally obtain the answer at $B[0, n, 0, n]$

My question is how do we trace back the solution? This is the first time I see an addition of two different matrices while finding a minimum (see the second condition in A). Is there a standard way of tracing back for such algorithms?

  • 1
    $\begingroup$ It's the same as in the case of one matrix. Whenever you have a minimum of several things, you have to record which of them was the minimum. $\endgroup$ – Yuval Filmus Jul 3 '17 at 11:05
  • $\begingroup$ Yes, you are right - How do I record which one was minimum when I am adding them? $\endgroup$ – user2785161 Jul 3 '17 at 11:06
  • $\begingroup$ Be creative. Use your programming skills. Imagine you'd have to program it - what would you do? $\endgroup$ – Yuval Filmus Jul 3 '17 at 11:13
  • $\begingroup$ Dear, I am programming it. Stuck for a week. $\endgroup$ – user2785161 Jul 3 '17 at 11:20
  • 1
    $\begingroup$ When taking the minimum of a set, you need to store the expression which achieves the minimum. From here it's just a programming exercise. $\endgroup$ – Yuval Filmus Jul 3 '17 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.