Bài giảng Phân tích và thiết kế thuật giải: Bài 4 - TS. Ngô Quốc Việt

Chia sẻ: You Can | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

143
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Phân tích và thiết kế thuật giải - Bài 4 cung cấp các kiến thức về quy hoạch động. Các nội dung được trình bày trong chương này gồm: Giới thiệu về quy hoạch động, so sánh giữa chia để trị và DP, các bước giải quyết, minh hoạ DP với bài toán Knapsack, bài toán ba lô 0-1,... Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Phân tích và thiết kế thuật giải: Bài 4 - TS. Ngô Quốc Việt

PHÂN TÍCH THIẾT KẾ THUẬT GIẢI QUY HOẠCH ĐỘNG TS. NGÔ QUỐC VIỆT 2015
Nội dung 1. Giới thiệu 2. Giải quyết một số bài toán bằng quy hoạch động.  Ba lô 0-1  Nhân ma trận 3. Bài tập 4. Hỏi đáp. 2
Giới thiệu  Quy hoạch động (dynamic programming) nhằm giải quyết bài toán tìm:  Trong đó, u là biến (một hay nhiều chiều), g(u) là hàm lượng giá, U là tập điều kiện ràng buộc.  Là thuật giải dạng bottom-up. Nghĩa là các bài toán “con” (không phải được chia từ bài toán lớn theo dạng chia để trị) được giải trước, và tổng hợp để ra kết quả của bài toán lớn. 3
Giới thiệu  Giống chia để trị ở chỗ: chia thành các bài toán con để giải quyết  Khác chia để trị ở chỗ  Các lời giải con không độc lập.  Các lời giải con được lưu trữ trong bảng kết quả. 4
So sánh giữa chia để trị và DP DP: lời giải con phụ thuộc  Chia để trị: lời giải con độc thuật giải luỹ thừa lập. 5
Các bước giải quyết  Xây dựng lời giải cho từng bài toán nhỏ.  Xây dựng công thức hồi quy nhằm xác định lời giải ở các bước sau.  Để tránh độ phức tạp luỹ thừa  lưu trữ các lời giải con vào bảng tra (để không phải giải lại như đệ quy). 6
Minh hoạ DP với bài toán Knapsack  DỮ LIỆU: n item  wi = cân nặng của item i  vi = giá trị của item i  W = sức chứa của knapsack  GIẢI PHÁP: tìm tập con S các item sao cho trọng lượng không vươt quá W  MỤC TIÊU: tìm cực đại giá trị của S 7
Bài toán Knapsack  Nghĩa là tìm: tập con S sao cho với  Được gọi là bài toán 0-1 Knapsack.  Chú ý: tìm cực đại theo giá trị thay vì theo trọng lượng hay kích thước của balô. 8
Thuật giải đơn giản  Sắp xếp các items theo “price per pound” vi/wi  Lấy từng item theo thứ tự này bỏ vào balô, nếu vẫn còn bỏ được (chú ý đến điều kiện ràng buộc).  Sinh viên hãy đánh giá thuật giải này (có tìm được KQ tối ưu không?) 9
Sử dụng DP cho Knapsack 0-1  Minh hoạ kết quả khác biệt giữa thuật giải đơn giản (tham lam) và DP 10
Sử dụng DP cho Knapsack 0-1  Đặt 𝑲[𝒋] là giá trị tối ưu của các item chứa trong ba lô kích thước 𝒋 (< 𝑾).  Yêu cầu cuối cùng cần tìm là K[M].  Để tìm K[W, n], cần xác định các lời giải con bao gồm 𝑖 (0 < 𝑖 < 𝑛) item đầu tiên cho ba lô có kích thước (0 < 𝑗 < 𝑊). 11
Sử dụng DP cho Knapsack 0-1  Ký hiệu các lời giải con là: 𝐾[𝑗, 𝑖].  Xét mảng hai chiều 𝑲[𝟎. . 𝑾, 𝟎. . 𝒏], trong đó  𝑲[𝒋, 𝒊] là giá trị tối ưu của các item trong giỏ có kích thước j, chỉ sử dụng các item 1,…,i.  Nhận xét: 𝑲[𝒋, 𝟎] = 𝟎 (không có item để lấy)  Nhận xét 𝑲[𝟎, 𝒊] = 𝟎 (kích thước balô bằng 0) 12
Sử dụng DP cho Knapsack 0-1  Công thức tính K[j, i] được xác định bởi các lời giải con như sau  K [ j, i  1] K [ j, i]  max  K [ j  wi , i  1]  vi  Trường hợp đặc biệt, nếu wi > W (kích thước item i lớn hơn cả kích thước ba lô, thì K[ j, i]  K[ j, i  1] 13
Sử dụng DP cho Knapsack 0-1  Giả sử đã tìm được K[j,i-1], hỏi cách tìm K[j, i]  Trả lời câu hỏi là có nên lấy item i bỏ vô balô (và có thể lấy các item khác ra cho có chỗ) không?  Nghĩa là chọn giữa  𝑲[ 𝒋 − 𝒘𝒊, 𝒊 − 𝟏] + 𝒗𝒊 (sử dụng item i)  𝑲[ 𝒋𝒊, 𝒊 − 𝟏] (không sử dụng item i) 14
Sử dụng DP cho Knapsack 0-1 K[ j,0] = 0 K[ j,i ] = max( K[ j-wi,i-1] +vi , K[ j,i-1] ) nếu j  wi K[ j,i ] = K[ j, i-1 ] nếu j < wi Công thức hồi quy trong thuật giải DP cho bài toán ba lô 0-1 15
Bảng kết quả ba lô 0-1 Hình minh hoạ từ dưới lên trên, cột biểu diễn kích thước ba lô, hàng biều diễn số lượng item 16
Bảng kết quả ba lô 0-1 17
Bảng kết quả ba lô 0-1  Cần giữ lại lời giải con nào đã chọn (để còn biết là các item nào trong ba lô) 18
Bảng kết quả ba lô 0-1  Theo hình trên, chúng ta sẽ ghi kết quả vào ma trận từ bottom-up, trái-phải 19
Bảng kết quả ba lô 0-1  Theo vết chúng ta sẽ biết được các item trong ba lô. •20 Kết quả: item 8, 5, 4, 2.