tailieunhanh - 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. | 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 programming 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 rat 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ế rat 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. CAU 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 PHAP quy HOACH ĐỘ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 toi ưu củá các bái toán con. 3 Tính nghiệm toi ưu tư dươi lện .