Quy hoạch động -- dynamic programming II

Dãy con tăng dài nhất

Bài toán dãy con tăng dài nhất (longest increasing subsequence-LIS) là một bài toán đặc trưng minh họa cho thuật toán quy hoạch động. Ở phần đồ thị chúng ta sẽ xem lại bài toán này và quy bài toán này về bài toán tìm đường đi dài nhất trong một đồ thị có hướng và không có chu trình (directed acyclic graph). Bài toán như sau:

Problem 2: Cho một mảng $n$ phần tử $A[1,2,\ldots,n]$. Tìm một dãy dài nhất các chỉ số $1 \leq i_1 < i_2 < \ldots < i_k \leq n$ sao cho $A[i_1] \leq A[i_2] \leq \ldots \leq A[i_k]$

 
Ví dụ: $A[10] = \{1,6,5,4,7,8,2,9,0,10\}$, (một trong số) dãy con tăng dài nhất là $\{1,6,7,8,9,10\}$ có chiều dài là $6$.

Trước hết ta giải bài toán "dễ hơn" một chút: tìm chiều dài của dãy con tăng lớn nhất của $A[1,2,\ldots,n]$. Hãy thử suy nghĩ một chút về bài toán theo cách như sau: ta muốn tìm dãy con tăng dài nhất của dãy $A[1,2,3,\ldots, n]$, ta có thể tìm dãy con tăng dài nhất của dãy con $A[1,2,\ldots,i]$ với mọi $i$. Một ý tưởng có thể áp dụng là bằng cách nào đó sử dụng thông tin về dãy con tăng dài nhất của $A[1,2,\ldots, j]$ với $j = 1,2, \ldots, i-1 $ để tìm dãy con tăng dài nhất của $A[1,2,\ldots, i]$. Gọi dãy con tăng dài nhất của $A[1,2,\ldots,i]$ là $A[i_1,i_2,\ldots, i_k]$. Trước hết ta xét $A[i]$, có hai trường hợp ở đây:

  1. Nếu $A[i]$ nằm trong dãy con tăng dài nhất của $A[1,2,\ldots, i]$ (tương đương với $i_k = i$), $A[i_1,i_2,\ldots, i_{k-1}]$ sẽ là dãy con tăng dài nhất của $A[1,2,\ldots, i-1]$ với mọi phần tử nhỏ hơn hoặc bằng $A[i]$.
  2. Nếu $A[i]$ không nằm trong dãy con tăng dài nhất của $A[1,2,\ldots, i]$ (tương đương với $i_k \not= i$), $A[i_1,i_2,\ldots, i_{k}]$ sẽ là dãy con tăng dài nhất của $A[1,2,\ldots, i-1]$.

Thuật toán với thời gian $O(n^2)$ và bộ nhớ $O(n^2)$

Gọi $LIS[i,j]$ với $i < j$ là chiều dài của dãy con tăng dài nhất của $A[1,2,\ldots,i]$ với các phần tử của dãy đều nhỏ hơn hoặc bằng $A[j]$. Ta khởi tạo $A[0,j] = 0, j = 1,2,\ldots,n$. Nếu $A[i] > A[j]$, ta biết chắc $A[i]$ không thể nằm trong dãy con tăng đó. Như vậy $LIS[i,j] = LIS[i-1,j]$. Nếu ngược lại ($A[i] \leq A[j]$), ta có hai trường hợp:

  1. $A[i]$ nằm trong dãy con tăng. Như vậy $LIS[i,j] = LIS[i-1,i] + 1$
  2. $A[i]$ không trong dãy con tăng. Như vậy $LIS[i,j] = LIS[i-1,j]$

Tóm lại ta sẽ có công thức đệ quy sau:

$LIS[i,j] = \begin{cases} LIS[i-1,j], & \mbox{if } A[i] > A[j]\\ \max\{LIS[i-1,i]+1, LIS[i-1,j]\}, & \mbox{otherwise } \end{cases} $

Để tiện cho việc thực thi, ta sẽ thêm phần tử $A[n+1] = +\infty$.
Giả mã của thuật toán:

LIS($A[1,2,\ldots, n]$):
    $A[n+1] \leftarrow \infty$
    for $i \leftarrow 0$ to $n$
        for $j \leftarrow i+1$ to $n+1$
           if $(A[j]$ < $A[i])$
                $LIS[i][j] \leftarrow LIS[i-1][j]$
           else
                $LIS[i][j] \leftarrow \max\{LIS[i-1][i] + 1, LIS[i-1][j]\}$
    return $LIS[n][n+1]$

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

int mem_waste_lis(int A[], int size){
int LIS[size+2][size+2];
int i = 0, j = 0;
for(i = 0 ; i &amp;lt; size + 2; i++){
memset(LIS[i], 0, sizeof(LIS[i]));// initialized every element to be 0
}
for (i = 1; i &amp;lt;= size; i++){
for(j = i+1; j &amp;lt;= size+1; j++){
if(A[j-1] &amp;lt; A[i-1]){// array A is indexed from 0
LIS[i][j] = LIS[i-1][j];
}else{
LIS[i][j] = (LIS[i-1][i] + 1 &amp;lt; LIS[i-1][j] ? LIS[i-1][j] :  LIS[i-1][i] + 1 );
}
}
}
return LIS[size][size+1];
}

Thuật toán trên thực hiện cập nhật một nửa kích thước mảng $LIS[0,1,\ldots,n][1,2,\ldots, n+1]$, trong đó cập nhật mỗi phần tửa của mảng mất thời gian là $\Theta(1)$. Như vậy thuật toán có thời gian là $\Theta(n^2)$. Dễ thấy thuật toán sử dụng $O(n^2)$ bộ nhớ để lưu mảng hai chiều kích thước $n\times n$.

Bài tập 1: Với mảng đầu vào là $A[10] = \{1,6,5,4,7,8,2,9,0,10\}$, hãy mô tả bảng $LIS$ là đầu ra của thuật toán trên.

Thuật toán với thời gian $O(n^2)$ và bộ nhớ $O(n)$

Trong phần này chúng ta sẽ tìm hiểu một cách nhìn khác về bài toán này (vẫn dùng thuật toán quy hoạch động). Thay vì dùng mảng hai chiều, ta dùng một mảng một chiều $B[1,2,\ldots,n]$ với phần tử $B[i]$ lưu chiều dài của dãy con tăng của $A[1,2,\ldots,i]$ kết thúc bởi $A[i]$. Dễ thấy $B[1] = 1$. Ta có công thức truy hồi sau cho $B[i]$

$ B[i] = \max_{\substack{1 \leq j \leq i-1\\ A[j] \leq A[i]}}{B[j]} + 1 $

Nói cách khác, ta tính $B[i]$ bằng cách duyệt qua các phần tử $B[j]$, $j \leq i-1$, với $A[j]$ tương ứng nhỏ hơn hoặc bằng $A[i]$ để tìm phần tử có gía trị lớn nhất rồi cộng với 1.

Gọi $C$ là mảng trong đó $C[i]$ lưu chiều dài của dãy con tăng dài nhất của $A[1,2,\ldots,i]$. Dễ thấy $C[1] = 1$ Giả sử ta đã tính được $B[i]$, dựa vào phân tích ở trên, ta có thể tính $C[i]$ như sau:

$ C[i] = \max \{C[i-1], B[i]\}$

Ta có giả mã sau:

LIS($A[1,2,\ldots, n]$):
    $B[1] \leftarrow 1$
    $C[1] \leftarrow 1$
    for $i \leftarrow 2$ to $n$
        max $\leftarrow 0$
        for $j \leftarrow 1$ to $i-1$
            if $A[j] \leq A[i]$ and $B[j] > $ max
                max $\leftarrow B[j]$
        $B[i] \leftarrow $ max $+1$
        $C[i] \leftarrow \max\{C[i-1], B[i]\}$
    return $C[n]$

 
Code bằng C của giả mã. Code đầy đủ được cho ở cuối bài.

int LIS(int A[], int size){
int B[size];
int C[size];
memset(B, 0, sizeof(B)); // set every element of B to 0
memset(C, 0, sizeof(C)); // set every element of C to 0
B[0] = 1;
C[0] = 1;
int i = 1, j = 0;
int max = 0;
for (i = 1; i &amp;lt; size ; i++){
max = 0;
for(j = 0; j &amp;lt; i; j++){
if(B[j] &amp;gt; max &amp;amp;&amp;amp; A[j] &amp;lt;= A[i]){
max = B[j];
}
}
B[i] = max + 1;
C[i] = B[i] &amp;gt; C[i-1] ? B[i] : C[i-1];
}
return C[size-1];
}

Trong giả mã trên, ta nhận thấy $C[i]$ chỉ phụ thuộc vào $C[i-1]$ (và $B[i]$) nên ta có thể tiết kiệm bộ nhớ bằng cách chỉ dùng một biến và cập nhận giá trị của biến đó qua các vòng lặp. Chi tiết thuật toán coi như bài tập cho bạn đọc (xem thêm tại Fibonacci).

Phân tích thời gian Thuật toán mất thời gian chủ yếu để cập nhật mảng $B[1,2,\ldots,n]$. Phần tử thứ $i$ cập nhật mất thời gian $O(i)$. Như vậy tổng thời gian cập nhật là $O(n^2)$. Thuật toán sử dụng 2 mảng B và C mỗi mảng kích thước $n$. Như vậy bộ nhớ thuật toán sử dụng là $O(n)$.

Bài tập 2: Với mảng đầu vào là $A[10] = \{1,6,5,4,7,8,2,9,0,10\}$, hãy mô tả mảng $B$ và $C$ là đầu ra của thuật toán trên.

Nhận xét

Hai thuật toán trên khác nhau cơ bản trong việc xác định "bài toán con". Với các bài toán con khác nhau sẽ cho ta thuật toán với thời gian tính và bộ nhớ khác nhau. Điểm mấu chốt của quy hoạch động chính là xác định đúng bài toán con. Rất khó có một quy tắc chung để xác định đâu là bài toán con sẽ cho ta thuật toán tối ưu. Thông thường với các bài toán quy hoạch động, không khó để thiết kết thuật toán dạng điền bảng 2 và 3 chiều. Để tiết kiệm bộ nhớ và thời gian hơn nữa cần những kĩ năng nhất định mà mình sẽ cố gắng giúp các bạn phát triển sâu hơn nữa trong các bài viết tiếp theo.

Thuật toán sau đây là cải tiến của thuật toán thứ hai. Điểm mấu chốt chính là việc duy trì một mảng tăng dần sao cho việc cập nhật phần tử thứ $i$ của bảng $B[i]$ có thể được thực hiện bằng tìm kiếm nhị phân. Trước khi đọc phần tiếp theo, bạn nên làm hai bài tập 1, 2 ở hai phần trước để hiểu kĩ hơn thuật toán.

Thuật toán với thời gian $O(n\log n)$ và bộ nhớ $O(n)$

Trong thuật toán ở phần 2, ta lưu thêm một mảng $D$ trong đó $D[k]$ lưu phần tử nhỏ nhất trong số các phần tử kết thúc của dãy con có chiều dài $k$. Ta sẽ cập nhật $D[k]$ theo từng bước.

Ví dụ với dãy $A[1,2,\ldots,10] = \{1,6,5,4,7,8,2,9,0,10\}$, ta có $D[2] = 2$ vì trong số các dãy con tăng có chiều dài 2 (đó là $\{1,6\},\{1,5\}, \ldots, \{1,2\}, \ldots, $ $\{1,10\}, \{6,7\},\{6,8\}, \ldots, \{9,10\}$), dãy $\{1,2\}$ có phần tử kết thúc là $2$ là phần tử nhỏ nhất. Như vậy mảng $D$ đầu ra là $D[1] = 0, D[2] = 2, D[3] = 7,$ $ D[4] = 8, D[5] = 9, D[6] = 10$.

Qua ví dụ trên có thể thấy rằng mảng $D$ đầu ra là mảng tăng dần, và ta sẽ chứng minh rằng (ở dưới) $D$ luôn là mảng tăng sau mỗi bước của thuật toán. Ta có giả mã sau:

FastLIS($A[1,2,\ldots, n]$):
    $B[1] \leftarrow 1$
    $D[1] \leftarrow A[1]$
    $p \leftarrow 1$
    for $i \leftarrow 2$ to $n$
        $k \leftarrow $ FloorBinarySearch$(D[1,2,\ldots,p], A[i])$
        $B[i] \leftarrow k+1$
        if $k= p$              [[found a longer subsequence]]
          $D[p+1] \leftarrow A[i]$
           $p \leftarrow p+1$
        else
           $D[k+1] \leftarrow A[i]$
    return $p$

 
Code của thuật toán bằng C. Để ý kĩ ở giả mã trên, mảng $B$ được sử dụng chỉ để minh họa thuật toán tốt hơn. Khi lập trình có thể bỏ mảng này. Code đầy đủ được cho ở cuối bài.

int fast_lis(int A[], int size){
int D[size+1];
memset(D, 0, sizeof(D)); // set every element of D to 0
D[0] = A[0];
int i = 1,  k =0;
int p = 0;
for (i = 1; i &amp;lt; size ; i++){
k = floor_binary_search(D, 0, p, A[i]);
if(k == p){ // found a longer subsequence
D[p+1] = A[i];
p++;
} else {
D[k+1] = A[i];
}
}
return p+1;
}

Gọi $A[i_1,i_2,\ldots, i_k]$, $i_k = i$, là mảng con tăng dài nhất của $A[1,2,\ldots,i]$ kết thúc bởi $A[i]$. Như vậy $A[i_1,i_2, \ldots, i_{k-1}]$ sẽ là mảng con tăng dài nhất của dãy $A[1,2,\ldots,i_{i-1}]$ kết thúc bởi $i_{k-1}$. Như vậy để tìm $A[i_1,i_2,\ldots, i_k]$, ta chỉ việc tìm $i_{k-1}$ sao cho $B[i_{k-1}]$ có chiều dài lớn nhất và $A[i_{k-1}] \leq A[i]$. Theo định nghĩa của $D$, $B[i_{k-1}]$ là chỉ số lớn nhất trong số các chỉ số của các phần tử có giá trị nhỏ hơn hoặc bằng $A[i]$ trong mảng $D$. Vì $D$ là mảng tăng, ta có thể thực hiện việc tìm kiếm bằng tìm kiếm nhị phân. Thủ tục FloorBinarySearch$(D[1,2,\ldots,n], a)$ sẽ trả lại $0$ nếu $a < D[1]$, $n$ nếu $a \geq D[n]$ và trả lại $k$ thỏa mãn $D[k] \leq a < D[k+1]$. Giả mã như sau:

FloorBinarySearch($D[1,2,\ldots, n],a$):
    if$(n \leq 5)$
        Use brute force
    else
        $m \leftarrow \lceil n /2\rceil$
        if $a$ < $ D[m]$
           FloorBinarySearch$(D[1,2,\ldots,m-1], a)$
        else if $D[m+1] \geq a$
          FloorBinarySearch$(D[m+1,2,\ldots,n], a)$
        else
            return $m$

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

int floor_binary_search(int _array[], int x, int y, int a){
int i = 0;
if(y - x &amp;lt;=5){ // trying brute force search
if(a &amp;lt; _array[x]) return x-1;
if(a &amp;gt;= _array[y]) return y;
else {
for(i = x; i &amp;lt; y; i++){
if(_array[i] &amp;lt;= a &amp;amp;&amp;amp; a &amp;lt;_array[i+1]){
return i;
}
}
}
} else {
int m = (x+y)/2;
if(a &amp;lt; _array[m]){
return floor_binary_search(_array, x, m-1, a);
} else if(a &amp;gt;= _array[m+1]){
return floor_binary_search(_array, m+1, y, a);
} else return m;
}
}

Phân tích thời gian và bộ nhớ Thuật toán thực hiện $n$ vong lặp, mỗi bước lặp thực hiện tìm kiếm nhị phân trên mảng $D[1,2,\ldots,p]$. Giả sử chiều dài của dãy con tăng lớn nhất là $L$, ta có $p \leq L$. Do đó, mỗi bước lặp sẽ mất thời gian $O(\log L)$. Như vậy thời gian chạy của thuật toán là $O(n\log L)$. Trường hợp xấu nhất $L = O(n)$, thời gian chạy của thuật toán là $O(n\log n)$. Dễ thấy bộ nhớ cần thiết của thuật toán là $O(n)$ để lưu mảng $D[1,2,\ldots, n]$.

Tính đúng đắn của thuật toán FastLIS($A[1,2,\ldots, n]$) là hệ quả trực tiếp của bổ đề sau:

Lemma: Gọi $p$ là giá trị sau vòng lặp $i$ của thuật toán FastLIS , ta có $p$ là chiều dài của dãy con tăng dài nhất của mảng $A[1,2,\ldots,i]$ với phần tử cuối cùng là $D[p]$.

 
Chứng minh

Ta sẽ chứng minh một phát biểu mạnh hơn bằng quy nạp: $D[j]$ sẽ là phần tử cuối nhỏ nhất trong các dãy có chiều dài $j$ của $A[1,2,\ldots, i]$. Trường hợp cơ sở $i=1$, bổ đề đúng. Giả sử bổ đề đúng với $i-1$, ta xét vòng lặp $i$.

  1. Nếu $k = p$ ($k$ là gi trị đầu ra của FloorBinarySearch $(D[1,2,\ldots,p], A[i])$), ta có $A[i] \geq D[p]$. Theo giả thiết quy nạp, $p$ là chiều dài của dãy con tăng dài nhất của mảng $A[1,2,\ldots,i-1]$ với phần tử cuối cùng là $D[p]$. Như vậy ta có thể ghép $A[i]$ vào cuối của dãy con tăng này để thu được dãy con tăng có chiều dài $p+1$. Các phần tử $D[1,2,\ldots, p]$ không đổi sau vòng lặp $i$. Do đó phát biểu trên đúng theo giả thiết quy nạp.
  2. Nếu $k < p$, ta có $D[k] \leq A[i] < D[k+1]$. Theo giả thiết quy nạp, $D[k]$ là phần tử cuối nhỏ nhất trong các dãy có chiều dài $k$ của $A[1,2,\ldots, i]$ và $D[k+1]$ là phần tử cuối nhỏ nhất trong các dãy có chiều dài $k+1$ của $A[1,2,\ldots, i-1]$. Vì $A[i] < D[k+1]$, sẽ không thể có dãy con của dãy $A[1,2,\ldots, i-1]$ có chiều dài $k+1$ với mọi phần tử nhỏ hơn $A[i]$. Như vậy, ghép $A[i]$ với dãy con của dãy $A[1,2,\ldots, i-1]$ có chiều dài $k$ với mọi phần tử nhỏ hơn hoặc bằng $A[i]$, ta sẽ được dãy có chiều dài $k+1$ với phần tử cuối nhỏ hơn $D[k+1]$. Vì thuật toán cập nhật $D[k+1]\leftarrow A[i]$, nên sau vòng lặp $i$, $D[k+1]$ sẽ là phần tử cuối nhỏ nhất trong các dãy có chiều dài $k+1$ của $A[1,2,\ldots, i]$. Do các phần tử khác của mảng $D$ không đổi, phát biểu trên đúng theo giả thiết quy nạp.

Tìm các phần tử của mảng con tăng dài nhất

Có ít nhất hai cách để có thể in ra các phần tử của mảng con sau khi đã tìm được chiều dài của mảng:

  1. Cách 1: ghi nhớ lại các dãy con trong mỗi bước của thuật toán. Ví dụ trong thuật toán 1, với mỗi giá $LIS[i][j]$, ta lưu một danh sách $List[i][j]$ chứa dãy con tương ứng với chiều dài $LIS[i][j]$. Cách này thường tốn thêm bộ nhớ, nhưng khi thuật toán kết thúc, chỉ việc in ra $List[n][n+1]$
  2. Cách 2: cách này dựa vào cách thức thực hiện của thuật toán để truy vết. Cách này không tốn thêm nhiều bộ nhớ, nhưng phải trả thời gian cho việc truy vết.

Sau đây mình sẽ minh họa Cách 2 với thuật toán 2. Tìm các phần tử của mảng con tăng với thuật toán 1 và 3 coi như bài tập.

Ta dựa vào mảng $B[1,2,\ldots, n]$ để truy vết thuật toán. Ý tưởng cơ bản như sau: giả sử ta có chiều dài của dãy con tăng là $L$ (đã tính được bởi thuật toán 2). Vì $B[i]$ là chiều dài của dãy con tăng lớn nhất của mảng $A[1,2,\ldots, i]$ kết thúc bởi $A[i]$, chỉ số $i$ lớn nhất sao cho $B[i] = L$ chính là chỉ số của phần tử cuối cùng của mảng con tăng lớn nhất của $A[1,2,\ldots, n]$. Ta có giả mã sau:

PrintLIS($B[1,2,\ldots, n], L$):
    $m \leftarrow +\infty$
    for $i \leftarrow n$ to $1$
       if $(B[i] = L)$ and $A[i] \leq m$
          print $A[i]$
          $m \leftarrow A[i]$
          $L \leftarrow L-1$

 
Dễ thấy thời gian để tìm các phần tử của mảng con tăng là $O(n)$.

 
Code: code, data.
Tham khảo

[1] Jeff Erickson, Dynamic Programming Lecture Notes , UIUC.
[2] Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms. 1st Edition). McGraw-Hill Higher Education, (2008).
[3]http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn

Facebook Comments

Tags: ,

  1. Abc’s avatar

    Bài viết hay lắm admin.

    Reply

Reply

Your email address will not be published. Required fields are marked *