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)

Tiến trình 2: Giải bài toán con (Conquer/Solve)

Tiến trình 3: Kết hợp lời giải (Merge/Combine)

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à:

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):