Cơ bản về Quy hoạch động

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Cơ bản về Quy hoạch động

Bài gửi by bí mật cuộc sống on 5/12/2010, 8:29 pm

Chào các bạn, chúng ta đều biết Quy hoạch động là một chiến lược rất hay trong Tin học. Nó xây dựng bài toán ban đầu từ những bài toán con nhỏ hơn có cùng vấn đề. Chính vì vậy, trong Quy hoạch động, nếu phát hiện ra cấu trúc con như vậy là ta đã tìm được cách giải quyết bài toán.

Một đặc điểm ngoài lề mà chúng ta cần chú ý là Quy hoạch động thường chỉ dùng để giải các bài toán thuộc lớp P (tức là tìm được thuật giải trong thời gian đa thức), còn đối với các bài toán NPC (chưa tìm ra thuật giải đa thức để giải quyết nó một cách hữu hiệu) thì ta cần phải sử dụng các chiến lược tìm kiếm kinh nghiệm trong đó.

Đối với các dạng toán về Quy hoạch động chỉ còn cách chúng ta rèn luyện nhiều qua các bài toán cơ bản, từ đó đúc rút về cách thực hiện chiến lược này như thế nào.

Mình xin giới thiệu với các bạn, một bài viết, khá thú vị, khá căn bản để chúng ta cùng rèn luyện thuật toán này của Thầy Nguyễn Thanh Tùng - giảng viên Trường Đại học Sư phạm Hà Nội (Hiện nay Thầy đang học Tiến sĩ về Công nghệ Phần mềm tại Mỹ Very Happy)

Download tại: Đây

Hi vọng tài liệu này sẽ giúp ích khi các bạn bước chân sử dụng chiến lược này.

Trong kỳ thi Olympic Tin học sinh viên toàn quốc năm 2009 có câu 1 sử dụng Quy hoạch động. Bài toán khá hay, các bạn download về thử giải xem Very Happy
avatar
bí mật cuộc sống
Moderator
Moderator

Nam Ngày sinh : 12/08/1989
Tuổi : 28
Ngày đăng ký : 05/12/2010

http://tosonnguyenxyz.summerhost.info/web/

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by Admin on 5/12/2010, 9:36 pm

Mình thấy quy hoạch động là một thuật toán rất hay, dùng để giải hầu hết các bài toán tối ưu. Dạng toán này cũng rất phổ biến trong các kỳ thi olympic tin học, tin học trẻ quốc gia và các giải quốc tế (IOI).

Rất cảm ơn bạn đã share một tài liệu khá hay về quy hoạch động. mình cũng xin chia sẻ một vài tài liệu khác về dạng QHD.

Download
Download
avatar
Admin
Quản trị viên
Quản trị viên

Nam Ngày sinh : 18/01/1992
Tuổi : 25
Ngày đăng ký : 25/04/2008

http://diendanpascal.forumotion.com

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by sptinhoc on 6/12/2010, 10:37 am

Chưa đọc nội dung nhưng đây là cái mà m rất cần. Thank
avatar
sptinhoc
Thành viên mới
Thành viên mới

Nam Ngày sinh : 12/10/1988
Tuổi : 29
Ngày đăng ký : 11/01/2010

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by quangfieu_s2 on 11/12/2010, 3:02 pm

hay
avatar
quangfieu_s2
Thành viên mới
Thành viên mới

Nam Ngày sinh : 28/03/1996
Tuổi : 21
Ngày đăng ký : 11/12/2010

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by hoang2596 on 11/12/2010, 3:09 pm

Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy
quangfieu_s2 đã viết:hay
Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy Very Happy
avatar
hoang2596
Thành viên mới
Thành viên mới

Nam Ngày sinh : 02/05/1996
Tuổi : 21
Ngày đăng ký : 11/12/2010

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by hoang2596 on 11/12/2010, 3:10 pm

quangfieu_s2 đã viết:hay
co hieu cai deo j dau ma keu hay


Cảnh cáo : hoang2596
Lý do : sử dụng từ ngữ thô tục.
avatar
hoang2596
Thành viên mới
Thành viên mới

Nam Ngày sinh : 02/05/1996
Tuổi : 21
Ngày đăng ký : 11/12/2010

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by bí mật cuộc sống on 11/12/2010, 6:17 pm

Bài 1 trong đề thi khối chuyên tin Olympic sinh viên này khá hay: Đề ở Đây

Ý tưởng: Sử dụng Quy hoạch động

Gọi max1 là giá trị lớn nhất của ak trong các sốtừ (a1, a2,…, ai)
Gọi max2 là giá trị lớn nhất của ak1 + 2ak2(k1 < k2) trong các số từ (a1, a2,…, ai)
Gọi max3 là giá trị lớn nhất của ak1 + 2ak2+ 3ak3 (k1 < k2 < k3) trong các số từ (a1, a2,…, ai).

Như vậy: Với 3 số a1, a2, a3thì:

max3 = a1+ 2a2 + 3a3
max2 = max(a1 + 2a2, a2+ 2a3, a1 + 2a3)
max1 = max(a1, a2, a3)

Ta sử dụng Quy hoạch động:

for i:= 4 to n do
begin
max3 = max(max3,max2 + 3ai);
max2 = max(max2,max1 + 2ai);
max1 = max(max1,ai);
end;
avatar
bí mật cuộc sống
Moderator
Moderator

Nam Ngày sinh : 12/08/1989
Tuổi : 28
Ngày đăng ký : 05/12/2010

http://tosonnguyenxyz.summerhost.info/web/

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by tranhoangnam on 1/1/2011, 8:37 am

ax ax. phe^ wa'

Cảnh báo : post bài không đúng chủ đề
avatar
tranhoangnam
Thành viên mới
Thành viên mới

Nam Ngày sinh : 27/11/1996
Tuổi : 21
Đến từ : hai phong
Ngày đăng ký : 01/01/2011

Về Đầu Trang Go down

Re: Cơ bản về Quy hoạch động

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết