Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 11: Tham ăn - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán Tham Ăn TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung
Bài toán
Trả tiền thừa
Ba lô
Chiến lược tham ăn
Cây bao trùm nhỏ nhất
Thuật toán Prim
Thuật toán Kruskal 1 Bài Toán Trả Tiền Thừa
Các loại đồng xu 100c, 25c, 10c, 5c, 1c
Với khoản tiền cần trả lại, sao cho số lượng đồng xu là ít nhất.
Ví dụ: trả lại 189c
189 xu 1c => 189
18 xu 10c, 1 xu 5c, 4 xu 1c => 23 2 Bài Toán Trả Tiền Thừa
Số lượng đồng xu trả lại là ít nhất?
Ý tưởng:
Sử dụng lần lượt các đồng xu có mệnh giá từ lớn nhất đến nhỏ nhất
Hy vọng số lượng đồng xu là ít nhất
Ví dụ: trả lại 189c
1 xu 100c, 3 xu 25c, 1 xu 10c, 4 xu 1c => 9
9 xu đã ít nhất chưa 3 Lập Trình Động – Nhắc Lại
Thường áp dụng cho bài toán tối ưu
Xác định được lời giải tối ưu
Dựa trên lời giải tối ưu các bài toán con
Có thể phức tạp hóa vấn đề
Không khả thi với bài toán thực tế
Không gian tìm kiếm rộng
Thời gian tìm kiếm lâu 4 Chiến Lược Tham Ăn
Xác định phương án (lời giải) tốt nhất tại thời điểm quyết định
Chọn tối ưu cục bộ (local optimal)
Hi vọng tìm được tối ưu toàn cục (global optimum)
Có thể tìm được lời giải tối ưu với một số bài toán
Hiệu quả trong thực tế 5 Tham Ăn – Lập Trình Động
Đều áp dụng tìm lời giải tối ưu
Lập trình động
Thiết kế dưới lên (bottom-up design) 1. Giải bài toán nhỏ 2. Sau đó xác định phương án lời giải
Tham ăn
Thiết kế trên xuống (top-down design) 1. Xác định phương án lời giải 2. Sau đó giải bài toán nhỏ 6 Trả Tiền Thừa – Lập Trình Động
Giải bài toán nhỏ
Có sử dụng loại xu xxx hay không (co/không)
Số tiền trả tăng dần từ 0
Thiết kế bảng 2 chiều
Gần tương tự bài toán ba lô? 7 Trả Tiền Thừa – Tham Ăn
Các loại đồng xu 100c, 25c, 10c, 1c
Với khoản tiền cần trả lại, sao cho số lượng đồng xu là ít nhất.
Ví dụ: trả lại 133c
Kỹ thuật tham ăn?
1 xu 100c, 1 xu 25c, 8 xu 1c => 10
1 xu 100c, 3 xu 10c, 3 xu 1c => 7
Tham ăn có thể không cho lời giải tối ưu 8 Bài Toán Ba Lô
Nhặt đầy đồ vật vào ba lô sao cho tối ưu
Điều kiện khối lượng ba lô
Mục tiêu tối ưu lợi nhuận
Bài toán:
Có N đồ vật, với khối lượng wi và giá trị ti
Khối lượng ba lô không vượt quá M
Xác định tập đồ vật để tổng giá trị lớn nhất
Sử dụng kỹ thuật tham ăn 9 Bài Toán Ba Lô – Tham Ăn N = 5, M = 100 i A B C D E wi 10 20 30 40 50 ti 20 30 66 40 50 10 Bài Toán Ba Lô – Tham Ăn N = 5, M = 100 i A B C D E wi 10 20 30 40 50 ti 20 30 66 40 50 Tham ăn theo cân nặng (wi) Xi 1 1 1 1 0
= 156 11 Bài Toán Ba Lô – Tham Ăn N = 5, M = 100 i A B C D E wi 10 20 30 40 50 ti 20 30 66 40 50 Tham ăn theo giá trị (ti) Xi 0 1 1 0 1
= 146 12 Bài Toán Ba Lô – Tham Ăn N = 5, M = 100 i A B C D E wi 10 20 30 40 50 ti 20 30 66 40 50 Tham ăn theo tỉ trọng (ti / wi) Xi 1 1 1 1 0
= 156 13 Đồ Thị – Định Nghĩa Đồ thị có hướng  = ( , ) bao gồm
Tập các đỉnh
Tập  ⊆ × cạnh
Đồ thị vô hướng
Cặp cạnh không có thứ tự ,  = (, )
Đồ thị định hướng
Cặp cạnh có thứ tự ,  ≠ ,  Cả hai trường hợp,  = ( ). Nếu  liên thông,  ≥ − 1, ⟹ log  =  log 14 Đồ Thị – Ví Dụ vô hướng định hướng 15 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở Đồ Thị – Ví Dụ trọng số không trọng số 16 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở 5 7 11 15 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở Đồ Thị – Ví Dụ liên thông không liên thông 17 Đồ Thị – Biểu Diễn
Biểu diễn  = ( , , với  1, 2, ,  , là ma trận !"1 . . , 1 . . $ ! %, &  '1 nếu %, & ∈  0 nếu %, & ∉  18   lưu trữ Bài Toán Cây Bao Trùm Nhỏ Nhất
Input: Đồ thị liên thông, vô hướng   ( , ) có trọng số .:  → ℝ
Output: Cây bao trùm 2 – một cây kết nối tất cả các đỉnh với trọng số nhỏ nhất . 2 =
.(, ) 3,4 ∈5 19 Cây Bao Trùm Nhỏ Nhất – Ví Dụ
Input: 20 Cây Bao Trùm Nhỏ Nhất – Ví Dụ
Output 21 Cấu Trúc Con Tối Ưu Xóa một cạnh bất kỳ (, ) ∈ 2. Thì, cây 2 được chia thành 2 cây con 26 và 2 Định lý. Cây con T6 là cây bao trùm nhỏ nhất của 6 = ( 6, 6), 6 là đồ thị con của bao gồm các đỉnh của 26 6 = đỉnh của 26 6 = 8, 9 ∈ : 8, 9 ∈ 6 Tương tự với 2 22 Thuật Toán Prim :: tập các đỉnh kề các cạnh trong tập cạnh 2 Ban đầu tập : chứa một đỉnh tuỳ chọn của đồ thị , còn 2 rỗng. Tại mỗi bước lặp: 1. Chọn (, ) ngắn nhất,  ∈ :,  ∈ − : 2. Thêm đỉnh  vào tập đỉnh : 3. Thêm cạnh (, ) vào tập cạnh 2. Tiếp tục phát triển cây 2 cho tới khi : = , ta nhận được 2 là cây bao trùm 23 Thuật Toán Kruskal Tập 2 các cạnh được xây dựng dần từng bước xuất phát từ 2 rỗng. Tại mỗi bước cạnh (, ) được chọn thêm vào 2 là cạnh ngắn nhất trong các cạnh còn lại và không tạo thành chu trình với các cạnh đã có trong 2. 24