Ý tưởng thuật toán:

Có lẽ quan trọng và áp dụng rộng rãi nhất là kỹ thuật thiết kế “Chia để trị”. Nó phân rã bài toán kích thước n thành các bài toán con nhỏ hơn mà việc tìm lời giải của chúng là cùng một cách. Lời giải của bài toán đã cho được xây dựng từ các bài toán con này. Ta có thể nói vắn tắt ý tưởng chính của phương pháp này là : chia dữ liệu thành từng miền đủ nhỏ, giải bài toán trên các miền đã chia rồi tổng hợp kết quả lại.

Để có được mô tả chi tiết thuật toán chia để trị chúng ta cần phải xác định :

1. Kích thước tới hạn n₀ (Bài toán có kích thước nhỏ hơn n₀ sẽ không cần chia nhỏ)
2. Kích thước của mỗi bài toán con trong cách chia
3. Số lượng các bài toán con như vậy
4. Thuật toán tổng hợp lời giải của các bài toán con

Các phần xác định trong 2 và 3 phụ thuộc vào 4. Chia như thế nào để khi tổng hợp có hiệu quả (thường là tuyến tính)

Sơ đồ tổng quát thuật toán chia để trị

(Viết theo tựa Pascal):

Procedure D_and_C(n)

Begin

If n ( n 0 Then

Giải bài toán một cách trực tiếp

Else

• Chia bài toán thành r bài toán con kích thước n/k
• For (Mỗi bài toán trong r bài toán con) Do D_and_C(n)
• Tổng hợp lời giải của r bài toán con để thu được lời giải của bài toán gốc

End;

(Viết theo tựa C#:)

Nếu gọi D&C (R) - R là miền dữ liệu - là hàm thể hiện cách giải bài toán theo phương pháp chia để trị thì ta có thể viết :

void D&C(R)

{ If ( R đủ nhỏ)

giải bài toán;

Else

{ Chia R thành R1 , ..., Rm ;

for (i = 1; i <=m; i++)

D&C(R);

Tổng hợp kết quả ;

}

}