Trong cách tiếp cận phân chia và chinh phục, vấn đề trong tay, được chia thành các vấn đề nhỏ hơn và sau đó mỗi vấn đề được giải quyết độc lập. Khi chúng ta tiếp tục phân 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 có sự phân chia nào nữa. Những vấn đề phụ "phân tử" nhỏ nhất có thể được giải quyết. Giải pháp của tất cả các vấn đề phụ cuối cùng được hợp nhất để có được giải pháp cho một vấn đề ban đầu.
Nhìn rộng ra, chúng ta có thể hiểu cách tiếp cận chia và chinh phục trong một quy trình gồm ba bước.
Chia / nghỉ
Bước này liên quan đến việc phá vỡ vấn đề thành các vấn đề nhỏ hơn. Các vấn đề phụ nên thể hiện một phần của vấn đề ban đầu. Bước này thường có một cách tiếp cận đệ quy để phân chia vấn đề cho đến khi không có vấn đề phụ nào được chia thêm. Ở giai đoạn này, các vấn đề phụ trở thành nguyên tử trong tự nhiên nhưng vẫn đại diện cho một phần của vấn đề thực tế.
Chinh phục / Giải quyết
Bước này nhận được rất nhiều vấn đề nhỏ hơn cần giải quyết. Nói chung, ở cấp độ này, các vấn đề được coi là "tự giải quyết".
Hợp nhất / kết hợp
Khi các vấn đề phụ nhỏ hơn được giải quyết, giai đoạn này kết hợp đệ quy chúng cho đến khi chúng tạo thành một giải pháp cho vấn đề ban đầu. Cách tiếp cận thuật toán này hoạt động đệ quy và các bước chinh phục & hợp nhất hoạt động gần đến mức chúng xuất hiện như một.
Ví dụ
Các thuật toán máy tính sau dựa trên phương pháp lập trình chia và chinh phục -
- Hợp nhất sắp xếp
- Sắp xếp nhanh chóng
- Tìm kiếm nhị phân
- Phép nhân ma trận của Strassen
- Cặp gần nhất (điểm)
Có nhiều cách khác nhau để giải quyết bất kỳ vấn đề máy tính nào, nhưng được đề cập là một ví dụ điển hình về phương pháp phân chia và chinh phục.
Được cập nhật: 9 tháng 4 lúc 18:52:28 | Lượt xem: 608
