Khi giải một bài toán con, cần đến nghiệm của bài toán con nhỏ hơn, ta chỉ cần tìm kiếm trong bảng, không cần phải giải lại. Chính vì thế mà giải thuật nhận được bằng phương pháp này rất có hiệu quả. | Chuyên đề Tin học PHƯƠNG PHÁP QUY HOÁCH ĐỘNG Biên sọạn Tran Quang Quá Giáọ viên trường PTTH chuyên Lương Thế Vinh Biên Họa Tháng 4 nám 2002 1. GIỚI THIỆU Phương pháp quy hoạch đọng dynamic prọgramming lá mọt kĩ thuạt đươc áp dung để giai nhiêu lơp bái tọán đác biêt lá các bái toán tọi ưu. Phương pháp quy họach đọng dung kĩ thuật bọttọm 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. Báng cách kết hơp nghiêm cua chung ta nhán đươc nghiêm cua bái tọán cơ lơn hơn. Cứ thế tiếp tuc chung ta sê nhán đươc nghiêm cua bái toán. Trọng quá trình đi từ dươi lên chung ta sê sư dung mọt báng đê lưu giư lơi giai cua các bái toán cọn đá giai không cán quan tám đến nọ đươc sư dung ơ đáu sau náy. Khi giai mọt bái toán cọn cán đến nghiêm cua bái toán cọn nhọ hơn ta chỉ cán tìm kiếm trọng báng khọng cán phái giai lai. Chính vì thế má giai thuát nhán đươc báng phương pháp náy rất cọ hiêu quá. . ưu điếm của phương pháp quy hoạch động Chương trình chay nhanh. . Phạm vi áp dung của phương pháp quy hoạch động Các bái toán tọi ưu như tìm xáu cọn chung dái nhất bái toán balọ tìm đương đi ngán nhất bái toán Ôtộmat vơi sộ phêp biến đổi ít nhất . Các bái toán cọ cọng thức truy họi. . Hạn chê cua phương pháp quy hoạch động Phương pháp quy họach đọng khọng đêm lai hiêu quá trọng các trương hơp sau Sự kết hơp lơi giai cua các bái toán cọn chưa chác chọ ta lơi giai cua bái toán lơn. sọ lương các bái toán cọn cán giai quyết vá lưu trữ kết quá cọ thế rất lơn khọng thê chấp nhán đươc. Khọng tìm đươc cọng thưc truy họi. Quy hoạch động 2 Trần Quang Quá 2. CÁU TRÚC CHUNG CỦA CHƯƠNG TRÌNH CHÍNH BEGIN Chương trình chính Chuẩn bị độc dư liệu vá khơi gán một sô giá trị Tạo báng Tra báng vá in kết quá END. 3. PHƯƠNG PHÁP quy hoạch ĐỘNG 1 Tính nghiệm tối ưu củá bái toán trong trương hơp riêng đơn gián nhất. 2 Tìm các cong thức đệ quy biếu diện nghiệm toi. ưu củá bái toán lơn thong quá nghiệm tói ưu củá các bái toán con. 3 Tính nghiệm tói ưu tư dươi lện .
