CHƯƠNG 5: PHƯƠNG PHÁP THAM LAM (The greedy method) I. Mở đầu 1. Ý tưởng 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. | Simpo PDFMergean d SpZit U n egiste edVers i o n - h tt p i m p o pdf. co m - 81 - CHƯƠNG 5 PHƯƠNG PHAP THAM LAM The greedy method I. Mô đầu 1. Y tưởng Phương pháp tham lam là kỹ thuật thiết kế thường được dung để 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. Tai 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 giai tối ưu cho bái toán nho tương ưng. Lơi giai cua bái toán đươc bo sung dán tưng bươc từ lơi giai cua các bái toán con. Lơi giai đươc xáỹ dựng như thế co chác lá lơi giai toi ưu cua bái toán Các lơi giai tìm đươc báng phương pháp tham lam thương chỉ lá chấp nhán đươc theo điểu kiến náo đo chưa chác lá toi ưu. Cho trươc mọt táp A gom n đoi tương tá cán phái chon mọt táp con S cua A. Vơi mọt táp con S đươc chon ra thoa mán các ỹểu cáu cua bái toán tá goi lá mọt nghiệm chap nhán đươc . Mot hám mục tiểu gán moi nghiệm chấp nhán đươc vơi mọt giá trị. Nghiệm toi ưu lá nghiệm chap nhán đươc má tái đo hám muc tiểu đát giá trị nho nhát lơn nhất . Đác trưng tham lam cua phương pháp thể hiện bơi trong moi bươc việc xử lí sệ tuán thểo mọt sự chon lưa trươc khong kể đến tình trang khong tốt co thể xáỹ ra khi thưc hiện lựa chon luc đáu. 2. MO hình Chon S từ táp táp A . Tính chất tham lam cua thuát toán định hương bơi hám Chon. - Khơi đông S 0 - Trong khi A 0 - Chon phán tử tot nhát cua A gán váo x x Chon A - Cáp nhát các đọì tương để chon A A- x - Nếu So x thoa mán ỹếu cáu bái toán thì Cáp nhát lơi giai S So x Thu tuc thuát toán tham lam co thể cái đát như sau input A output S lơi giai grệệdỹ A n S 0 whilệ A 0 x Chon A A A- x if So x chấp nhán đươc S So x Tran Tuấn Minh Khoa Toán-Tin Sưu tầm bởi Simpo PDFMergean d SpZit Unregistẹíed Vers i o n - h tt p i m p o pdf. co m - 82 - return S II. Bai toàn người du lich 1. Bài toàn Một nguời du lịch muôn tham quan n thành phô T1 . Tn . Xuất phát từ một thành phô nào đô người du lịch muôn đi qua tất cà các thành phô côn lai môi thành phô .
