tailieunhanh - Giải thuật 2004

Tham khảo sách 'giải thuật 2004', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Ch. 1: Dynamic Programming Dynamic Programming Ch. 1: Dynamic Programming Giôùi thieäu Dynamic programming giaûi baøi toaùn baèng caùch keát hôïp caùc lôøi giaûi cuûa caùc baøi toaùn con. (ôû ñaây “programming” khoâng coù nghóa laø laäp trình). So saùnh dynamic programming vaø “chia-vaø-trò” (divide-and-conquer) Giaûi thuaät chia-vaø-trò chia baøi toaùn thaønh caùc baøi toaùn con ñoäc laäp , giaûi chuùng baèng ñeä quy, keát hôïp chuùng ñeå coù lôøi giaûi cho baøi toaùn ban ñaàu. Giaûi thuaät dynamic programming caùc baøi toaùn con khoâng ñoäc laäp vôùi nhau: chuùng coù chung caùc baøi toaùn con nhoû hôn. giaûi moãi baøi toaùn con chæ moät laàn, vaø ghi nhôù lôøi giaûi ñoù trong moät baûng ñeå truy caäp khi caàn ñeán. Ch. 1: Dynamic Programming Baøi toaùn toái öu Baøi toaùn toái öu coù theå coù nhieàu lôøi giaûi moãi lôøi giaûi coù moät trò Tìm lôøi giaûi coù trò toái öu (cöïc tieåu hay cöïc ñaïi). Ch. 1: Dynamic Programming Nguyeân taéc cuûa dynamic programming Moät giaûi thuaät dynamic programming ñöôïc xaây döïng qua boán böôùc: 1. Xaùc ñònh caáu truùc cuûa moät lôøi giaûi toái öu. 2. Ñònh nghóa ñeä quy cho giaù trò cuûa moät lôøi giaûi toái öu. 3. Tính giaù trò cuûa moät lôøi giaûi toái öu töø döôùi leân (“bottom-up”). 4. Xaây döïng lôøi giaûi toái öu töø caùc thoâng tin ñaõ tính. Ch. 1: Dynamic Programming Nhaân moät chuoãi ma traän Cho moät chuoãi ma traän A1, A2,., An . Xaùc ñònh tích A1A2 An döïa treân giaûi thuaät xaùc ñònh tích cuûa hai ma traän. Bieåu dieãn caùch tính tích cuûa moät chuoãi ma traän baèng caùch “ñaët giöõa ngoaëc” (pa’renthesize) caùc caëp ma traän seõ ñöôïc nhaân vôùi nhau. Moät tích cuûa moät chuoãi ma traän laø fully parenthesized neáu noù laø moät ma traän hoaëc laø tích cuûa hai tích cuûa chuoãi ma traän fully parenthesized khaùc, vaø ñöôïc ñaët giöõa ngoaëc. Ví duï: moät vaøi tích cuûa chuoãi ma traän ñöôïc fully parenthesized A (AB) ((AB)C). . | Ch. 1: Dynamic Programming Dynamic Programming Ch. 1: Dynamic Programming Giôùi thieäu Dynamic programming giaûi baøi toaùn baèng caùch keát hôïp caùc lôøi giaûi cuûa caùc baøi toaùn con. (ôû ñaây “programming” khoâng coù nghóa laø laäp trình). So saùnh dynamic programming vaø “chia-vaø-trò” (divide-and-conquer) Giaûi thuaät chia-vaø-trò chia baøi toaùn thaønh caùc baøi toaùn con ñoäc laäp , giaûi chuùng baèng ñeä quy, keát hôïp chuùng ñeå coù lôøi giaûi cho baøi toaùn ban ñaàu. Giaûi thuaät dynamic programming caùc baøi toaùn con khoâng ñoäc laäp vôùi nhau: chuùng coù chung caùc baøi toaùn con nhoû hôn. giaûi moãi baøi toaùn con chæ moät laàn, vaø ghi nhôù lôøi giaûi ñoù trong moät baûng ñeå truy caäp khi caàn ñeán. Ch. 1: Dynamic Programming Baøi toaùn toái öu Baøi toaùn toái öu coù theå coù nhieàu lôøi giaûi moãi lôøi giaûi coù moät trò Tìm lôøi giaûi coù trò toái öu (cöïc tieåu hay cöïc ñaïi). Ch. 1: Dynamic Programming .