Giải thuật chia để trị (divide and conquer)
Giải thuật chia để trị (Divide and Conquer) là gì?
Phương pháp chia để trị (Divide and Conquer) là một phương pháp quan trọng trong việc thiết kế các giải thuật. Ý tưởng của phương pháp này khá đơn giản và rất 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 đó thành các bài toán con nhỏ hơn. Tiếp tục chia cho đến khi các bài toán nhỏ này không thể chia thêm 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.
Nói chung, bạn có thể hiểu giải thuật chia để trị (Divide and Conquer) qua 3 tiến trình sau:
Tiến trình 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 sử dụng phương pháp đệ qui để chia nhỏ các bài toán cho đến khi không thể chia thêm nữa. 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.
Tiến trình 2: Giải bài toán con (Conquer/Solve)
Trong bước này, các bài toán con được giải.
Tiến trình 3: Kết hợp lời giải (Merge/Combine)
Sau khi các bài toán con đã được giải, trong bước này chúng ta sẽ kết hợp chúng một cách đệ qui để tìm ra giải pháp cho bài toán ban đầu.
Hạn chế của giải thuật chia để trị (Devide and Conquer)
Giải thuật chia để trị tồn tại hai hạn chế, đó là:
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.
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.
Ví dụ giải thuật chia để trị
Dưới đây là một số giải thuật được xây dựng dựa trên phương pháp chia để trị (Divide and Conquer):
- 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
Theo Tutorialspoint
Bài trước: Giải thuật tham lam (Greedy Algorithm)
Bạn nên đọc
-
Công thức tính diện tích hình quạt tròn
-
Công thức tính đường cao trong tam giác thường, cân, đều, vuông
-
Trọng tâm là gì? Công thức tính trọng tâm của tam giác
-
Cách tính diện tích hình tròn và chu vi hình tròn
-
Công thức tính đường chéo hình vuông, đường chéo hình chữ nhật
-
Công thức tính diện tích xung quanh hình nón cụt, diện tích toàn phần hình nón cụt, thể tích hình nón cụt
Theo Nghị định 147/2024/ND-CP, bạn cần xác thực tài khoản trước khi sử dụng tính năng này. Chúng tôi sẽ gửi mã xác thực qua SMS hoặc Zalo tới số điện thoại mà bạn nhập dưới đây:

- Code NgầuThích · Phản hồi · 1 · 17/08/20
- Code NgầuThích · Phản hồi · 0 · 17/08/20

Cũ vẫn chất
-
Hentai là gì? Code hen là gì?
Hôm qua -
Thơ vui về đàn ông và đàn bà
Hôm qua -
Corki DTCL mùa 7: Lên đồ, đội hình chuẩn Corki Pháo Thủ
2 ngày -
Cách viết mét vuông (m²), mét khối (m³) trên điện thoại, máy tính
Hôm qua -
Lệnh CS 1.1, mã Half Life trên máy tính
Hôm qua 3 -
Cách sửa lỗi định dạng số khi dùng Mail Merge trong Word
Hôm qua -
Hướng dẫn kích hoạt hoặc vô hiệu hóa bộ lọc SmartScreen trên Windows
Hôm qua -
Cách khôi phục danh bạ đã xóa trên iPhone
2 ngày -
Cách kết nối máy in qua WiFi, cài máy in qua WiFi trên Windows 10/11
Hôm qua -
Hướng dẫn tạo danh mục bảng biểu trong Word tự động
Hôm qua 3