tailieunhanh - Phương pháp quy hoạch động trong việc giải một lớp “các bài toán tối ưu”

Quy hoạch động là dùng kĩ thuật đi từ dưới lên. Xuất phát từ trường hợp đơn giản nhất, có thể tìm ngay ra nghiệm bằng cách kết hợp nghiệm của chúng, ta nhận được nghiệm của bài toán cỡ lớn hơn. | Nội dung Text Phương pháp quy hoạch động trong việc giải một lớp các bài toán tối ưu .den color inherit .ttnd ol .ttnd ul .ttnd dl padding 0 0px 0 20px .ttnd hr margin 10px 0px .ttnd a href javascript void 0 .ttnd a href color inherit dtextscript p text-align left dtextscript img vertical-align middle PHƯƠNG PHÁP QUY HOẠCH ĐỘNG TRONG VIỆC lt br gt GIẢI MỘT LỚP CÁC BÀI TOÁN TỐI ƯU lt br gt lt br gt L NG C HƯNG lt br gt lt br gt TÓM TẮT lt br gt lt br gt Phương pháp quy hoạch động là một kĩ thuật được áp dụng để giải các bài toán tìm phương án tối lt br gt ưu . Vậy ý tưởng của phương pháp quy hoạch động thật đơn giản Để tránh việc tính lại mọi thứ lt br gt hai lần ta lưu giữ kết quả đã tìm được vào một mảng làm giả thiết cho việc tìm kiếm những kết quả lt br gt cho trường hợp sau . Chúng ta sẽ làm đầy dần giá trị của bảng này . Bởi các kết quả của những lt br gt trường hợp trước đã được giải quyết . Kết quả cuối cùng cũng chính là kết quả cần giải . lt br gt Quy hoạch động là dùng kĩ thuật đi từ dưới lên . Xuất phát từ trường hợp đơn giản nhất có thể lt br gt tìm ngay ra nghiệm bằng cách kết hợp nghiệm của chúng ta nhận được nghiệm của bài toán cỡ lt br gt lớn hơn . Cứ như thế ta nhận được đủ nghiệm của bài toán cần tìm .Trong quá trình đi Từ dưới lt br gt lên chúng ta sẽ sử dụng một bảng lưu giữ lời giải của các bài toán con đã được giải. Khi giải một lt br gt bài toán cần đến nghiệm của những bài toán nhỏ hơn ta chỉ việc tìm kiếm trong bảng . Chính vì vậy lt br gt mà thuật toán Quy hoạch động là rất có hiệu quả . lt br gt lt br gt ABSTRACT lt br gt lt br gt Dynamic programming is the method of solving complex problems for optimal solutions. lt br gt The ideas behind Dynamic programming are very simple lt br gt In order to avoid recalculating everything we store the solutions to the subproblems in a table lt br gt which is used as a fundamental theory to solve new problems. We will build up the values of the lt br gt table by adding the solved results of the .