Như vậy là trong những bài trước, chúng ta đã cùng ôn lại qua những kiến thức cơ bản về cấu trúc dữ liệu, thuật toán, độ phức tạp của thuật toán, và cùng với đó là một giải thuật rất cơ bản là đệ quy. Và để tiếp nối series về các phương pháp thiết kế giải thuật, ở phần tiếp theo này, chúng ta sẽ cùng đi vào tìm hiểu về một trong những chiến lược thiết kế thuật toán phổ biến nhất, đó là chia để trị, hay divide and conquer.
Hãy cùng tìm hiểu xem "chia để trị" là gì, nó có những đặc điểm gì, có quan hệ như thế nào với đệ quy, và nó được ứng dụng vào để giải quyết những bài toán như thế nào nhé
Khái niệm chia để trị
Trong khoa học máy tính, chia để trị là một mô hình thiết kế thuật toán quan trọng, hoạt động dựa trên ý tưởng chia vấn đề cần giải quyết thành các vấn đề con cùng dạng với vấn đề đã cho, chỉ khác là cỡ của chúng nhỏ hơn, cứ như vậy lặp lại nhiều lần, cho đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp. Sau đó, lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu.
Một giải thuật chia để trị thường được thiết kế theo 3 bước như sau:
- Chia [divide]: Chia bài toán ra thành các bài toán nhỏ hơn [subproblems]. Về cơ bản thì những bài toán nhỏ này giống với bài toán ban đầu.
- Trị [conquer]: Giải quyết bài toán con trong trường hợp nó đủ nhỏ, còn không thì tiếp tục tiến hành chia tách nó ra thành những bài toán con nhỏ hơn nữa.
- Kết hợp [combine]: Kết hợp các kết quả từ bài toán con nhỏ nhất, để ra lời giải cho các bài toán con [subproblems], và cứ thế cuối cùng ra được lời giải cho bài toán ban đầu.
[Hình ảnh miêu tả giải thuật Chia để Trị. Image Source]
Đến đây, khi nhắc đến việc chia bài toán ban đầu thành các bài toán con đồng dạng, rồi tiếp tục chia các bài toán con đó thành các bài toán con nhỏ hơn, và cứ tiếp tục như vậy cho đến khi gặp được bài toán con đủ nhỏ, hay đủ đơn giản để giải quyết, thì chắc hẳn các bạn cũng sẽ thấy tư tưởng của nó khá quen thuộc với một khái niệm mà chúng ta đã từng tìm hiểu ở bài trước nhỉ. Đúng vậy, với cách thiết kế thuật toán chia để trị như ở trên, thì chúng ta thường liên tưởng ngay đến giải thuật đệ quy. Và trong thực tế, các giải thuật chia để trị cũng thường được implement bằng cách sử dụng đệ quy.
Ta có thể viết một lược đồ đơn giản để miêu tả một giải thuật chia để trị như sau
DivideConquer [A] { if [A đủ nhỏ] { return Solve [A] } else { for [i = 1; i 1: mid = len[A]//2 L = A[:mid] R = A[mid:] mergeSort[L] mergeSort[R] merge[A, L, R] def merge[A, L, R]: i = j = k = 0 while i