Báo Cáo Phương pháp quy hoạch động và bài toán chia quà sử dụng phương pháp quy hoạch động

Kết quả 1 đến 5 của 5

BÁO CÁO Phương pháp quy hoạch động và bài toán chia quà sử dụng phương pháp quy hoạch động

  1. #1
    Chuyên mục: TOÁN HỌC Mã số tài liệu: 82996
    Thể loại: Báo Cáo Hỗ trợ:  Hỗ trợ viên
    Giá: 10,000 đ Người bán: xuanbinh Đang Ngoại tuyến
    0902.365.878Giờ hành chính
    • TẢI VỀ (35.0 KB, 14 lượt tải)

  2. Giới thiệu tài liệu Phương pháp quy hoạch động và bài toán chia quà sử dụng phương pháp quy hoạch động

    I. Phương pháp Quy hoạch động

    1. Khái niệm:
    Một trong các hướng giải quyết các bài toán tối ưu trong tin học là sử dụng phương pháp “quy hoạch động”. “Quy hoạch” được hiểu theo nghĩa tối ưu, tức là giá trị của hàm mục tiêu phải là max hoặc min theo một nghĩa nào đó với các ràng buộc liên quan; còn “động” được hiểu theo hai nghĩa:
    - Phải đưa được bài toán về dạng công thức truy hồi Bellman.
    - Đưa bài toán ban đầu về các bài toán nhỏ hơn (ít nhất là hai bài toán nhỏ), giải các bài toán nhỏ bằng cách tìm nghiệm tối ưu của các bài toán này, sau đó tổng hợp lại thành lời giải tối ưu của bài toán lớn (theo cách thức truy vết).
    Qua đó ta có thể thấy, tư tưởng chủ đạo của phương pháp này dựa trên nguyên lý tối ưu của Bellman phát biểu như sau:
    “Nếu một dãy các lựa chọn là tối ưu thì mọi dãy con của nó cũng tối ưu”.
    Bên cạnh đó, khi thiết kế các thuật toán quy hoạch động ta thường dùng kỹ thuật “phân vùng để xử lý” nghĩa là để giải quyết một bài toán lớn ta chia nó thành nhiều bài toán con có thể giải quyết độc lập. Trong phương pháp quy hoạch động, việc thể hiện nguyên lý này là hết sức rõ ràng.
    Khi không biết chắc chắn cần giải quyết bài toán con nào, chúng ta giải quyết tất cả các bài toán con và lưu trữ những lời giải này với mục đích sử dụng chúng theo một sự phối hợp nào đó để giải quyết các bài toán tổng quát hơn. Hai phương pháp cần thiết phải có trong việc thiết kế một bài toán dưới dạng quy hoach động là phân tích và tổng hợp. Phân tích bài toán lớn thành các bài toán nhỏ, sau đó tổng hợp lại thành lời giải tối ưu của bài toán lớn.
    2. Các bước tổng quát của quy hoạch động:
    - Xây dựng hàm quy hoach động (hàm mục tiêu).
    - Lập bảng lưu lại giá trị của hàm.
    - Tính các giá trị ban đầu của bảng.
    - Tính các giá trị còn lại theo kích thước tăng dần của bảng cho đến khi đạt được giá trị tối ưu cần tìm.
    - Dùng bảng lưu để truy xuất (truy vết, phục hồi) lời giải tối ưu.
    3. Hạn chế của quy hoạch động:
    Phương pháp quy hoạch động không đem lại hiệu qủa trong các tình huống sau:
    - Sự kết hợp lời giải của các bài toán con chưa chắc đã cho ta lời giải của bài toán lớn hơn.
    - Số lượng các bài toán con cần giải quyết và lưư trữ kết quả có thể rất lớn, không thể chấp nhận được.

    II. Bài toán chia quà dùng quy hoạch động

    1. Bài toán:
    Minh và Nhật là hai anh em sinh đôi, trong ngày sinh nhật, hai anh em nhận được n món quà (n<=60). Trên món quà i có ghi giá tiền x[i]. Hai anh em quyết định phân chia n món quà thành hai phần, mỗi người được sở hữu một phần. Hãy giúp Minh và Nhật phân chia sao cho chênh lệch giá trị của hai phần quà là ít nhất.
    Dữ liệu vào: cho trong file Dulieu.pas gồm 2 dòng:
    - Dòng 1 chứa số nguyên n.
    - Dòng 2 chứa n số nguyên x[1] x[n] cách nhau bằng một dấu cách.
    Dữ liệu ra: để trong file Output.pas gồm 2 dòng:
    - Mỗi dòng ghi các số tương ứng với số thứ tự của các đồ chơi của từng người, cuối mỗi dòng là tổng giá trị của các đồ chơi đó.

    Hy vọng tài liệu Phương pháp quy hoạch động và bài toán chia quà sử dụng phương pháp quy hoạch động sẽ giúp ích cho bạn
  3. #2
    P
    paper Đang Ngoại tuyến Thành viên
    Ngày tham gia
    22-01-13
    Bài viết
    98
    Cảm ơn chủ thớt nhiều nhóe :-*


  4. #3
    M
    mrthibn91 Đang Ngoại tuyến Thành viên
    Ngày tham gia
    11-03-13
    Bài viết
    2
    Cảm ơn chủ thớt nhiều nhóe :-*


  5. #4
    N
    nguyenhung1962 Đang Ngoại tuyến Thành viên
    Ngày tham gia
    19-03-13
    Bài viết
    54
    Nội dung chuẩn


  6. #5
    K
    khovigai Đang Ngoại tuyến Thành viên
    Ngày tham gia
    02-05-13
    Bài viết
    28
    Chúc chủ thớt sức khỏe dồi dào để up nhiều tài liệu hay cho cộng đồng. Thanks!!!!!


Thông tin về chủ đề này

Users Browsing this Thread

Có 1 người đang xem chủ đề. (0 thành viên và 1 khách)