Giải thuật Qui hoạch động
3 posters
Trang 1 trong tổng số 1 trang
Giải thuật Qui hoạch động
Tư tưởng cơ bản của phương pháp qui hoạch động là 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 bài toán con cần đến nghiệm của bài toán con cỡ nhỏ hơn, ta chỉ cần lấy lời giải ở bảng mà không cần giải lại. Chính vì thế mà giải thuật Qui hoạch động sẽ rất hiệu quả khi giải quyết các bài toán yêu cầu tìm tối ưu.
Để giải quyết một bài bằng phương pháp Qui hoạch động, chúng ta cần tiến hành những công việc sau:
- Tìm nghiệm của các bài toán nhỏ nhất.
- Tìm ra công thức (qui tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ nhơn.
- Tạo ra một bảng lưu trữ các nghiệm của các bài toán con, Sau đó tính nghiệm của bài toán con theo công thức đã tìm ra và lưu vào bảng.
- Từ các bài toán con đã giải quyết để tìm nghiệm của bài toán.
- Nếu bài toán có yêu cầu hiển thị các lựa chọn của phương án tối ưu thì thực hiện "Truy vết" để tìm.
=> =>
Để giải quyết một bài bằng phương pháp Qui hoạch động, chúng ta cần tiến hành những công việc sau:
- Tìm nghiệm của các bài toán nhỏ nhất.
- Tìm ra công thức (qui tắc) xây dựng nghiệm của bài toán con thông qua nghiệm của các bài toán con cỡ nhỏ nhơn.
- Tạo ra một bảng lưu trữ các nghiệm của các bài toán con, Sau đó tính nghiệm của bài toán con theo công thức đã tìm ra và lưu vào bảng.
- Từ các bài toán con đã giải quyết để tìm nghiệm của bài toán.
- Nếu bài toán có yêu cầu hiển thị các lựa chọn của phương án tối ưu thì thực hiện "Truy vết" để tìm.
=> =>
QHĐ là giải thuật rất hay và hiệu quả khi giải quyết bài toán "tối ưu".
Tuy nhiên, QHĐ đòi hỏi khá nhiều IQ của người lập trình
Được sửa bởi Admin ngày Fri Jan 28, 2022 12:01 pm; sửa lần 1.
TH~TACAZ~ and Lý Nguyễn Công Chính like this post
Cao Hải Dương- Năng động
- Posts : 59
Points : -329909
Reputation : -329968
Join date : 18/06/2018
Age : 19
Location : Bình Định
Trang 1 trong tổng số 1 trang
Permissions in this forum:
Bạn không có quyền trả lời bài viết
|
|