Tham lam

Giới thiệu

Phương pháp nhánh cận đã cải tiến được so với phương pháp quay lui nhờ vào việc chùng ta đánh giá trước được các nghiệm mở rộng. Tuy nhiên, không phải lúc nào chúng ta cũng đánh giá được, hoặc đã đánh giá nhưng số nghiệm còn lại cũng rất lớn. Trong một số bài toán, chúng ta buộc phải chấp nhận lấy những nghiệm có giá trị chỉ gần tối ưu để đổi lấy thời gian thực thi. Phương pháp tham lam ra đời để đáp ứng nhu cầu đó.

Tư tưởng chính của Tham Lam

Tư tưởng của tham lam cũng gần giống với nhánh cận ở chỗ khi đã chọn được thành phần thứ k, trước khi chọn thành phần k+1 ta cung đánh giá độ tốt của nghiệm mở rộng. Nhưng cách đánh giá của tham lam khác ở chỗ, nếu nhánh cận chúng ta phải đánh giá dựa vào giá trị ban đâu cho đến thời điểm đó thì với tham lam, ta chỉ đánh giá cục bộ tại thời điểm chọn. Nghĩa là ta chọn xi là thành phần tốt nhất trong Si.

Mô hình tổng quát

Hàm Select là hàm chọn trong Si ra một xi tốt nhất. Lưu ý rằng, xi chỉ tốt nhất cục bộ tại bước đó, về kết quả tổng thể, có thể nghiệm không phải nghiệm tối ưu. Nhưng điểm lợi là tham lam có độ phức tạp thấp nên chạy rất nhanh.

Ví dụ

Chúng ta quay lại với bài người đi du lịch đã xét bên phần nhánh cận, bây giờ chúng ta xét cách làm của tham lam:

Mô hình hóa:

Nghiệm bài toán có dạng vector X = (x1, x2, ..., xn, x1)

Điều kiện nghiệm:

x1 =1

xi != xj với mọi j,i

Tham lam:

Xuất phát từ thành phố 1, ta sẽ chọn x2 là thành phố gần Tp 1 nhất, chọn x3 là TP gần TP 2 nhất, ...

Các em quan sát 2 bộ dữ liệu sau đây:

Code chương trình các em xem tại trang 82, SGK chuyên Tin quyển 1 - HSD

Bài tập

Làm lại bài toán máy ATM theo cách tham lam và 4 bài ở phần nhánh cận cũng làm lại theo cách này. Sau đó rút ra kết luận về độ tối ưu của nghiệm và thời gian chạy.