advanced trick

You are currently browsing articles tagged advanced trick.

Trong bài một số kĩ thuật cải tiến quy hoạch động I, chúng ta đã làm quen với giải thuật Dan Hirshberg kết hợp quy hoạch động với chia để trị để giảm bộ nhớ của thuật toán quy hoạch động. Hôm nay mình sẽ giới thiệu phương pháp chia để trị kết hợp với quy hoạch động để tăng tốc thuật toán cho một lớp các bài toán. Ý tưởng của kĩ thuật này hơi giống ý tưởng của Knuth-Yao trong bài trước. Trước hết chúng ta hãy xem xét ví dụ sau (ví dụ được chuyển thể từ một bài toán trên codeforces):

Problem 1: Có $n$ người đang đợi trong một hàng đợi để đi lên một máy bay có $k$ khoang. Nhân viên máy bay muốn xếp $n$ người này vào khoang theo thứ tự từ khoang thứ nhất đến khoang thứ $k$. Thứ tự xếp người vào khoang máy bay phải tuân theo thứ tự hàng đợi. Ví dụ: bạn có thể xếp $q_1$ người liên tiếp đầu tiên trong hàng đợi vào khoang thứ nhất, $q_2$ người liên tiếp sau $q_1$ người đầu tiên trong hàng đợi vào khoangng thứ hai, $\ldots$, $q_k$ người cuối cùng của hàng đợi vào khoang thứ $k$. Như vậy $\sum_{i=1}^k q_k = n$. Tuy nhiên, trong những người đó, có những người ghét nhau. Gọi $A[1,2,\ldots, n][1,2,\ldots, n]$ là mảng số nguyên trong đó $A[i,j]$ thể hiện mức độ ghét nhau của người thứ $i$ và thứ $j$. Biết rằng $A[i,j] = A[j,i]$ và $A[i,i] = 0 $ với mọi $i,j$. Tìm cách xếp (tìm $q_1,q_1,\ldots,q_k$) sao cho:

  • Mỗi khoang có ít nhất một người.
  • Tổng mức độ ghét nhau là nhỏ nhất, trong đó mức độ ghét nhau của một khoang được định nghĩa là tổng mức độ ghét nhau đôi một của những người trong khoang đó

     
    Ví dụ: Có $n= 3$ người trong hàng đợi và máy bay có $k=2$ khoang với mảng $A$ như sau:

    $\begin{bmatrix} 0 & 2 & 0 \\ 2 & 0 & 3 \\ 0 & 3 & 0 \end{bmatrix}$

    Có thể thấy cách xếp tối ưu là xếp hai người đầu tiên của hàng đợi vào khoang thứ nhất và người thứ 3 vào khoang thứ hai. Tổng mức độ ghét nhau trong trường hợp này là $2$.

    Ta có thể phát triển thuật toán quy hoạch động cho bài toán này như sau : Gọi $C[i][j]$ là chi phí để xếp $j$ người đầu tiên của hàng đợi vào $i$ khoang đầu tiên. Ta có công thức sau:

    $C[i,j] = \begin{cases} 0, & \mbox{if } i = j \\ \min_{i \leq \ell < j} C[i-1,\ell] + D[\ell+1,j], & \mbox{otherwise} \end{cases} \qquad (1)$

     
    Trong đó $D[i,j]$ là mức độ ghét nhau nếu xếp người thứ $i, i+1, \ldots, j$ vào cùng một khoang và được định nghĩa như sau:

    $D[i,j] = \sum_{i \leq p < q \leq j}A[p,q]\qquad (2)$

     
    Dưạ vào công thức $(2)$, ta có thể tính được mảng $D[1,2,\ldots,n][1,2,\ldots, n]$ trong thời gian $O(n^2)$ và dựa vào công thức $(1)$, ta có thể tính được lời giải tối ưu $C[k,n]$ trong thời gian $O(kn^2)$ như sau:

    SlowDynamicProgram($A[1,2,\ldots, n][1,2,\ldots, n]$):
        ComputeDisimilarity$(A[1,2,\ldots, n][1,2,\ldots, n])$
        for $i \leftarrow 1$ to $k$
            for $j \leftarrow i+1$ to $n$
                tmp $\leftarrow +\infty$
                for $\ell \leftarrow i$ to $j$
                    tmp $\leftarrow \min\{$ tmp, $C[i-1,\ell] + D[\ell+1, j]\}$
                $C[i,j] \leftarrow$ tmp
        return $C[k,n]$

     

    ComputeDissimilarity($A[1,2,\ldots, n][1,2,\ldots,n]$):
        for $i \leftarrow 1$ to $n$
            $D[i,i]\leftarrow 0$
            $B[i,i]\leftarrow 0$
        for $d \leftarrow 1$ to $n-1$
            for $i \leftarrow 1$ to $n-d$
                $B[i,i+d] \leftarrow B[i+1,i+d] + A[i,i+d]$   [[$B[i,j] = \sum_{i \leq \ell < j} A[\ell,j]$]]
                $D[i,i+d] \leftarrow D[i,i+d-1] + B[i,i+d]$

     
    Sau đây mình sẽ giới thiệu kĩ thuật chia để trị để giải bài toán có công thức quy hoạch động dạng $(1)$ trong thời gian $O(n^2 + kn\log n)$.

    Kĩ thuật chia để trị

    Gọi $R[i,j]$ là chỉ số nhỏ nhất (hay điểm chia tối ưu của $C[i,j]$) sao cho $C[i,j]$ đạt giá trị nhỏ nhất tại chỉ số này, i.e, $C[i,j] = C[i-1,R[i,j]] + D[R[i,j],j]$. Nếu bạn còn nhớ, trong kĩ thuật của Knuth-Yao, ta chứng minh được $R[i,j] \leq R[i,j+1] \leq R[i+1,j+1]$ (định nghĩa $R[i,j]$ trong kĩ thuật Knuth-Yao hơi khác một chút) với trường hợp $D[i,j]$ thỏa mãn bất đẳng thức hình chữ nhật. Trong trường hợp các bài toán đang xét ở đây, ta có thể chứng minh một bất đẳng thức tương tự:

    $R[i,j] \leq R[i,j+1] \qquad (3)$

     
    Chứng minh Với $i \leq r < j$, ta định nghĩa $C_r[i,j] = C[i-1,r] + D[r+1,j]$. Bằng một vài biến đổi đại số đơn giản, ta có thể chứng minh được mệnh đề sau:

    Nếu $r_2 \leq r_1$ và $C_{r_1}[i,j] \leq C_{r_2}[i,j]$, ta có $C_{r_1}[i,j+1] \leq C_{r_2}[i,j+1]$.

    Do đó, nếu ta gọi $r_1 = R[i,j]$ và $r_2 = R[i,j+1]$, theo định nghĩa của $r_2$, ta có:

    $C_{r_1}[i,j+1] \geq C_{r_2}[i,j+1]$.

    Giả sử $r_2 < r_1$, bằng cách lấy contrapositive của mệnh đề trên, ta có:

    $C_{r_1}[i,j] \geq C_{r_2}[i,j]$.

    Do đó theo định ghĩa của $r_1$, $C_{r_1}[i,j] = C_{r_2}[i,j]$ và do đó $r_1 \leq r_2$ vì $r_1$ là chỉ số bé nhất, trái với giả thiết $r_2 < r_1$ (dpcm).


    Do đó, theo $(3)$, ta có:

    $R[i,i] \leq R[i,i+1] \leq \ldots \leq R[i,n] \qquad (4)$

     
    Do đó chúng ta biết mảng một chiều $R[i]$ sẽ là mảng "đã sắp xếp" theo chiều tăng dần. Ở đây từ đã sắp xếp trong ngoặc kép vì mảng $R[i]$ chưa được cho trước mà chúng ta phải đi tìm. Dễ thấy $R[i,i] = i$ và $R[i,n]$ có thể tính được trong thời gian $O(n)$. Như vậy chúng ta biết rằng $C[i,i+1], \ldots, C[i,n-1]$ có điểm chia tối ưu trong khoảng $[R[i,i], R[i,n]]$. Áp dụng ý tưởng của tìm kiếm nhị phân, chúng ta có thể tính $C[i, m]$ (ở đây $m = (i+n)/2$) và $R[i,m]$. Dựa vào bất đẳng thức $(4)$, ta biết rằng $R[i,i+1], \ldots, R[i,m-1]$ nằm trong khoảng $[R[i,i], R[i,m]$ và $R[i,m+1], \ldots, R[i,n]$ nằm trong khoảng $[R[i,m], R[i,n]$. Do đó ta có thể gọi đệ quy trên hai dãy con này. Chi tiết thuật toán như sau:

    FastDynamicProgram($A[1,2,\ldots, n][1,2,\ldots,n]$):
        ComputeDisimilarity$(A[1,2,\ldots, n][1,2,\ldots, n])$
        for $i \leftarrow 1$ to $k$
            $R[i,i] \leftarrow i$
            $R[i,n] \leftarrow $ ComputeR($i,n,i,n$)
            DivConDynamic($i, i+1, n-1, i, R[i,n]$)
        return $C[k,n]$

     

    DivConDynamic($i, x, y, L, R$):
        if $y-x \leq 2$
            use bruteforce
        else
            $m \leftarrow \lfloor \frac{x+y}{2}\rfloor$
            $R[i,m] \leftarrow $ ComputeR($i,m,L,R$)
            DivConDynamic($i, x, m-1, L, R[i,m]$)
            DivConDynamic($i, m+1, y, R[i,m], R$)

     

    ComputeR($i,j, L, R$):
        tmp $\leftarrow +\infty$
        $p \leftarrow L$
        for $\ell \leftarrow L$ to $R$
            tmp $\leftarrow \min\{$ tmp, $C[i-1,\ell] + D[\ell+1, j]\}$
            $p \leftarrow \ell$
        $C[i,j]\leftarrow $ tmp
        return $p$

     
    Thủ tục DivConDynamic($i, x, y, L, R$) tính các giá trị $C[i,x], C[i,x+1], \ldots, C[i,y]$ nếu biết điểm chia tối ưu của $C[i,x]$ và $C[i,y]$ trong khoảng $[L, R]$. Thủ tục ComputeR($i,j, L, R$) tính $C[i,j]$, trả lại điểm chia tối ưu của $C[i,j]$ biết rằng điểm chia đó nằm trong khoảng $[L,R]$

    Phân tích thời gian tính Trước hết ta phân tích thời gian của thủ tục đệ quy DivConDynamic. Gọi $T(n,m)$ là thời gian tính của thủ tục DivConDynamic($i, x, y, L, R$) trong đó $m = R-L$ và $n = y-x$. Dễ thấy thời gian tính của thủ tục ComputeR($i,m,L,R$) là $O(R-L) = O(m)$. Trường hợp $m = O(1)$, thời gian tính $T(m,n)$ quy về:

    $ T(n) = 2T(n/2) + O(1) = O(n)$

    Trường hợp $n = O(1)$, dễ thấy $T(n,m) = O(m)$. Gọi $R[i,m] = k$, ta có công thức đệ quy sau:

    $ T(n,m) = \begin{cases} O(n), & \mbox{if } m = O(1)\\ O(m), & \mbox{if } n = O(1) \\ T(\frac{n}{2}, k) + T(\frac{n}{2}, m - k) + O(m), & \mbox{otherwise} \end{cases}$

     
    Do đó, bằng phương pháp quy nạp, ta có thể chứng minh được $T(m,n) =O((m+n)\log n)$. Suy ra, trong mỗi vòng lặp, thủ tục DivConDynamic($i, i+1, n-1, i, R[i,n]$) có thời gian tính là $O(n\log n)$. Do đó tổng thời gian tính của thuật toán là $O(n^2 + kn\log n)$ trong đó thời gian $O(n^2)$ dùng để tính bảng $D[1,2,\ldots,n][1,2,\ldots,n]$.
    Code của giả mã bằng C:

    int fast_dynamic_program(int n, int k){
    compute_dissimilarity(n);
    int i = 0, j = 0, l = 0, tmp;
    for( i = 0 ; i &lt; n ; i ++){
    memset(C[i], 0, sizeof(C[i])); // set everything to 0
    }
    for (j = 1; j &lt; n; j++){
    C[0][j] = D[0][j];
    }
    for(i = 1; i &lt; k; i++){
    R[i][i] = i;
    R[i][n-1] = computeR(i,n-1, i, n-1);
    div_con_dynamic(i, i+1, n-2, i, R[i][n-1]);
    }
    return C[k-1][n-1];
    }
    void div_con_dynamic(int i, int x, int y, int optL, int optR){
    if(y &lt; x) return;
    else if(y == x){
    R[i][x] = computeR(i, x, optL, optR);
    } else {
    int m = (x+y)/2;
    R[i][m] = computeR(i,m,optL,optR);
    div_con_dynamic(i, x, m-1, optL, R[i][m]);
    div_con_dynamic(i, m+1,y,R[i][m], optR);
    }
    }
    int computeR(int i, int j, int L, int R){
    int tmp = INFTY, p = L, l = 0;
    for(l = L; l &lt;= R; l++){
    if(C[i-1][l-1] + D[l][j] &lt; tmp){
    tmp = C[i-1][l-1] + D[l][j];
    p = l;
    }
    }
    C[i][j] = tmp;
    return p;
    }
    void compute_dissimilarity(int n){
    int d = 0, i = 0;
    for( i = 0; i &lt; n; i++){
    memset(D[i], 0, sizeof(D[i]));
    memset(B[i], 0, sizeof(B[i]));
    }
    for( d = 1; d &lt; n; d++){
    for(i = 0; i &lt; n-d; i++){
    B[i][i+d] = B[i+1][i+d] + A[i][i+d];
    D[i][i+d] = D[i][i+d-1] + B[i][i+d];
    }
    }
    }
    

    Code: flight-boarding, code đã accept trên codeforces.
    Tham khảo
    [1] Codeforces blogs: http://codeforces.com/blog/entry/8219, http://codeforces.com/blog/entry/8192
    [2] Zvi Galil and Kunsoo Park. 1992. Dynamic programming with convexity, concavity and sparsity. Theor. Comput. Sci. 92, 1 (January 1992), 49-76.

    Tags: , ,

    « Older entries