Trong bài quy hoạch động IV, chúng ta đã làm quen với bài toán cây nhị phân tìm kiếm tối ưu (Optimal Binary Search Tree - OBTS) và thuật toán quy hoạch động để giải bài toán này trong thời gian $O(n^3)$. Chúng ta cũng thảo luận thuật toán Knuth, cải tiến quy hoạch động, với thời gian $O(n^2)$ dựa trên bổ đề sau:
$R[i,j-1] \leq R[i,j] \leq R[i+1,j] \qquad (1)$
Về ý nghĩa của các bảng $R$, bạn đọc có thể xem lại bài viết quy hoạch động IV. Ở bài trước, mình chưa đưa ra chứng minh bổ đề trên của Knuth. Trong bài này mình sẽ chứng minh bổ đề này và giới thiệu một phương pháp tổng quát cho một lớp các bài toán tương tự. Phương pháp này được Yao [1] phát triển vào năm 1980.
Bất đẳng thức hình chữ nhật
Để minh họa cho phương pháp của mình, Yao xem xét bài toán sau:
Ví dụ: $A[1,2,3] = {5,3,4}$. Nếu bạn tính tích theo thứ tự $(5\cdot 3)\cdot 4$, chi phí bạn phải trả là $15 + 60 = 75$. Tuy nhiên, nếu bạn tính theo thứ tự $5\cdot(3\cdot 4)$, bạn chỉ phải trả chi phí $12 + 60 = 72$.
Tương tự như OBST, gọi $C[i,j]$ là chi phí ít nhất để tính tích $A[i]\cdot A[i+1]\cdots A[j]$. Ta có công thức đệ quy sau:
$C[i,j] = \begin{cases} 0, & \mbox{if } i = j \\ W[i,j] + \min_{i < k \leq j}\{C[i,k-1] + C[k,j] \}, & \mbox{otherwise } \end{cases}$
Trong đó $W[i,j] = A[i]\cdot A[i+1]\cdots A[j]$. Ta có thể giải bài toán trên trong thời gian $O(n^3)$ bằng quy hoạch động như giả mã sau. Bạn đọc có thể tham khảo bài viết này để hiểu thêm chi tiết.
for $i \leftarrow 1$ to $n$
$C[i,i] \leftarrow 0$
$R[i,i] \leftarrow i$
for $d \leftarrow 1$ to $n-1$
for $i \leftarrow 1$ to $n-d$
ComputeCost($i,i+d$)
return $C[1,n]$
$C[i,j] \leftarrow +\infty$
for $r \leftarrow i+1$ to $j$
tmp $\leftarrow C[i,r-1] + C[r,j]$
if tmp $\leq C[i,j]$
$C[i,j] \leftarrow$ tmp
$R[i,j] \leftarrow r$
$C[i,j] \leftarrow C[i,j] + W[i,j]$
Tuy nhiên, trong trường hợp bảng $W$ thỏa mãn điều kiện trong định lý sau, Yao chứng minh rằng có thể giải bài toán trên trong thời gian $O(n^2)$:
- Bất đẳng thức hình chữ nhật: $W[i,j] + W[i',j'] \leq W[i',j] + W[i,j']$ với mọi $i \leq i' \leq j \leq j'$
- Đơn điệu: $W[i,j] \leq W[i',j']$ với mọi $i' \leq i \leq j \leq j'$
thì bảng $C[1,2,\ldots,n][1,2,\ldots,n]$ thỏa mãn công thức đệ quy ở trên có thể được cập nhật trong thời gian $O(n^2)$.
Ví dụ: bảng $W$ của bài toán nhân dãy số thỏa mãn hai tính chất trong định lý Yao. Thật vậy, với $i \leq i'\leq j \leq j'$, ta có:
$\begin{array}{l} W[i,j] & = A[i]\cdot A[i+1] \cdots A[j] \\ W[i',j'] & = A[i']\cdot A[i'+1] \cdots A[j'] \\ W[i',j] &= A[i']\cdot A[i'+1] \cdots A[j] \\ W[i,j'] &= A[i]\cdot A[i+1] \cdots A[j'] \end{array}$
Đặt $a = A[i]\cdot A[i+1] \cdots A[i'-1], b = A[i']\cdot A[i'+1] \cdots A[j],$ $c= A[j+1] \cdots A[j']$, ta có bất đẳng thức hình chữ nhật trở thành:
$ab + bc \leq b + abc \Leftrightarrow b(a-1)(c-1) \geq 0$
Tính chất đơn điệu cuả bảng $W$ có thể dễ thấy và coi như bài tập cho bạn đọc. Một ví dụ khác là bảng $W$ của bài toán OBST cũng thỏa mãn tính chất này (chứng minh coi như bài tập).
Tương tự như giải thuật Knuth cho OBST, Yao chứng minh rằng bảng $R$ thỏa mãn tính chất sau:
$R[i,j-1] \leq R[i,j] \leq R[i+1,j] \qquad (2)$
Do đó thủ tục ComputeCost($i,j$) có thể được thay thế bảng thủ tục sau:
$C[i,j] \leftarrow +\infty$
for $r \leftarrow R[i,j-1]$ to $R[i+1,j]$
tmp $\leftarrow C[i,r-1] + C[r,j]$
if tmp $\leq C[i,j]$
$C[i,j] \leftarrow$ tmp
$R[i,j] \leftarrow r$
$C[i,j] \leftarrow C[i,j] + W[i,j]$
Do đó, tổng thời gian tính toán của thuật toán là $O(n^2)$ (chi tiết phân tích thuật toán xem thêm tại đây).
Chứng minh định lý Yao
Để chứng minh đị lý Yao, ta chỉ cân chứng minh bất đẳng thức $(2)$. Trước tiên ta chứng minh rằng bảng $C$ thỏa mã bất đẳng thức hình chữ nhật. Hay nói cách khác, với $i \leq i' \leq j \leq j'$, ta chứng minh:
$C[i,j] + C[i',j'] \leq C[i',j] + C[i,j'] \qquad (3)$
Ta sẽ chứng minh bằng phương pháp quy nạp với biến quy nạp là $\ell = |j'-i|$. Trường hợp $i = i'$ hoặc $j = j '$, bạn đọc có thể dễ dàng kiểm tra bất đằng thức $(3)$ là đúng. Do đó, bất đẳng thức đúng khi $\ell \leq 1$. Với $\ell \geq 2$, ta có hai trường hợp:
- Nếu $i < i'=j < j'$, bất đẳng thức trở thành:
$C[i,j] + C[j,j'] \leq C[i,j']$
Gọi $r$ là giá trị sao cho: $C[i,j'] = W[i,j] + C[i,r-1] + C[r,j']$. Ta có hai trường hợp nhỏ sau:
- Nếu $r \leq j$, theo công thức đệ quy của bảng $C$, ta có $C[i,j] = W[i,j] + C[i,r-1] + C[r,j]$. Do đó:
$\begin{array}{l} C[i,j] + C[j,j'] & \leq W[i,j] + C[i,r-1] + C[r,j] + C[j,j'] \\ & \leq W[i,j] + C[i,r-1] + C[r,j'] \\ &\leq W[i,j'] + C[i,r-1] + C[r,j'] \\ & = C[i,j'] \end{array}$
Bất đẳng thức thứ nhất theo định công thức đệ quy cuả bảng $C$. Bất đẳng thức thứ hai theo giả thiết quy nạp và bất đẳng thức thứ ba theo tính đơn điệu của $W$.
- Nếu $r \geq j$, chứng minh tương tự và coi như bài tập cho bạn đọc.
- Nếu $r \leq j$, theo công thức đệ quy của bảng $C$, ta có $C[i,j] = W[i,j] + C[i,r-1] + C[r,j]$. Do đó:
- Nếu $i < i' < j' < j$, gọi $r_1,r_2$ là các số sao cho $C[i',j] = W[i',j] + C[i',r_1-1] + C[r_1,j]$, $C[i,j'] = W[i,j'] + C[i,r_2-1] + C[r_2,j']$. Ta có hai trường hợp con:
- Nếu $r_1 \leq r_2$, ta có $i \leq i' < r_1 \leq r_2$. Do đó:
$\begin{array}{l} C[i,j] + C[j,j'] & \leq W[i,j] + C[i,r_1-1] + C[r_1,j] + W[i',j'] + C[i',r_2-1] + C[r_2,j'] \\ & \leq W[i',j] + W[i,j'] + C[i,r_1-1] + C[r_1,j] + C[i',r_2-1] + C[r_2,j'] \\ &\leq W[i',j] + W[i,j'] + C[i,r_2-1] + C[r_2,j'] + C[i',r_1-1] + C[r_1,j] \\ & = C[i',j] + C[i,j'] \end{array}$
Bất đẳng thức thừ nhất theo công thức đệ quy của bảng $C$. Bất đẳng thức thứ 2 theo tính chất bất đẳng thức hình chữ nhật của bảng $W$. Bất đẳng thức thứ 3 theo giả thiết quy nạp áp dụng cho $i \leq i' < r_1 \leq r_2$. Đẳng thức cuối cùng theo định nghĩa của $r_1,r_2$.
- Nếu $r_2 \leq r_1$, ta có $r_2 \leq r_1 \leq j \leq j'$. Chứng minh tương tự như trường hợp trên và coi như bài tập cho bạn đọc.
- Nếu $r_1 \leq r_2$, ta có $i \leq i' < r_1 \leq r_2$. Do đó:
Do đó, bảng $C$ cũng thỏa mãn bất đẳng thức hình chữ nhật.
Với mỗi $k$ thỏa mãn $i < k \leq j$, kí hiệu $C_k[i,j] = W[i,j] + C[i,k-1] + C[k,j]$. Gọi $r_1, r_2$ là hai số sao cho $i \leq r_1 < r_2 \leq j$.
Ta sẽ chứng minh nếu:
$C_{r_2}[i,j-1] \leq C_{r_1}[i,j-1] \Rightarrow C_{r_2}[i,j] \leq C_{r_1}[i,j] \qquad (4)$
Thật vậy, dễ thấy:
$\begin{array}{lcl} C_{r_2}[i,j-1] &\leq& C_{r_1}[i,j-1] \\ \Rightarrow C[i,r_2-1] + C[r_2,j] &\leq& C[i,r_1-1] + C[r_1,j] \qquad (5)\end{array}$
Ngoài ra, vì $C$ thỏa mãn bất đẳng thức hình chữ nhật, ta có:
$C[r_1,j-1] + C[r_2, j] \leq C_[r_1,j] + C[r_2, j-1] \qquad (6)$
Kết hợp bất đảng thức $(5)$ và $(6)$ ta thu được bất đẳng thức $(4)$.
Bây giờ chúng ta sẽ chứng minh bất đẳng thức $(2)$. Từ thủ tục ComputeCost($i,j$), dễ thấy $R[i,j]$ là chỉ số lớn nhất sao cho
$C[i,j] = W[i,j] + C[i,R[i,j]-1] + C[R[i,j], C]$
Gọi $r_1 = R[i,j-1], r_2 = R[i,j]$. Giả sử $r_2 < r_1$, theo định nghĩa của $r_2$, ta có:
$C_{r_2}[i,j] < C_{r_1}[i,j] $
Do đó, theo bất đẳng thức $(4)$, ta có:
$C_{r_2}[i,j-1] < C_{r_1}[i,j-1]$
điều này trái với định nghĩa của $r_1$. Do đó $r_1 \leq r_2$ hay nói cách khác, $R[i,j-1] \leq R[i,j]$. Vế phải của $(2)$ có thể được chứng minh bằng cách tương tự.
Tham khảo
[1] Yao, F. Frances. "Efficient dynamic programming using quadrangle inequalities." In Proceedings of the twelfth annual ACM symposium on Theory of computing, pp. 429-435. ACM, 1980.
[2] TopCoder http://codeforces.com/blog/entry/8219.
Bài tập
Bài 1 (bẻ xâu): (bài toán được lấy từ http://www.spoj.com/problems/BRKSTRNG/): Cho một xâu $A[1,2,\ldots,n]$ gồm $n$ kí tự, không có dấu cách. Bạn muốn bẻ xâu này thành $M$ xâu con bằng cách thêm $M-1$ dấu cách, mỗi lần chỉ được thêm một dấu cách, vào các vị trí $a_1,a_2,\ldots, a_{M-1}$ của xâu $A[1,2,\ldots,n]$. Tuy nhiên, bạn sẽ phải trả chi phí $\ell$ để bẻ một xâu liên tục có chiều dài $\ell$ thành hai xâu con. Tìm cách bẻ xâu hiệu quả nhất.
Ví dụ: $A[1,2,\ldots, 10] =$ ALGORITHMS. Bạn muốn bẻ xâu thành 3 xâu con AL GO RITHMS với vị trí bẻ tương ứng là $a_1 = 2, a_2 = 4$. Bạn có thể bẻ xâu theo cách sau:
ALGORITHMS $\rightarrow$ AL GORITHMS $\rightarrow$ AL GO RITHMS
Cách này tốn chí phí là: $10 + 8= 18$. Tuy nhiên, nếu bạn bẻ như sau:
ALGORITHMS $\rightarrow$ ALGO RITHMS $\rightarrow$ AL GO RITHMS
bạn sẽ chỉ tốn chí phí là: $10 + 4 = 14$.
Recent Comments