Chia để trị là thuật toán gì? Ví dụ áp dụng

Trong chương trình học phổ thông hoặc nâng cao, chắc hẳn bạn đọc đã được nghe về thuật ngữ "chia để trị" (divide and conquer). Vậy chia để trị là gì? Bài này sẽ đi vào sơ lược giúp bạn đọc nắm được các ý chính của chia để trị, từ đó áp dụng vào việc học tập và làm việc của mình.

Thuật toán chia để trị là một phương pháp quan trọng trong việc thiết kế các giải thuật, chủ yếu trong tin học và toán học. Ý tưởng của thuật toán này khá đơn giản và dễ hiểu. Khi cần giải quyết một bài toán, ta sẽ tiến hành chia bài toán lớn đó đó thành các bài toán con nhỏ hơn. Tiếp tục quà trình chia cho đến khi các bài toán nhỏ này không thể chia thêm được nữa, khi đó ta sẽ giải quyết các bài toán nhỏ nhất này và cuối cùng kết hợp giải pháp của tất cả các bài toán nhỏ để tìm ra giải pháp của bài toán ban đầu.

Trong ứng dụng, thuật toán chia để trị được thực hiện qua tiến trình 3 bước sau.

Bước 1: Chia nhỏ (divide/break)

Trong bước này, chúng ta chia bài toán ban đầu thành các bài toán con. Mỗi bài toán con nên là một phần của bài toán ban đầu. Nói chung, bước này thường sử dụng phương pháp đệ quy (recursion) để chia nhỏ cho đến bài toán nhỏ nhất. Khi đó, các bài toán con được gọi là atomic (nguyên tử), nhưng chúng vẫn biểu diễn một phần nào đó của bài toán ban đầu.

Bước 2: Giải bài toán con (conquer/solve)

Trong bước này, các bài toán con sẽ được giải một cách tốt nhất và gọn nhất.

Bước 3: Kết hợp (merge/combine)

Sau khi đã được giải các bài toán con, bước này chúng ta sẽ kết hợp chúng một cách đệ quy ngược để tìm ra giải pháp cho bài toán ban đầu.

1429png_53165ecb42eb2be57c7f.jpg

Các ví dụ áp dụng thuật toán chia để trị.

- Giải thuật sắp xếp trộn (Merge Sort)

- Giải thuật sắp xếp nhanh (Quick Sort)

- Giải thuật tìm kiếm nhị phân (Binary Search)

- Nhân ma trận của Strassen

...

Thuật toán nào dù đa năng cũng thường có vài hạn chế và chia để trị không ngoại lệ. Hạn chế của thuật toán chia để trị nằm trong việc làm thế nào để chia tách bài toán một cách hợp lý thành các bài toán con, bởi vì nếu các bài toán con được giải quyết bằng các thuật toán khác nhau thì sẽ rất phức tạp. Ngoài ra còn điểm hạn chế là việc kết hợp lời giải các bài toán con được thực hiện như thế nào để máy và người có thể hiểu được.

Minh họa: Giải thuật sắp xếp nhanh (Quick Sort)

Bước 1: Chia danh sách cần sắp xếp từ mảng array[1..n] thành hai danh sách con có kích thước tương đối bằng nhau nhờ chỉ số của một phần tử gọi là chốt, ta có thể chọn chốt là phần tử ở giữa, ở cuối, ở đầu hoặc phần tử ngẫu nhiên nào trong mảng sao cho thuận tiện.

Bước 2: Sau khi đã chia thành 2 mảng dựa vào phần tử chốt, ở bước này ta sắp xếp sao cho: những phần tử nhỏ hơn hoặc bằng giá trị phần tử chốt được đưa về phía trước và nằm trong mảng con thứ nhất, các phần tử lớn hơn giá trị của chốt được đưa về phía sau vào mảng con thứ hai. Cứ tiếp tục chia như vậy tới khi các mảng con đều có độ dài bằng 1 (không chia được nữa).

Bước 3: Bằng việc lắp ghép các bước giải quyết các bài toán con trên ta sẽ thu được kết quả là mảng ban đầu sẽ được sắp xếp.

1429png_c007f046ea1e2309f5e6.jpgMinh họa giải thuật sắp xếp nhanh (Quick Sort)

***

// hàm giải quyết việc sắp xếp các phần tử ở hai đầu của mảng 

// dựa vào phần tử chốt là phần tử cuối mảng

    int partition(int arr[], int low, int high) 

    { 

        // chốt được chọn ở đây là phần tử cuối mảng

        int pivot = arr[high];  

        int i = (low-1);  

        for (int j=low; j<high; j++) 

        {  

            // nếu phần tử nhỏ hơn hoặc bằng với chốt

            if (arr[j] <= pivot) 

            { 

                i++; 

  

                // đổi chỗ arr[i] và arr[j] 

                int temp = arr[i]; 

                arr[i] = arr[j]; 

                arr[j] = temp; 

            } 

        } 

        

        // đổi chỗ arr[i+1] và arr[high] (chốt)

        int temp = arr[i+1]; 

        arr[i+1] = arr[high]; 

        arr[high] = temp; 

        

        // trả về chỉ số của chốt

        return i+1; 

    } 

    

    // Hàm thực hiện quicksort

    void sort(int arr[], int low, int high) 

    { 

        // nếu chỉ số của đầu mảng nhỏ hơn chỉ số cuối mảng

        if (low < high) 

        { 

            // tìm chỉ số của chốt sau khi đã thực hiện sắp xếp

            int pi = partition(arr, low, high); 

  

            // lặp lại các bước với mảng từ phần tử đầu tiên đến chốt - 1

            // và từ chốt + 1 đến phần tử cuối cùng của mảng.

            sort(arr, low, pi-1); 

            sort(arr, pi+1, high); 

        } 

    }

***

(tổng hợp)

Đăng nhập để bình luận
Đang tải thêm ... The comment will be refreshed after 00:00.

Hãy là người đầu tin bình luận về bài viết này!