Trong bài này chúng ta xem xét 2 bài toán khác nhap áp dụng phương pháp quy hoạch động.

String Edit Distance
Cho hai chuỗi (string) $A[1,2,\ldots, n]$ và $B[1,2,\ldots, m]$ có chiều dài lần lượt là $n$ và $m$. Khoảng cách edit distance(ED), hay còn gọi là khoảng cách Levenshtein, là số nhỏ nhất các thao tác: chèn một kí tự (letter insertion), xóa kí tự (letter deletion), và đổi kí tự (letter substitution) để biến chuỗi này thành chuỗi kia.

Ví dụ: khoảng cách giữa FOOD và MONEY tối đa là 4 vì:

FOOD $\rightarrow$ MOOD $\rightarrow$ MOND $\rightarrow$ MONED $\rightarrow$ MONEY

 
Trong bài này chúng ta sẽ thiết kế thuật toán với thời gian $O(nm)$ cho bài toán này dựa trên quy hoạch động. Điều thú vị là thuật toán quy hoạch động cho bài toán này là gần tối ưu về mặt thời gian, theo nghĩa nếu $n = m$, không tồn tại thuật toán chạy với thời gian ít hơn $n^{2-\epsilon}$ với mọi $\epsilon > 0$ trừ khi Giả Thiết Thời Gian Lũy Thừa (Exponential Time Hypothesis) là sai [2].

Để nhận biết bài toán con ta hãy suy nghĩ câu hỏi sau: liệu ta có thể tính khoảng cách ED giữa hai chuỗi con $A[1,2,\ldots ,i]$ và $B[1,2,\ldots, j]$ nếu ta biết khoảng cách giữa các chuỗi $A[1,2,\ldots, \bar{i}]$ và $B[1,2,\ldots, \bar{j}]$ với $\bar{i} \leq i$ và $\bar{j} \leq j$, trong đó ít nhất một trong hai $\bar{i} \not= i$ hoặc $\bar{j} \not= j$. Trả lời được câu hỏi như vậy có nghĩa là bạn có thể tính được ED giữa $A[1,2,\ldots, i]$ và $B[1,2,\ldots, j]$ dựa vào các bài toán con nhỏ hơn. Gọi $ED[i,j]$ là khoảng cách ED giữa hai dãy con $A[1,2,\ldots, i]$ và $B[1,2,\ldots, j]$.

Nếu ta có hai chuỗi con $A[1,2,\ldots ,i]$ và $B[1,2,\ldots, j]$, ta có ba lựa chọn để áp dụng ba thao tác với $A[i]$:

1. Xóa $A[i]$. Như vậy $ED[i,j] = ED[i-1,j]+1$
2. Chèn kí tự $B[j]$ vào sau $A[i]$. Như vậy $ED[i,j] = ED[i,j-1]+1$
3. "Thay thế" $A[i]$ bằng $B[j]$. Ta có hai trường hợp con ở đây: nếu $A[i] \not= B[j]$, khi đó $ED[i,j] = ED[i-1,j-1]+1$. Ngược lại ($A[i] = B[j]$), $ED[i,j] = ED[i-1,j-1]$

Trường hợp một trong hai số $i = 0$ hoặc $j=0$, khoảng cách tương ứng là $ED[i,j] = j$ hoặc $ED[i,j] = i$. Định nghĩa:

$I[A \not= B] = \begin{cases} 1, & \mbox{if } A \not= B\\ 0, & \mbox{if } \mbox{otherwise} \end{cases}$

Ta có giả mã sau:

 
Code của thuật toán bằng C. Code đầy đủ được cho ở cuối bài.

int edit_distance(char A[], char B[]){
int n = strlen(A), m = strlen(B);
int ED[n+1][m+1];
int i = 0;
int j = 0;
for(i = 0; i  <= n; i++){
memset(ED[i], 0, sizeof(ED[i]));// set everything to 0
}
for(j = 0; j <= m; j++){
ED[0][j] = j;
}
for(i = 0 ; i <= n; i++){
ED[i][0] = i;
}
int diff;
for(i = 1; i <= n ;i++){
for(j = 1; j <= m; j++){
ED[i][j] = ED[i-1][j] + 1;
ED[i][j] = (ED[i][j] < ED[i][j-1] + 1? ED[i][j] : ED[i][j-1] + 1);
diff = (A[i-1] == B[j-1]? 0 :  1);// arrays in C are indexed from 0
ED[i][j] = (ED[i][j] < ED[i-1][j-1] + diff? ED[i][j] : ED[i-1][j-1] + diff);
}
}
return ED[n][m];
}

Bài tập: In ra các chuỗi trung gian trong quá trình chuyển $A$ thành $B$ như ở trong ví dụ FOOD - MONEY bằng cách truy vết thuật toán EditDistance (có thể tham khảo thêm ở đây).

Phân tích thời gian và bộ nhớ Thời gian tính của thuật toán EditDistance bằng thời gian cần thiết để cập nhật mảng $ED[1,2,\ldots,n][1,2,\ldots,m]$. Mỗi phần tử của mảng mất thời gian $O(1)$ để cập nhật. Do đó thời gian tính của thuật toán là $O(m\cdot n)$. Bộ nhớ của thuật toán cũng là $O(m\cdot n)$ để lưu bảng.

Nếu để ý kĩ ta sẽ thấy trong thuật toán EditDistance, phần tử mảng $ED[i,j]$ chỉ phụ thuộc và 3 phần tử liền kề trong bảng. Như vậy ta chỉ cần lưu hàng $i-1$ của bảng $ED$, phần tử liền kề bên trái (left) và liền kề đường chéo (dag) của $ED[i,j]$. Do đó, ta giảm bộ nhớ xuống còn $O(m)$.

Giả mã như sau:

 
Vì $n$ và $m$ có vai trò như nhau, thay đổi một chút ta có thể giảm bộ nhớ xuống còn $O(\min\{n,m\})$. Code của giả mã bằng C:

int mem_edit_distance(char A[], char B[]){
int n = strlen(A), m = strlen(B);
int ED[m+1];
int i = 0;
int j = 0;
memset(ED, 0, sizeof(ED)); // set everything to 0
int dag = 0;
int left = 0;
for(j = 0; j <= m; j++){
ED[j] = j;
}
int diff;
int curr = 0;
for(i = 1; i <= n ;i++){
left = i;
dag = i-1;
for(j = 1; j <= m; j++){
curr = ED[j] + 1;
curr = (curr < left + 1? curr : left + 1);
diff = (A[i-1] == B[j-1]? 0 :  1); // I[A != B]
curr = (curr < dag + diff? curr : dag + diff);
left = curr;
dag = ED[j];
ED[j] = curr;
}
}
return ED[m];
}

Subset Sum
Trong bài này, chúng ta đã phát triển thuật toán quay lui với thời gian $2^n$ cho bài toán Subset Sum. Ý tưởng đệ quy là xét một phần tử $x \in X$, tồn tại một dãy con có tổng bằng $T$ nếu một trong hai điều kiện sau là đúng:

1. Tồn tại một tập con của $X \setminus \{x\}$ có tổng bằng $T - x$
2. Tồn tại một tập con của $X \setminus \{x\}$ có tổng bằng $T$

Như vậy ta có công thức đệ quy:

$SS(n,T) = \begin{cases} True, & \mbox{if } T = 0 \\ False, & \mbox{if } T < 0 \mbox{ or } i < 0 \\ SS(n-1,T-X[n])\vee SS(n-1,T), & \mbox{otherwise } \end{cases}$

Như vậy nếu ta đặt $SS[i,t] = True$ nếu tồn tại một dãy con của $A[1,2,\ldots,i]$ có tổng bằng $t$, ta có $SS[i-1,t]$ và $SS[i-1, t-X[i]]$ đều là các bài toán con. Ta có giải thuật quy hoạc động sau:

 
Code của giả mã bằng C:

int dynamic_subset_sum(int X[], int size, int T){
int S[size+1][T+1];
int i = 0, t = 0;
for(i = 0 ; i < size+1; i++)
memset(S[i], 0, sizeof(S[i])); // set every element to be 0
for( i = 0 ; i < size+1; i++){
S[i][0] = 1;
}
for(i = 1; i < size+1; i++){
S[i][0] = 1;
for(t = 1; t < X[i-1]; t++){ // arrays in C are indexed from 0
S[i][t] = S[i-1][t];
}
for(t = X[i-1]; t < T+1; t++){
S[i][t] = (S[i-1][t] + S[i-1][t - X[i-1]] > 0? 1 : 0);
}
}
return S[size][T];
}

Phân tích thời gian Thời gian tính toán của thuật toán DynamicSubsetSum có thể được quy về thời gian cập nhật các phần tử của mảng $S[n,T]$. Vì mỗi phần tử của mảng được cập nhật trong thời gian $O(1)$, thời gian tính toán của thuật toán là $O(nT)$. Dễ thấy thuật toán sử dụng $O(nT)$ bộ nhớ để lưu mảng $S[n,T]$.

Code: edit distance and data, subset sum
Tham khảo
[1] Jeff Erickson, Dynamic Programming Lecture Notes , UIUC.
[2] Backurs, Arturs, and Piotr Indyk. "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)." arXiv preprint arXiv:1412.0348 (2014).
[3] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. 1st Edition). McGraw-Hill Higher Education, (2008).