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 | Generated by Foxit PDF Creator Foxit Software http For evaluation only. Chương III Phương pháp Tham lam . Đặc trưng của chiến lược tham lam Bài toán tối ưu tổ họp Là một dạng của bài toán tối ưu nó có dạng tổng quát như sau Cho hàm f X xác định trên một tập hữu hạn các phần tử D. Hàm f X được gọi là hàm mục tiêu. Mỗi phần tử X a D có dạng X xl x2. xn được gọi là một phương án. Cần tìm một phương án X a D sao cho hàm f X đạt min max . Phương án X như thế được gọi là phương án tối ưu. Ta có thồ tìm thấy phương án tối ưu bàng phương pháp vét cạn nghĩa là xót tất cả các phương án trong tập D hữu hạn đổ xác đinh phương án tốt nhất. Mặc dù tập hợp D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bàng phương pháp vét cạn ta có the cần một thời gian mũ. Generated by Foxit PDF Creator Foxit Software http For evaluation only. Nội dung kĩ thuật tham ăn 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 đen khi hoàn chỉnh đủ n thành phẩn . Với mồi Xi ta sè chọn Xi tối ưu. Với cách này thi có the ờ bước cuối cùng ta không còn gì để chọn mả phải chấp nhận một giá trị cuối cùng còn lại. Áp dụng kĩ thuật tham ăn sẽ cho một giải thuật thời gian đa thức tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chú chua hẳn là tối ưu. Generated by Foxit PDF Creator Foxit Software http For evaluation only. . Đặc tính lựa chọn tham lam Toàn bộ phương pháp tối ưu có thổ đạt được từ việc chọn tối ưu trong từng bước chọn. Vồ khía cạnh nảy giải thuật tham lam khác với giải thuật quy hoạch động ở chỗ Trong quí hoạch động chúng ta thực hiện chọn cho từng bước nhưng việc lụa chọn này phụ thuộc vào cách giải quyết các bài toán con. Với giải thuật tham lam tại mỗi bước chúng ta chọn bất cứ cái gì lả tốt nhất vào thời điểm hiện tại và sau đó giải quyết các vấn
