Tìm hiểu về cơ chế phân chia để trị(Divide and Conquer) trong thuật toán » http://139.180.218.5

Trong bài này tất cả chúng ta sẽ tiếp cận với chính sách được dùng nhiều trong những thuật toán đó là cách phân loại để trị ( Divide and Conquer ) hay chia để chinh phục, nhắm giúp thuật toán nhanh và hiệu suất cao hơn .

1. Giới thiệu

Trong cách tiếp cận phân chia và chinh phục(chia để trị), bài toán được chia thành các bài toán con nhỏ hơn và sau đó mỗi bài toán được giải quyết độc lập. Khi chúng ta tiếp tục chia các bài toán con thành các bài toán con nhỏ hơn, cuối cùng chúng ta có thể đạt đến một giai đoạn mà không thể phân chia được nữa. Những vấn đề con nhỏ nhất có thể có “nguyên tử” (phân số) được giải quyết. Lời giải của tất cả các bài toán con cuối cùng được hợp nhất để có được lời giải của một bài toán ban đầu.

Nhìn chung, tất cả chúng ta hoàn toàn có thể hiểu cách tiếp cận chia để trị trong quy trình tiến độ ba bước sau :

2. Phân chia hoặc ngắt(Divide/Break)

Bước này tương quan đến việc chia nhỏ yếu tố thành những yếu tố nhỏ hơn. Các yếu tố phụ nên đại diện thay mặt cho một phần của yếu tố khởi đầu. Bước này thường sử dụng một cách tiếp cận đệ quy để chia bài toán cho đến khi không có bài toán con nào hoàn toàn có thể chia được nữa. Ở tiến trình này, những yếu tố phụ trở thành nguyên tử về thực chất nhưng vẫn bộc lộ một phần nào đó của yếu tố trong thực tiễn .

3. Chinh phục / Giải quyết(Conquer/Solve)

Bước này nhận được rất nhiều yếu tố nhỏ hơn cần xử lý. Nói chung, ở Lever này, những yếu tố được coi là ‘ tự xử lý ’ .

4. Hợp nhất / Kết hợp(Merge/Combine)

Khi những bài toán con nhỏ hơn được xử lý, quá trình này phối hợp chúng một cách đệ quy cho đến khi chúng tạo thành một giải pháp của bài toán bắt đầu. Cách tiếp cận thuật toán này bằng hoạt động giải trí đệ quy những bước chinh phục và hợp nhất chúng gần nhau đến mức chúng Open thành một .
Ví dụ

Các thuật toán máy tính sau đây dựa trên cách tiếp cận lập trình chia để trị:

• Hợp nhất Sắp xếp(Merge Sort)
• Sắp xếp nhanh chóng(Quick Sort)
• Tìm kiếm nhị phân(Binary Search)
• Phép nhân ma trận của Strassen(Strassen’s Matrix Multiplication)
• Cặp gần nhất (điểm)(Closest pair (points))

Có nhiều cách khác nhau có sẵn để xử lý bất kể yếu tố máy tính nào, nhưng những cách được đề cập là một ví dụ nổi bật về giải pháp chia và chinh phục .

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu dụng, bạn hoàn toàn có thể tham gia những kênh sau của cafedev để nhận được nhiều hơn nữa :

Chào thân ái và quyết thắng!

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!