Trong thiết kế giải thuật, đôi khi chúng ta phải đưa ra quyết định chọn một phần tử trong tập các lựa chọn để xử lí và sau đó, tiếp tục thực hiện thuật toán sau khi đã xử lí phần tử được chọn. Nếu chúng ta chọn được phần tử "đủ tốt" trong tất cả các bước, thuật toán của chúng ta sẽ chạy với thời gian rất nhanh. Ví dụ trong thuật toán Quicksort, nếu phần tử chốt mà ta chọn trong mỗi bước là median (trung vị) của mảng con chưa sắp xếp thì thuật toán của chúng ta sẽ là $O(n\log n)$ với hằng số ẩn sau $O$ khá nhỏ.
Tuy nhiên, làm thế nào để chọn được phần tử "đủ tốt" là một vấn đề không hề dễ và đôi khi mất không ít thời gian vì chí ít ta cũng cần phải duyệt qua tất cả các lựa chọn để tìm ra phần tử đủ tốt đó. Ví dụ với Quicksort, chúng ta có thể áp dụng thuật toán Blum-Floyd-Pratt-Rivest-Tarjan để chọn median trong thời gian $O(n)$. Tuy nhiên làm như vậy thì thuật toán Quicksort $O(n\log n)$ cuối cùng sẽ có hằng số ẩn sau $O$ quá lớn.
Trong những trường hợp như Quicksort, chọn ngẫu nhiên, như sẽ chỉ ra dưới đây, sẽ cho chúng ta một giải pháp không quá tệ.
Việc chọn ngẫu nhiên theo nguyên lí trên thường sẽ khiến cho thực thi thuật toán của chúng ta sẽ trở nên đơn giản hơn rất nhiều. Tuy nhiên, khó khăn sẽ nằm ở phần phân tích thuật toán và đây cũng là điểm yếu của các thuật toán ngẫu nhiên. Trong thực tế thì những giải thuật kiểu "thực thi đơn giản, phân tích khó khăn" thường được ưu tiên hơn là "thực thi khó khăn, phân tích đơn giản". Chúng ta sẽ tìm hiểu hai ví dụ áp dụng nguyên lí trên: Quicksort và chọn median. Trước khi đọc tiếp, mình khuyến khích bạn đọc xem lại hai bài viết trước đây về hai bài toán này. Ngoài ra, xem lại Appendix về tính tổng và tích và bài xác suất cơ bản cũng sẽ giúp bạn tư duy tốt hơn trong phần phân tích mà mình sẽ trình bày.
Quicksort ngẫu nhiên
Nhắc lại thuật toán Quicksort: Giả sử ta muốn sắp xếp mảng đầu vào $A[1,2,\ldots,n]$. Để đơn giản ta sẽ giả sử các phần tử của mảng $A[1,2,\ldots,n]$ đôi một khác nhau. Thuật toán gồm hai bước:
- Chọn một phần tử của mảng (bất kì), $A[p]$, gọi là pivot, và phân mảng thành hai phần: phần 1 gồm những phần tử nhỏ hơn hoặc bằng $A[p]$ và phần 2 gồm những phần tử lớn hơn $A[p]$
- Gọi đệ quy sắp xếp phần 1 và phần 2
Trong trường hợp lí tưởng, phần tử pivot $A[p]$ trong mỗi bước mà ta chọn là median thì hai phần sẽ có kích thước bằng nhau và bằng cỡ $\frac{n}{2}$. Do đó thời gian sắp xếp của Quicksort thỏa mãn: $T(n) = 2T(n/2) + O(n)$. Từ đó suy ra $T(n) = O(n\log n)$. Chi tiết các bạn xem thêm tại bài viết gốc.
Giả mã như sau:
if$(n > 1)$
Choose a pivot element $A[p]$
$r \leftarrow $ Partition($A[1,2,\ldots, n],p$)
QuickSort($A[1,2,\ldots, r-1]$)
QuickSort($A[r+1,2,\ldots, n]$)
swap $A[p] \leftrightarrow A[n]$
$i \leftarrow 0$
$i \leftarrow n$
while $i$ < $j$
repeat $i \leftarrow i + 1$ until $(i \geq i \mbox{ or } A[i]\geq A[n])$
repeat $i \leftarrow j - 1$ until $(i \geq i \mbox{ or } A[j]\geq A[n])$
if $i$ < $j$
swap $A[i] \leftrightarrow A[j]$
swap $A[i] \leftrightarrow A[n]$
return $i$
Trong trường hợp xấu nhất, mỗi bước ta đều chọn phải phần tử pivot $A[p]$ mà hai phần có độ dài lệch nhau quá lớn thì thời gian của Quicksort sẽ là $O(n^2)$. Để tránh trường hợp xấu nhất này ta sẽ chọn $A[p]$ ngẫu nhiên. Thuật toán trở thành:
if$(n > 1)$
Choose $A[p]$ randomly from $A[1,2,\ldots,n]$
$r \leftarrow $ Partition($A[1,2,\ldots, n],p$)
RandomizedQuickSort($A[1,2,\ldots, r-1]$)
RandomizedQuickSort($A[r+1,2,\ldots, n]$)
Dòng màu đỏ chính là sự khác nhau của Quicksort và Quicksort ngẫu nhiên. Sự thay đổi này, như ta đã thấy, là khá đơn giản. Bây giờ chúng ta sẽ phân tích thuật toán. Do thời gian của thuật toán sẽ tỉ lệ với số phép so sánh, ta sẽ tính kì vọng số phép so sánh của thuật toán trên.
Phân tích thuật toán: Trước hết ta có nhận xét đơn giản sau:
Nhận xét: Hai phần tử bất kì của mảng được so sánh với nhau tối đa 1 lần và chúng chỉ được so sánh với nhau khi một trong hai phần tử đó được chọn là pivot tại bước nào đó của thuật toán.
Gọi $X$ là số lượng phép so sánh trong quá trình thực thi RandomizedQuickSort. Với mỗi cặp chỉ số $(i,j)$ sao cho $i < j$, ta định nghĩa biến ngẫu nhiên 0/1 $X_{ij}$ như sau: $X_{ij} = 1$ nếu phần tử nhỏ tứ $i$ của mảng được so sánh với phần tử nhỏ thứ $j$ của mảng và $X_{ij} = 0$ nếu ngược lại.
$ X_{ij} = \begin{cases} 1, & \mbox{if i-th and j-th smallest elements are compared.} \\ 0, & \mbox{otherwise. }\end{cases} \qquad (1)$
Như vậy, ta sẽ có:
$X = \sum_{i=1}^n \sum_{j = i +1}^n X_{ij} \qquad (2)$
Theo tính tuyến tính của kì vọng:
$E[X] = \sum_{i=1}^n \sum_{j = i +1}^n E[X_{ij}] \qquad (3)$
Do $X_{ij}$ là biến ngẫu nhiên 0/1, ta suy ra $E[X_{ij}] = \mathrm{Pr}[X_{ij}]$. Do đó, tính $(3)$ sẽ được quy về tính các xác suất $\mathrm{Pr}[X_{ij}]$. Theo nhận xét ở trên, $\mathrm{Pr}[X_{ij}]$ chính là xác suất phần tử nhỏ thứ $i$ hoặc thứ $j$ sẽ được chọn làm pivot trong một bước nào đó.
Tưởng tượng ta xếp các phần tử của mảng trên trục đường thẳng trong đó phần tử nhỏ thứ $i$ của mảng sẽ được sắp xếp vào điểm có tọa độ $i$. Nếu bất kì phần tử nào trong khoảng $(i+1,j-1)$ (loại trừ hai đầu mút) được chọn làm pivot tại một bước nào đó thì hai phần tử nhỏ thứ $i$ và thứ $j$ sẽ không có cơ hội được so sánh với nhau. Do đó, xác suất để một trong hai phần tử đó được chọn làm pivot sẽ là:
$\mathrm{Pr}[X_{ij}] = \frac{2}{j-i+1}\qquad (4)$
Số $j-i+1$ chính là độ dài của đoạn $[i,j]$. Kết hợp với $(3)$ ta suy ra:
$E[X] = \sum_{i=1}^n \sum_{j = i +1}^n\frac{2}{j-i+1} = 2(n+1)H(n) - 4n\sim 2n\ln n \qquad (5) $
Phương trình thứ 2 của $(5)$ là do ta áp dụng công thức $(3)$ ở Appendix tính tổng và tích.
Remark: Phân tích trên đây được viết ở phần mở đầu của cuốn sách nổi tiếng về Randomized Algorithms của Rajeev Motwani and Prabhakar Raghavan [1]. Mình khuyến khích bạn đọc xem thêm note của Avrim Blum [2]; trong đó Blum còn đưa ra cách phân tích khác dựa trên giải một phương trình đệ quy.
Chọn phần tử lớn thứ $k$ của mảng
Bài toán như sau: Cho một mảng $A[1,2,\ldots,n]$, tìm phần tử lớn thứ $k$ của mảng.
Tóm tắt thuật toán: Thuật toán gồm hai bước:
- Chọn một phần tử pivot, $A[p]$, và phân mảng thành hai phần: phần 1 gồm những phần tử nhỏ hơn hoặc bằng $A[p]$ và phần 2 gồm những phần tử lớn hơn $A[p]$. Gọi $r$ là vị trí của phần tử pivot $A[p]$ trong mảng $A$ sau khi phân.
- Nếu $r = k$, ta sẽ trả lại $A[p]$. Nếu $r < k$, phần tử thứ $k$ của mảng ban đầu sẽ là phần tử thứ $k-r$ của mảng con $A[r+1,\ldots,n]$; do đó, ta sẽ gọi đệ quy trên phần 2. Cuối cùng, nếu $r > k$, phần tử thứ $k$ của mảng ban đầu sẽ là phần tử thứ $k$ của mảng con $A[1,\ldots,r-1]$; do đó, ta sẽ gọi đệ quy trên phần 1.
Giả mã:
if $n ==1$
return $A[1]$
else
Choose a pivot $A[p]$
$r \leftarrow$ Partition$(A[1,2,\ldots, n],p)$
if $k$ < $ r$
return QuickSelect$(A[1,2,\ldots, r-1],k)$
else if $k$ > $r$
return QuickSelect$(A[r+1,2,\ldots, n],k-r)$
else
return $A[r]$
Chọn $A[p]$ như thế nào cũng lại là một vấn đề của bài toán này. Nếu chúng ta may mắn, mỗi bước ta đều chọn được $A[p]$ là phần tử chia mảng thành hai phần gần bằng nhau thì thuật toán ta thu được là $O(n)$. Nếu không may thì có thể sẽ là $O(n^2)$.
Ý tưởng chính trong thuật toán $O(n)$ của Blum,Floyd,Pratt,Rivest và Tarjan đó là chọn ra được pivot $A[p]$ đủ tốt trong thời gian $O(n)$. Thuật toán bao gồm các bước sau: (1) Chia $A[1,2,\ldots,n]$ thành $n/5$ khối, mỗi khối có kích thước là $5$. (2) Tìm $n/5$ phần tử, mỗi phần tử là median của một khối đã chia ở bước $1$. Gọi $B[1,2,\ldots,n/5]$ là tập các phần tử đó. (3) Gọi đệ quy tìm trung vị của $B[1,2,\ldots,n/5]$, lấy trung vị đó làm phần tử $A(p)$. (4) Thực hiện như giải thuật ban đầu với $A[p]$ vừa chọn được. Bằng các phân tích cụ thể hơn, thuật toán cuối cùng cũng có thời gian $O(n)$. Tuy nhiên, hằng số ẩn sau big-O cũng không hề nhỏ. Chi tiết bạn đọc xem thêm tại bài viết gốc.
Trong bài này, ta sẽ thay đổi 1 dòng trong QickSelect để thu được thuật toán ngẫn nhiên khá đơn giản mà cũng hiệu quả:
if $n ==1$
return $A[1]$
else
Choose a pivot $A[p]$ randomly
$r \leftarrow$ Partition$(A[1,2,\ldots, n],p)$
if $k$ < $ r$
return RandomizedQuickSelect$(A[1,2,\ldots, r-1],k)$
else if $k$ > $r$
return RandomizedQuickSelect$(A[r+1,2,\ldots, n],k-r)$
else
return $A[r]$
Tất cả những khó khăn lại nằm trong phần phân tích. Ta sẽ quy về phân tích số lượng phép so sánh cần thiết để tìm ra phần tử mong muốn. Gọi $T(n,k)$ là số lượng phép so sánh kì vọng để chọn ra phần tử lớn thứ $k$ của mảng gồm $n$ phần tử. Gọi $T(n) = \max_{k}T(n,k)$.
Phân tích: Phân tích dựa trên bài toán sau đây:
Bài toán bẻ thanh chocolate: Rùa và Thỏ cùng nhặt được một thanh kẹo chocolate có chiều dài 1. Do không biết chia thế nào cho công bằng, Thỏ đề xuất nhờ bác Gấu già chia thanh kẹo đó. Bác Gấu, do không còn tinh mắt, chọn một điểm ngẫu nhiên trên thanh kẹo và bẻ thành hai phần. Thỏ tham ăn và nhanh tay hơn nên luôn chọn phần to còn Rùa thì chỉ được phần nhỏ. Hỏi kì vọng chiều dài thanh kẹo của Thỏ là bao nhiêu?
Đáp án là $3/4$. Nếu bạn nào muốn xem chi tiết lời giải thì xem tại đây. Chú ý trong bài toán trên, miền của bài toán là miền liên tục.
Trở lại bài toán của chúng ta. Coi mảng $A[1,2,\ldots,n]$ như một "thanh chocolate rời rạc" có chiều dài $n$ và coi việc chọn phần tử pivot $A[p]$ như "bẻ thanh chocolate" tại một điểm ngẫu nhiên. Ở đây, sự khác biệt cơ bản so với bài toán bẻ chocolate ở trên đó là miền của chúng ta là rời rạc. Tuy nhiên, chiều dài kì vọng của phần lớn hơn vẫn không vượt quá $3n/4$. Xem chi tiết tại đây. Sau khi đã bẻ, trong trường hợp tồi nhất, chúng ta sẽ phải đệ quy trên phần dài nhất để tìm kiếm. Do đó, ta có:
$T(n) \leq T(\frac{3n}{4}) + n-1 \qquad (6)$
Số $n-1$ chính là số phép so sánh để chia mảng thành hai phần sau khi đã chọn được pivot. Giải công thức truy hồi trên ta được $T(n) \leq 4n$. Như vậy:
Remark Phần phân tích thuật toán RandomizedQickSelect là do Avrim Blum [3]. Thực tế phân tích này chỉ đưa cho bạn một cách nhìn trực quan về bài toán mà chưa phải là một phân tích "tỉ mỉ và chính xác" về mặt toán học. Bạn có thể xem cách phân tích tỉ mỉ hơn (ý tưởng thì vẫn như vậy) trong note [3].
Một số vấn đề
Vấn đề đầu tiên đó là thời gian thực tế của thuật toán ngẫu nhiên. Trong hai phân tích ở trên, chúng ta biết rằng RandomizedQickSort và RandomizedQickSelect có thời gian chạy kì vọng lần lượt là $O(n\log n)$ và $O(n)$. Tuy nhiên, trong thực tế, đôi khi thuật toán cuả chúng ta chạy nhanh hơn thời gian kì vọng và đôi khi lại chạy chậm hơn thời gian kì vọng vì giá trị của một biến ngẫu nhiên tại một thời điểm nào đó có thể nhỏ hơn hoặc lớn hơn hoặc nhỏ hơn giá trị kì vọng.
Về mặt lý thuyết thì thuật toán thực tế có thể chạy lâu hơn kì vọng nhiều lần và trong một số trường hợp (không phải hai thuật toán trong bài này) thuật toán không dừng (lặp vô hạn). Tuy nhiên, xác suất trường hợp như vậy xảy ra thường vô cùng nhỏ và khó có thể xảy ra trong thực tế. Để định lượng xem khả năng thuật toán chạy chậm hơn kì vọng, ví dụ 10 lần, là bao nhiêu thì chúng ta cần phải dùng đến những công cụ từ lý thuyết xác suất. Chính vì thế mà việc phân tích giải thuật ngẫu nhiên một cách đầy đủ thường khó hơn rất nhiều so với các phân tích ở trên. Ở đây mình sẽ giới thiệu và sử dụng bất đẳng thức Markov. Bất đẳng thức này khá đơn giản, vì thế nên các kết quả thu được cũng chưa thực sự mạnh.
$\mathrm{Pr}[X\geq a] \leq \frac{E[X]}{a} \qquad (7)$
Từ bất đẳng thức Markov, ta dễ dàng suy ra xác suất để thuật toán chạy chậm hơn kì vọng 10 lần ($a = 10 E[X]$) là không quá $0.1$. Thực tế, các thuật toán này chạy lớn hơn 3 lần kì vọng với xác suất rất nhỏ. Tuy nhiên, để phân tích được điề unày thì cần đến công cụ rất mạnh như bất đẳng thức Chernoff. Mình sẽ không đi sâu hơn vì vấn đề này vượt quá phạm vi của bài viết.
Vấn đề thứ hai nằm trong chính sự ngẫu nhiên. Ở đâu mà ta có ngẫu nhiên và làm thế nào để chọn được một phần tử ngẫu nhiên trong máy tính? Câu hỏi này không hể đơn giản và có cả một ngành khoa học chuyên nghiên cứu về nó. Để đạt được một nguồn ngẫu nhiên thực sự là một việc không dễ dàng. Các nguôn ngẫu nhiên mà ta thường sử dụng trong máy tính (ví dụ sử dụng các hàm random để sinh số ngẫu nhiên trong máy tính) là giả ngẫu nhiên. Các nguồn này trông hơi giống ngẫu nhiên (do ta khó đoán được quy luật của các số sinh ra) nhưng không thực sự là ngẫu nhiên. Trong thực thi các giải thuật, ta chấp nhận các nguồn giả ngẫu nhiên này thay cho nguồn ngẫu nhiên thực sự.
Tham khảo
[1] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995.
[2] Avrim Blum. Lecture Note on Probabilistic Analysis and Randomized Quicksort. CMU, 2011.
[3] Avrim Blum. Lecture Note on Selection. CMU, 2011.
[4] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005.
Recent Comments