2
$\begingroup$

I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim to minimize the total sum of distances between matched points with the following constraints:

  • Every point from both vectors has to be matched at least once, but can be matched multiple times.
  • A point i can only be matched with a point j if no point o is matched with a point u such that i < o and j > u or i > o and j < u, i.e., the ‘lines’ of the matches are not allowed to cross.

In order to compute the distance between two matched points, we use the absolute difference.

(Easy) Example input:

1.0 2.0 2.4 3.5
2.0 2.1 2.0 3.2

Should output:

1.8 

Because in this example |1.0 - 2.0| + |2.0 - 2.1| + |2.4 - 2.0| + |3.5 - 3.2| is optimal

The assignment hints to sequence alignment which I thoroughly studied and came across the Needleman-Wunsch algorithm. However, I can't figure out how to adapt it to this problem.

$\endgroup$
2
$\begingroup$

Since this is a programming assignment, I only show some hints.

Consider two vectors $\vec{a} = a_1 \cdots a_i \cdots a_m$ and $\vec{b} = b_1 \cdots b_j \cdots b_n$.

First, please prove the following

Observation: $a_m$ must be matched with $b_n$.

Second, consider the following subproblems,

$$D(i,j) \triangleq \text{the optimal (matching) distance between } a_1 \cdots a_i \text{ and } b_1 \cdots b_j.$$

and answer the following question

Given the observation above, what is the relationship between $D_{i,j}$ and $D(i-1, j)$, $D(i, j-1)$, or maybe $D(i-1, j-1)$?

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.