Thuật toán chia để trị

Chia để trị (divide and conquer) là một chiến lược thuật toán rất quan trọng và phổ biến. Chia để trị thường được triển khai dựa trên đệ quy (recursion), bao gồm hai bước: "chia" (divide) và "trị" (conquer).

1. Chia (giai đoạn phân chia): Chia bài toán ban đầu thành hai hoặc nhiều bài toán con (subproblem) một cách đệ quy cho đến khi đạt được bài toán con nhỏ nhất.
2. Trị (giai đoạn hợp nhất): Bắt đầu từ những bài toán con nhỏ nhất đã có lời giải, hợp nhất các lời giải của bài toán con từ dưới lên trên để xây dựng lời giải cho bài toán ban đầu.

Như được mô tả trong hình bên dưới, sắp xếp trộn (merge sort) là một trong những ứng dụng điển hình của chiến lược chia để trị.

1. Chia: Chia mảng (array) ban đầu (bài toán ban đầu) thành hai mảng con (subarray) (bài toán con) một cách đệ quy cho đến khi mảng con chỉ còn một phần tử (element) (bài toán con nhỏ nhất).
2. Trị: Hợp nhất các mảng con đã sắp xếp (lời giải cho các bài toán con) từ dưới lên trên để thu được mảng ban đầu đã sắp xếp (lời giải cho bài toán ban đầu).

Cách xác định bài toán chia để trị

Việc một bài toán có phù hợp để giải quyết bằng phương pháp chia để trị hay không thường có thể được xác định dựa trên các tiêu chí sau.

1. Bài toán có thể phân rã: Bài toán ban đầu có thể được chia thành các bài toán con nhỏ hơn, tương tự nhau, và có thể được chia nhỏ một cách đệ quy theo cùng một phương pháp.
2. Các bài toán con là độc lập: Không có sự chồng chéo giữa các bài toán con, chúng độc lập với nhau và có thể được giải quyết một cách độc lập.
3. Lời giải của các bài toán con có thể hợp nhất: Lời giải cho bài toán ban đầu được tạo ra bằng cách hợp nhất các lời giải của các bài toán con.

Rõ ràng, sắp xếp trộn thỏa mãn ba tiêu chí này.

1. Bài toán có thể phân rã: Chia mảng (bài toán ban đầu) thành hai mảng con (bài toán con) một cách đệ quy.
2. Các bài toán con là độc lập: Mỗi mảng con có thể được sắp xếp độc lập (các bài toán con có thể được giải quyết một cách độc lập).
3. Lời giải của các bài toán con có thể hợp nhất: Hai mảng con đã được sắp xếp (lời giải của bài toán con) có thể được trộn lại thành một mảng đã sắp xếp (lời giải của bài toán ban đầu).

Nâng cao hiệu quả thông qua chia để trị

Chia để trị không chỉ giải quyết hiệu quả các bài toán thuật toán, mà thường còn giúp nâng cao hiệu suất của thuật toán. Trong số các thuật toán sắp xếp, sắp xếp nhanh (quick sort), sắp xếp trộn và sắp xếp vun đống (heap sort) nhanh hơn sắp xếp chọn (selection sort), sắp xếp nổi bọt (bubble sort) và sắp xếp chèn (insertion sort) vì chúng áp dụng chiến lược chia để trị.

Điều này đặt ra một câu hỏi: Tại sao chia để trị lại có thể nâng cao hiệu suất của thuật toán, và logic nền tảng của nó là gì? Nói cách khác, tại sao việc chia một bài toán lớn thành nhiều bài toán con, giải quyết các bài toán con đó rồi hợp nhất các lời giải của chúng lại hiệu quả hơn so với việc giải quyết trực tiếp bài toán ban đầu? Câu hỏi này có thể được thảo luận từ hai khía cạnh: số lượng phép toán và tính toán song song.

Tối ưu hóa số lượng phép toán

Lấy "sắp xếp nổi bọt" làm ví dụ, việc xử lý một mảng có độ dài \(n\) yêu cầu độ phức tạp thời gian (time complexity) là \(O(n^2)\). Giả sử chúng ta chia mảng tại điểm giữa thành hai mảng con như hình bên dưới. Việc phân chia cần thời gian \(O(n)\), sắp xếp mỗi mảng con cần thời gian \(O((n / 2)^2)\), và trộn hai mảng con cần thời gian \(O(n)\), dẫn đến độ phức tạp thời gian tổng thể là:

\[ O(n + (\frac{n}{2})^2 \times 2 + n) = O(\frac{n^2}{2} + 2n) \]

Tiếp theo, chúng ta tính toán bất đẳng thức sau, trong đó vế trái và vế phải lần lượt biểu thị tổng số phép toán trước và sau khi phân chia:

\[ \begin{aligned} n^2 & > \frac{n^2}{2} + 2n \newline n^2 - \frac{n^2}{2} - 2n & > 0 \newline n(n - 4) & > 0 \end{aligned} \]

Điều này có nghĩa là khi \(n > 4\), số lượng phép toán sau khi phân chia sẽ ít hơn, và hiệu suất sắp xếp sẽ cao hơn. Lưu ý rằng độ phức tạp thời gian sau khi phân chia vẫn là bậc hai \(O(n^2)\), nhưng hằng số (constant term) trong độ phức tạp đã trở nên nhỏ hơn.

Đi xa hơn nữa, nếu chúng ta liên tục chia các mảng con từ trung điểm của chúng thành hai mảng con cho đến khi các mảng con chỉ còn một phần tử thì sao? Cách tiếp cận này chính là "sắp xếp trộn", với độ phức tạp thời gian là \(O(n \log n)\).

Suy nghĩ xa hơn, điều gì sẽ xảy ra nếu chúng ta thiết lập nhiều điểm phân chia và chia đều mảng ban đầu thành \(k\) mảng con? Tình huống này rất giống với sắp xếp theo thùng (bucket sort), vốn rất phù hợp để sắp xếp lượng dữ liệu khổng lồ, với độ phức tạp thời gian lý thuyết là \(O(n + k)\).

Tối ưu hóa tính toán song song

Chúng ta biết rằng các bài toán con được tạo ra bởi phương pháp chia để trị độc lập với nhau, vì vậy chúng thường có thể được giải quyết bằng tính toán song song (parallel computation). Điều này có nghĩa là chia để trị không chỉ có thể làm giảm độ phức tạp thời gian của thuật toán, mà còn thích hợp cho việc tối ưu hóa song song bởi hệ điều hành (operating system).

Tối ưu hóa song song đặc biệt hiệu quả trong môi trường đa nhân (multi-core) hoặc đa bộ xử lý (multi-processor), vì hệ thống có thể xử lý đồng thời nhiều bài toán con, tận dụng tối đa tài nguyên tính toán (computing resources) và giảm đáng kể tổng thời gian chạy (runtime).

Ví dụ, trong "sắp xếp theo thùng" được thể hiện trong hình dưới đây, chúng ta phân phối đều lượng dữ liệu khổng lồ vào các thùng khác nhau, và các nhiệm vụ sắp xếp cho tất cả các thùng có thể được phân phối cho các đơn vị tính toán khác nhau. Sau khi hoàn thành, các kết quả sẽ được hợp nhất.

Các ứng dụng phổ biến của chia để trị

Một mặt, chia để trị có thể được sử dụng để giải quyết nhiều bài toán thuật toán kinh điển.

• Tìm cặp điểm gần nhất (closest pair of points): Thuật toán này trước tiên chia tập hợp điểm thành hai phần, sau đó tìm cặp điểm gần nhất trong mỗi phần một cách riêng biệt, và cuối cùng tìm cặp điểm gần nhất nằm bắc cầu qua cả hai phần.
• Nhân số nguyên lớn (large integer multiplication): Ví dụ, thuật toán Karatsuba, phân rã phép nhân số nguyên lớn thành một vài phép nhân và phép cộng số nguyên nhỏ hơn.
• Nhân ma trận (matrix multiplication): Ví dụ, thuật toán Strassen, phân rã phép nhân ma trận lớn thành nhiều phép nhân và phép cộng ma trận nhỏ hơn.
• Bài toán Hanota (Hanota problem): Bài toán Hanota có thể được giải bằng đệ quy, đây là một ứng dụng điển hình của chiến lược chia để trị.
• Giải bài toán cặp nghịch thế (inversion pairs): Trong một dãy, nếu một số đứng trước lớn hơn một số đứng sau thì hai số này tạo thành một cặp nghịch thế. Việc giải bài toán cặp nghịch thế có thể sử dụng phương pháp chia để trị với sự trợ giúp của sắp xếp trộn.

Mặt khác, chia để trị được áp dụng rộng rãi trong việc thiết kế thuật toán và cấu trúc dữ liệu (data structure).

• Tìm kiếm nhị phân (binary search): Tìm kiếm nhị phân chia một mảng đã sắp xếp thành hai phần từ chỉ số trung điểm, sau đó quyết định loại bỏ một nửa dựa trên kết quả so sánh giữa giá trị mục tiêu và giá trị của phần tử ở giữa, và thực hiện bước tìm kiếm nhị phân tương tự trên khoảng còn lại.
• Sắp xếp trộn: Đã được giới thiệu ở đầu phần này, không cần giải thích thêm.
• Sắp xếp nhanh: Sắp xếp nhanh chọn một giá trị chốt (pivot value), sau đó chia mảng thành hai mảng con, một mảng chứa các phần tử nhỏ hơn chốt và mảng còn lại chứa các phần tử lớn hơn chốt, sau đó thực hiện thao tác phân chia tương tự trên hai phần này cho đến khi các mảng con chỉ còn một phần tử.
• Sắp xếp theo thùng: Ý tưởng cơ bản của sắp xếp theo thùng là phân tán dữ liệu vào nhiều thùng, sau đó sắp xếp các phần tử bên trong mỗi thùng, và cuối cùng lấy các phần tử từ mỗi thùng theo thứ tự để thu được một mảng đã sắp xếp.
• Các loại cây: Ví dụ như cây tìm kiếm nhị phân (binary search tree), cây AVL (AVL tree), cây đỏ-đen (red-black tree), cây B (B-tree), cây B+ (B+ tree), v.v. Các thao tác tìm kiếm, chèn và xóa của chúng đều có thể được xem là các ứng dụng của chiến lược chia để trị.
• Đống (heaps): Đống là một cây nhị phân đầy đủ (complete binary tree) đặc biệt, và các thao tác khác nhau của nó như chèn, xóa và vun đống (heapify) thực tế đều ngụ ý ý tưởng chia để trị.
• Bảng băm (hash table): Mặc dù bảng băm không trực tiếp áp dụng chia để trị, một số phương pháp giải quyết xung đột băm (hash collision) lại gián tiếp áp dụng chiến lược chia để trị. Ví dụ, các danh sách liên kết (linked list) dài trong phương pháp kết xích (chaining) có thể được chuyển đổi thành cây đỏ-đen để nâng cao hiệu suất tìm kiếm.

Có thể thấy rằng chia để trị là một ý tưởng thuật toán "âm thầm thâm nhập", được nhúng vào nhiều thuật toán và cấu trúc dữ liệu khác nhau.