PHƯƠNG PHÁP NHÁNH CẬN

-Dùng giải quyết bài toán tìm cấu hình tốt nhất trong các cấu hình liệt kê bằng thuật toán quay lui.

-Giảm thời gian thực hiện của thuật toán quay lui.

Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả năng đánh giá cấu hình ở từng bước.

Nếu tại bước thứ i đánh giá được cấu hình không tối ưu thì quay lui ngay không cần phải gọi đệ quy tìm tiếp các thành phần khác của cấu hình.

PHUONG PHAP THAM LAM

-Tham  ăn  hiểu  một  cách  dân  gian  là:  trong  một  mâm  có  nhiều  món  ăn,  món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba…

-Kĩ thuật tham ăn thường được vận dụng để giải bài toán tối ưu tổ hợp bằng cách xây dựng một phương án X. Phương án X được xây dựng  bằng cách lựa chọn  từng thành phần Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. 

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

Lời giải của bài toán được xây dựng từng bước từ lời giải các bài toán con

Đặc trưng tham lam của phương pháp thể hiện ở chỗ: tại mỗi bước xây dựng bài toán con, sẽ chọn một khả năng tốt nhất (tối ưu cục bộ). 

Tuy nhiên có thể lời giải cuối cùng lại không phải là lời giải tối ưu nhất

QUY HOẠCH ĐỘNG

Quy hoạch động thường dùng giải các bài toán tối ưu có bản chất đệ quy

Việc tìm nghiệm tối ưu của bài toán đã cho được thực hiện dựa trên việc tìm nghiệm tối ưu của các bài toán con.

Quy hoạch động bắt đầu từ việc giải các bài toán nhỏ nhất, kết quả của các bài toán con được ghi nhận lại để phục vụ cho việc giải các bài toán lớn hơn, cho tới khi giải được bài toán ban đầu. 

Thoát khỏi việc giải lại bài toán con mỗi khi cần ta đòi hỏi lời giải của nó.

*CÁC BƯỚC XÂY DỰNG THUẬT TOÁN

Xác định yêu cầu và điều kiện của lời giải tối ưu 

Tìm công thức đệ quy biểu diễn nghiệm tối ưu của bài toán lớn thông qua nghiệm tối ưu của các bài toán con.

Tổ chức cấu trúc dữ liệu lưu trữ kết quả tính toán bằng công thức đệ quy (Bảng phương án) 

Dựa vào kết quả ghi nhận truy vết tìm ra nghiệm tối ưu.