thiết kế và đánh giá thuật toán - trần tuấn minh -6

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...
Nội dung trích xuất từ tài liệu:
thiết kế và đánh giá thuật toán - trần tuấn minh -6 Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 81 - CHÖÔNG 5: PHÖÔNG PHAÙP THAM LAM (The greedy method) I. Môû ñaàu 1. YÙ töôûng Phöông phaùp tham lam laø kyõ thuaät thieát keá thöôøng ñöôïc duøng ñeå giaûi caùc baøi toaùn toái öu. Phöông phaùp ñöôïc tieán haønh trong nhieàu böôùc. Taïi moãi böôùc, theo moät choïn löïa naøo ñoù ( xaùc ñònh bằng moät haøm choïn), seõ tìm moät lôøi giaûi toái öu cho baøi toaùn nhoû töông öùng. Lôøi giaûi cuûa baøi toaùn ñöôïc boå sung daàn töøng böôùc töø lôøi giaûi cuûa caùc baøi toaùn con. Lôøi giaûi ñöôïc xaây döïng nhö theá coù chaéc laø lôøi giaûi toái öu cuûa baøi toaùn ? Caùc lôøi giaûi tìm ñöôïc baèng phöông phaùp tham lam thöôøng chæ laø chaáp nhaän ñöôïc theo ñieàu kieän naøo ñoù, chöa chaéc laø toái öu. Cho tröôùc moät taäp A goàm n ñoái töôïng, ta caàn phaûi choïn moät taäp con S cuûa A. Vôùi moät taäp con S ñöôïc choïn ra thoûa maõn caùc yeâu caàu cuûa baøi toaùn, ta goïi laø moät nghieäm chaáp nhaän ñöôïc . Moät haøm muïc tieâu gaén moãi nghieäm chaáp nhaän ñöôïc vôùi moät giaù trò. Nghieäm toái öu laø nghieäm chaáp nhaän ñöôïc maø taïi ñoù haøm muïc tieâu ñaït giaù trò nhoû nhaát ( lôùn nhaát). Ñaëc tröng tham lam cuûa phöông phaùp theå hieän bôûi : trong moãi böôùc vieäc xöû lí seõ tuaân theo moät söï choïn löïa tröôùc, khoâng keå ñeán tình traïng khoâng toát coù theå xaûy ra khi thöïc hieän löïa choïn luùc ñaàu. 2. Moâ hình Choïn S töø taäp taäp A . Tính chaát tham lam cuûa thuaät toaùn ñònh höôùng bôûi haøm Choïn. - Khôûi ñoäng S = ∅; - Trong khi A ≠ ∅ : - Choïn phaàn töû toát nhaát cuûa A gaùn vaøo x : x = Choïn (A) ; - Caäp nhaät caùc ñoái töôïng ñeå choïn : A = A-{x}; - Neáu S∪ {x} thoûa maõn yeáu caàu baøi toaùn thì Caäp nhaät lôøi giaûi : S = S∪ {x}; Thuû tuïc thuaät toaùn tham lam coù theå caøi ñaët nhö sau : input A[1..n] output S //lôøi giaûi; greedy (A,n) ≡ S = ∅; while ( A ≠ ∅) { x= Choïn(A); A = A-{x} if( S∪ {x} chaáp nhaän ñöôïc ) S = S∪ {x}; } Traàn Tuaán Minh Khoa Toaùn-Tin Sưu t m b i: www.daihoc.com.vn Simpo PDF Mergevaø ñaùnh giaù thuaät toaùn Thieát keá and Split Unregistered Version - http://www.simpopdf.com - 82 - return S; II. Baøi to aùn ngöôøi du lòch 1. Baøi toaùn Moät nguôøi du lòch muoán tham quan n thaønh phoá T1,.., Tn . Xuaát phaùt töø moät thaønh phoá naøo ñoù, ngöôøi du lòch muoán ñi qua taát caû caùc thaønh phoá coøn laïi, moãi thaønh phoá ñi qua ñuùng 1 laàn roái quay trôû laïi thaønh phoá xuaát phaùt. Goïi Cij laø chi phí ñi töø thaønh phoá Ti ñeán Tj . Haõy tìm moät haønh trình thoûa yeâu caàu baøi toaùn sao cho chi phí laø nhoû nhaát. 2. YÙ töôûng Ñaây laø baøi toaùn tìm chu trình coù troïng soá nhoû nhaát trong moät ñôn ñoà thò coù höôùng coù troïng soá. Thuaät toaùn tham lam cho baøi toaùn laø choïn thaønh phoá coù chi phí nhoû nhaát tính töø thaønh phoá hieän thôøi ñeán caùc thaønh phoá chöa qua. 3. Thuaät toaùn Input C= (Cij) output TOUR //Haønh trình toái öu, COST;//Chi phí töông öùng Moâ taû : TOUR := 0; COST := 0; v := u; // Khôûi taïo ∀k := 1 → n ://Thaêm taát caû caùc thaønh phoá // Choïn caïnh keá ) - Choïn laø ñoaïn noái 2 thaønh phoá coù chi phí nhoû nhaát tính töø TP v ñeán caùc thaønh phoá chöa qua. - TOUR := TOUR + ; //Caäp nhaät lôøi giaûi - COST := COST + Cvw ; //Caäp nhaät chi phí // Chuyeán ñi hoaøn thaønh TOUR := TOUR + ; COST := COST + Cvu ; Minh hoạ : 1 1 ⎡0 5⎤ 1 2 7 5 2 2 ⎢1 3⎥ 0 4 4 ⎢ ⎥ C = ⎢2 2⎥ ...