Chuyên đề Tin học PHƯƠNG PHÁP QUY HOẠCH ĐỘNG

Phương pháp quy hoạch động (dynamic programming) là một kĩ thuật đượcáp dụng để giải nhiều lớp bài toán, đặc biệt là các bài toán tối ưu.Phương pháp quy hoạch động dùng kĩ thuật bottom up (đi từ dưới lên):Xuất phát từ các trường hợp riêng đơn giản nhất, có thể tìm ngay ra nghiệm.
Nội dung trích xuất từ tài liệu:
Chuyên đề Tin học PHƯƠNG PHÁP QUY HOẠCH ĐỘNG Chuyeân ñeà Tin hoïc PHÖÔNG PHAÙP QUY HOAÏCH ÑOÄNG Bieân soaïn: Traàn Quang Quaù Giaùo vieân tröôøng PTTH chuyeân Löông Theá Vinh, Bieân Hoaø Thaùng 4 naêm 20021. GIÔÙI THIEÄU: Phöông phaùp quy hoaïch ñoäng (dynamic programming) laø moät kó thuaät ñöôïc aùp duïng ñeå giaûi nhieàu lôùp baøi toaùn, ñaëc bieät laø caùc baøi toaùn toái öu. Phöông phaùp quy hoaïch ñoäng duøng kó thuaät bottom up (ñi töø döôùi leân): Xuaát phaùt töø caùc tröôøng hôïp rieâng ñôn giaûn nhaát, coù theå tìm ngay ra nghieäm. Baèng caùch keát hôïp nghieäm cuûa chuùng, ta nhaän ñöôïc nghieäm cuûa baøi toaùn côõ lôùn hôn. Cöù theá tieáp tuïc, chuùng ta seõ nhaän ñöôïc nghieäm cuûa baøi toaùn. Trong quaù trình “ñi töø döôùi leân” chuùng ta seõ söû duïng moät baûng ñeå löu giöõ lôøi giaûi cuûa caùc baøi toaùn con ñaõ giaûi, khoâng caàn quan taâm ñeáùn noù ñöôïc söû duïng ôû ñaâu sau naøy. Khi giaûi moät baøi toaùn con, caàn ñeán nghieäm cuûa baøi toaùn con nhoû hôn, ta chæ caàn tìm kieám trong baûng, khoâng caàn phaûi giaûi laïi. Chính vì theá maø giaûi thuaät nhaän ñöôïc baèng phöông phaùp naøy raát coù hieäu quaû. 1.1. Öu ñieåm cuûa phöông phaùp quy hoaïch ñoäng: Chöông trình chaïy nhanh. • 1.2. Phaïm vi aùp duïng cuûa phöông phaùp quy hoaïch ñoäng: Caùc baøi toaùn toái öu: nhö tìm xaâu con chung daøi nhaát, baøi toaùn baloâ, tìm • ñöôøng ñi ngaén nhaát, baøi toaùn OÂtoâmat vôùi soá pheùp bieán ñoåi ít nhaát, … Caùc baøi toaùn coù coâng thöùc truy hoài. • 1.3. Haïn cheá cuûa phöông phaùp quy hoaïch ñoäng: Phöông phaùp quy hoaïch ñoäng khoâng ñem laïi hieäu quaû trong caùc tröôøng hôïp sau: Söï keát hôïp lôøi giaûi cuûa caùc baøi toaùn con chöa chaéc cho ta lôøi giaûi cuûa baøi • toaùn lôùn. Soá löôïng caùc baøi toaùn con caàn giaûi quyeát vaø löu tröõ keát quaû coù theå raát • lôùn, khoâng theå chaáp nhaän ñöôïc. Khoâng tìm ñöôïc coâng thöùc truy hoài. • Quy hoaïch ñoäng 2 Traàn Quang Quaù2. CAÁU TRUÙC CHUNG CUÛA CHÖÔNG TRÌNH CHÍNH: BEGIN {Chöông trình chính} Chuaån bò: ñoïc döõ lieäu vaø khôûi gaùn moät soá giaù trò; Taïo baûng; Tra baûng vaø in keát quaû; END.3. PHÖÔNG PHAÙP QUY HOAÏCH ÑOÄNG: 1) Tính nghieäm toái öu cuûa baøi toaùn trong tröôøng hôïp rieâng ñôn giaûn nhaát. 2) Tìm caùc coâng thöùc ñeä quy bieåu dieãn nghieäm toái öu cuûa baøi toaùn lôùn thoâng qua nghieäm toái öu cuûa caùc baøi toaùn con. 3) Tính nghieäm toái öu töø döôùi leân (bottom up) vaø ghi laïi caùc nghieäm toái öu cuûa caùc baøi toaùn con ñaõ tính ñeå söû duïng sau naøy.4. VÍ DUÏ: 4.1. Daõy Fibonaci: Ñeà baøi: In ra maøn hình 20 soá haïng ñaàu cuûa daõy Fibonaci. Bieát: F1 = 1 F2 = 1 F3 = 2 Fi = Fi-1 + Fi-2 vôùi i > 2 F4 = 3 Giaûi thuaät: 1) Tính nghieäm cuûa baøi toaùn trong tröôøng hôïp rieâng ñôn giaûn nhaát. F1 = F2 = 1 2) Tìm caùc coâng thöùc ñeä quy bieåu dieãn nghieäm toái öu cuûa baøi toaùn lôùn thoâng qua nghieäm toái öu cuûa caùc baøi toaùn con. Fi = Fi-1 + Fi-2 vôùi i > 2 Möôøi soá haïng ñaàu cuûa daõy Fibonaci: i 1 2 3 4 5 6 7 8 9 10 F[i] 1 1 2 3 5 8 13 21 34 55 4.2. Toå hôïp chaäp k cuûa n phaàn töû: k Ñeà baøi: Tính caùc phaàn töû cuûa maûng C[n, k] = Cn = soá toå hôïp chaäp k cuûa n phaàn töû, vôùi 0 ≤ k ≤ n ≤ 20. o n Bieát Cn = Cn = 1 k k-1 k Cn = Cn-1 + Cn-1Quy hoaïch ñoäng 3 Traàn Quang Quaù Giaûi thuaät: 1) Tính nghieäm cuûa baøi toaùn trong tröôøng hôïp rieâng ñôn giaûn nhaát. For i := 1 To n Do Begin C[0, i] := 1; C[i, i] := 1; End; 2) Tìm caùc coâng thöùc ñeä quy bieåu dieãn nghieäm toái öu cuûa baøi toaùn lôùn thoâng qua nghieäm toái öu cuûa caùc baøi toaùn con. ...