Báo Cáo Giải bài toán bằng phương pháp quy hoạch động

Lời giới thiệu

Trong thế giới hiện đại, mọi ngành nghề, mọi vấn đề đều liên quan đến tin học. Nhờ có máy tính mà những bài toán trước đây tưởng như không thể giải nổi ngày nay đã giải quyết được. Các vấn đề của đời sống đều có thể đưa về tổng quát hoá thành các bài toán. Mỗi một lĩnh vực tìm cách giải quyết chúng theo một góc độ riêng. Đối với chúng ta là những người hoạt động trong lĩnh vực tin học phải tìm cách giải quyết các bài toán này một cách khoa học, hiệu quả và luôn hướng tới một cách giải tối ưu nhất. Tuy nhiên không phải lúc nào chúng ta cũng tìm được cách giải tối ưu nhất mà có những vấn đề có thể giải được hoặc không hoặc trong trường hợp này nó tối ưu nhưng trong những trường hợp khác nó lại không tối ưu thậm trí còn có thể chứng minh được nó rất tồi.
Sau khi học song môn Phân tích thiết kế thuật toán tôi thấy bản thân mình cần có trách nhiệm vận dụng các kiến thức được trang bị để giải quyết một số bài toán thực tế mà trong đời sống hiện tại hay gặp phải tại các công ty đó chính là các bài toán tối ưu. Các bài toán này thường sử dụng các phương pháp Quy hoạch động, Tham lam, Vét cạn Quay lui. Trong nội dung chương trình đã học tôi lựa chọn phương pháp Quy hoạch động để giải quyết bài toán. Do trình độ còn nhiều hạn chế nên có thể thuật toán tôi đưa ra chưa hay, chưa tối ưu. Vậy kính mong Thầy và các bạn học viên trong lớp góp ý, bổ xung để bài toán được giải quyết một cách đầy đủ, tối ưu hơn mang lại lợi ích và ứng dụng thực tế hơn.

Xin chõn thành cảm ơn TS. Đào Thanh Tĩnh người đó giảng dạy và hướng dẫn tụi thực hiện bài tập này!

Mục lục
Lời giới thiệu . 2
Phần I. Phương pháp Quy hoạch động . 4
1. ý tưởng của thuật toán 4
2. Các bước giải bài toán bằng phương pháp quy hoạch động . 5

Phần II. ứng dụng phương pháp Quy hoạch động giải quyết bài toán thực tế. 6
1. Bài toán . 6
2. Phương pháp thiết kế . 7
3. Thuật toán . 8
4. Đánh giá thuật toán 9
5. Chứng minh tính đúng đắn của thuật toán 10
6. Ví dụ minh hoạ 11
7. So sánh với phương pháp xếp hàng tuần tự 13

Phần III. Chương trình . 16
Phần I. Phương pháp Quy hoạch động
1.ý tưởng của thuật toán:
Phương pháp Quy hoạch động là kỹ thuật từ dưới lên “Bottom up”. Để giải quyết bài toán người ta đi phân tích bài toán thành các bài toán nhỏ rồi tìm cách giải quyết bài toán này một cách tốt nhất, sau đó kết hợp nghiệm của chúng lại để giải quyết bài toán lớn hơn. Quá trình cứ tiếp tục cho đến khi nhận được kết quả của bài toán lớn hơn.
Trong quá trình giải các bài toán con dùng một bảng để lưu trữ kết quả, lời giải của bài toán con. Khi bài toán con tìm đến giá trị nghiệm của bài toán nhỏ hơn thì nó lấy giá trị này trong bảng mà không cần phải giải lại bài toán con. Đây chính là lợi thế và rất hiệu quả khi sử dụng phương pháp Quy hoạch động để giải quyết bài toán tìm được nghiệm tối ưu.
Tuy nhiên không phải lúc nào phương pháp Quy hoạch động cũng đem lại hiệu quả có khi giá trị ngiệm của bài toán con không phải là giá trị cần cho bài toán lớn hơn hoặc giá trị cần lưu trữ của các bài toán quá lớn không thể chấp nhận được lúc này cần phải lựa chọn phương pháp giải khác cho phù hợp.
2. Các bước giải bài toán bằng phương pháp quy hoạch động.
Bước 1: Tìm nghiệm của bài toán con (các trường hợp riêng) đơn giản nhất mà ta có thể giải quyết được, đây chính là điều kiện dừng của bài toán là phương án cơ sở.
Bước 2: Tìm ra công thức (hoặc quy tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của bài toán con cỡ nhỏ hơn (thường đây chính là công thức truy hồi), nhờ có công thức truy hồi này mà tính được (lấp đầy) được bảng phương án ở bước 3.
Bước 3: Tạo ra một bảng để lưu trữ các nghiệm của bài toán con bảng này gọi là bảng phương án (cân nhắc có nên dùng mảng để lưu trữ các nghiệm của bài toán con).
Bước 4: Tính nghiệm của bài toán con thông qua nghiệm của bài toán con cỡ nhỏ hơn.
Bước 5: Từ bảng phương án đã được làm đầy tìm cách xây dựng nghiệm của bài toán dựa trên tiêu trí mục đích đề ra của đầu bài. Đây chính là quá trình truy vết dựa vào kết quả của bảng phương án để tìm ra phương án tối ưu cuối cùng và cũng là kết quả của bài toán.