Cấu trúc dữ liệu - Phân chia và chinh phục

Trong cách tiếp cận phân chia và chinh phục, bài toán trong tay đượ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.

Nói chung, chúng ta có thể hiểu divide-and-conquer cách tiếp cận theo quy trình ba bước.

Chia / ngắt

Bước này liên quan đến việc chia nhỏ vấn đề thành các vấn đề phụ nhỏ hơn. Các vấn đề phụ nên đại diện cho một phần của vấn đề ban đầ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 có thể chia được nữa. Ở giai đoạn này, các vấn đề phụ trở thành nguyên tử về bản chất nhưng vẫn thể hiện một phần nào đó 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 bài toán con nhỏ hơn được giải quyết, giai đoạn này kết 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 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 nhau đế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 đây dựa trên divide-and-conquer cách tiếp cận lập trình -

• 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 có sẵn để giải quyết bất kỳ vấn đề máy tính nào, nhưng những cách được đề cập là một ví dụ điển hình về phương pháp chia và chinh phục.