Chia để trị: là một mô hình thiết kế thuật toán quan trọng dựa trên đệ quy với nhiều phân nhánh. Thuật toán chia để trị hoạt động bằng cách chia bài toán thành nhiều bài toán nhỏ hơn thuộc cùng thể loại, cứ như vậy lặp lại nhiều lần, cho đến khi bài toán thu được đủ đơn giản để có thể giải quyết trực tiếp. Sau đó lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu.

Quay Lui: Về bản chất, tư tưởng của phương pháp là thử từng khả năng cho đến khi tìm thấy lời giải đúng. Đó là một quá trình tìm kiếm theo độ sâu trong một tập hợp các lời giải. Trong quá trình tìm kiếm, nếu ta gặp một hướng lựa chọn không thỏa mãn, ta quay lui về điểm lựa chọn nơi có các hướng khác và thử hướng lựa chọn tiếp theo. Khi đã thử hết các lựa chọn xuất phát từ điểm lựa chọn đó, ta quay lại điểm lựa chọn trước đó và thử hướng lựa chọn tiếp theo tại đó. Quá trình tìm kiếm thất bại khi không còn điểm lựa chọn nào nữa.

Quy trình đó thường được cài đặt bằng một hàm đệ quy mà trong đó mỗi thể hiện của hàm lấy thêm một biến và lần lượt gán tất cả các giá trị có thể cho biến đó, với mỗi lần gán trị lại gọi chuỗi đệ quy tiếp theo để thử các biến tiếp theo. Chiến lược quay lui tương tự với tìm kiếm theo độ sâu nhưng sử dụng ít không gian bộ nhớ hơn, nó chỉ lưu giữ trạng thái của một lời giải hiện tại và cập nhật nó.

Để tăng tốc quá trình tìm kiếm, khi một giá trị được chọn, trước khi thực hiện lời gọi đệ quy, thuật toán thường xóa bỏ giá trị đó khỏi miền xác định của các biến có mâu thuẫn chưa được gánvà kiểm tra tất cả các hằng số để tìm các giá trị khác đã bị loại trừ bởi giá trị vừa được gán

Các bài toán thỏa mãn ràng buộc là các bài toán có một lời giải đầy đủ, trong đó thứ tự của các phần tử không quan trọng. Các bài toán này bao gồm một tập các biến mà mỗi biến cần được gán một giá trị tùy theo các ràng buộc cụ thể của bài toán. Việc quay lui là để thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều tổ hợp chưa hoàn chỉnh, và nhờ đó giảm thời gian chạy

Phương pháp tham lam: là kỹ thuật thiết kế thường được dùng để giải các bài toán tối ưu. Phương pháp được tiến hành trong nhiều bước. Tại mỗi bước, theo một chọn lựa nào đó ( xác định bằng một hàm chọn), sẽ tìm một lời giải tối uư cho bài toán nhỏ tương ứng. Lời giải của bài toán được bổ sung dần từng bước từ lời giải của các bài toán con. Lời giải được xây dựng như thế có chắc là lời giải tối ưu của bài toán ?

Các lời giải theo phương pháp tham lam thường chỉ là chấp nhận được theo điều kiện nào đó, chưa chắc là tối ưu.

Cho trước một tập A gồm n đối tượng, ta cần phải chọn một tập con S của A. Với một tập con S được chọn ra thỏa mãn các yêu cầu của bài toán, ta gọi là một nghiệm chấp nhận được . Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị. Nghiệm tối ưu là nghiệm chấp nhận được mà tại đó hàm mục tiêu đạt giá trị nhỏ nhất ( lớn nhất).

Đặc trưng tham lam của phương pháp thể hiện bởi : trong mỗi bước việc xử lí sẽ tuân theo một sự chọn lựa trước, không kể đến tình trạng không tốt có thể xảy ra khi thực hiện lựa chọn lúc đầu.

Qui hoạch động:

-         Các bài toán con là không độc lập với nhau nghĩa là các bài toán con cùng có chung các bài toán “cháu”

-         Phân rã: chia bài toán cần giải thành những bài toán con nhỏ hơn có cùng dạng với bài toán ban đầu sao cho bài toán con kích thước nhỏ nhất có thể giải một cách trực tiếp. Bài toán xuất phát có thể coi là bài toán con có kích thước lớn nhất.

-         Giải các bài toán con và ghi nhận lời giải: lưu trữ lời giải của các bài toán con vào một bảng để sử dụng lại nhiều lần do đó không cần phải lặp lại cùng một bài toán.

-         Tổng hợp lời giải: lần lượt từ lời giải của các bài toán con kích thước nhỏ hơn xây dựng lời giải của bài toán con có kích thước lớn hơn cho đến khi thu được lời giải của bài toán xuất phát

So sánh sự giống và khác nhau giữa Quy Hoạch Động và Chia Để Trị

Giống:

-         Đều có 3 giai đoạn:

o   Phân rã: từ bài toán đầu hình thành nhiều bài toán nhỏ.

o   Trị: giải các bài toán con

o   Tổng hợp các lời giải thu được

Khác:

-         Quy hoạch động giải quyết xong bài toán lưu lại kết quả còn chia để trị thì không.

-         Quy hoạch động giải quyết bài toán con 1 lần còn chia để trị giải quyết nhiều lần.

-         Quy hoạch động giải quyết bài toán con từ dưới lên còn chia để trị từ trên xuống.

Sự khác nhau cơ bản giữa tham lam và quy hoạch động là với tham lam ta không cần biết các nghiệm của bài toán con để có thể thực hiện một lựa chọn nào đó và vì một bài toán có thể có nhiều nghiệm tối ưu nên thuật toán tham lam có thể hiệu quả hơn quy hoạch động.