Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Tham ăn - Lê Nguyên Khôi

Nội dung text: Bài giảng Thiết Kế & Đánh Giá Thuật Toán - Tham ăn - Lê Nguyên Khôi

1. ế ế ậ a ườ ạ ọ ệ
2. ộ
   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
3. ả ề ừa
   Các lo i ng xu 100c, 25c, 10c, 5c, 1c
   Vi kho n ti n cn tr li, sao cho s lư ng ng xu là ít nh t.
   Ví d: tr li 189c
   189 xu 1c => 189
   18 xu 10c, 1 xu 5c, 4 xu 1c => 23 2
4. ả ề ừa
   S lư ng ng xu tr li là ít nh t?
   Ý tư ng:
   S dng ln lư t các ng xu có mnh giá t ln nh t n nh nh t
   Hy vng s lư ng ng xu là ít nh t
   Ví d: tr li 189c
   1 xu 100c, 3 xu 25c, 1 xu 10c, 4 xu 1c => 9
   9 xu ã ít nh t ch ưa 3
5. ậ ộ ắ ạ
   Th ư ng áp dng cho bài toán ti ưu
   Xác nh ư c li gi i ti ưu
   Da trên li gi i ti ưu các bài toán con
   Có th ph c tp hóa vn
   Không kh thi vi bài toán th c t
   Không gian tìm ki m rng
   Th i gian tìm ki m lâu 4
6. ế ượ a
   Xác nh ph ươ ng án (li gi i) tt nh t ti th i im quy t nh
   Ch n ti ưu cc b (local optimal)
   Hi vng tìm ư c ti ưu toàn cc (global optimum)
   Có th tìm ư c li gi i ti ưu vi mt s bài toán
   Hi u qu trong th c t 5
7. a ậ ộ
   u áp dng tìm li gi i ti ưu
   Lp 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 li gi i
   Tham n
   Thi t k trên xu ng (top-down design) 1. Xác nh ph ươ ng án li gi i 2. Sau ó gi i bài toán nh 6
8. ả ề ừa ậ ộ
   Gi i bài toán nh
   Có s dng lo i xu xxx hay không (co/không)
   S ti n tr tng dn t 0
   Thi t k bng 2 chi u
   Gn tươ ng t bài toán ba lô? 7
9. ả ề ừa a
   Các lo i ng xu 100c, 25c, 10c, 1c
   Vi kho n ti n cn tr li, sao cho s lư ng ng xu là ít nh t.
   Ví d: tr li 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 li gi i ti ưu 8
10. a
    Nh t y vt vào ba lô sao cho tối ưu
    iu ki n kh i lư ng ba lô
    Mc tiêu ti ưu li nhu n
    Bài toán:
    Có N v t, vi kh i l ư ng wi và giá tr ti
    Kh i lư ng ba lô không vư t quá M
    Xác nh tp vt tng giá tr ln nh t
    S dng k thu t tham n 9
11. a a N = 5, M = 100 i ABCDE wi 10 20 30 40 50 ti 20 30 66 40 50 10
12. a a N = 5, M = 100 i ABCDE wi 10 20 30 40 50 ti 20 30 66 40 50 Tham n theo cân nng (wi) Xi 1 1 1 1 0 = 156 11
13. a a N = 5, M = 100 i ABCDE 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
14. a a N = 5, M = 100 i ABCDE 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
15. ồ ị ị a th có hư ng = (, ) bao gm
    Tp các nh
    Tp ⊆ × cnh
    th vô hư ng
    Cp cnh không có th t , = (, )
    th nh hư ng
    Cp cnh có th t , ≠ , C hai tr ư ng hp, = (). Nu liên thông, ≥ − 1, ⟹ log = log 14
16. ồ ị ụ vô hư ng nh h ư ng Cu Gi y Cu Gi y HQG BX Kim Mã HQG BX Kim Mã Ngã tư S Ngã tư S 15
17. ồ ị ụ tr ng s không tr ng s Cu Gi y Cu Gi y 5 7 HQG BX Kim Mã HQG BX Kim Mã 11 15 Ngã tư S Ngã tư S 16
18. ồ ị ụ liênthông khôngliênthông 17
19. ồ ị ể ễ
    Bi u di n = ( , v i , là ma tr n lưu tr 18
20. a ỏ ấ
    Input: th liên thông, vô hư ng (, ) có tr ng s : → ℝ
    Output: Cây bao trùm – mt cây kt ni tt c các nh vi tr ng s nh nh t = (, ) , ∈ 19
21. a ỏ ấ ụ
    Input: 20
22. a ỏ ấ ụ
    Output 21
23. ấ ố Ư Xóa mt cnh bt k (, ) ∈ . Thì, cây ư c chia thành 2 cây con và nh lý. Cây con là cây bao trùm nh T nh t ca = ( , ), là th con ca bao gm các nh ca nh ca = = , ∈:,∈ Tươ ng t vi 22
24. ậ : tp các nh k các c nh trong t p c nh Ban u t p ch a m t nh tu ch n c a th , còn rng. Ti m i b ư c lp: 1. Ch n (, ) ng n nh t, ∈ , ∈ − 2. Thêm nh vào tp nh 3. Thêm c nh (, ) vào t p c nh . Ti p t c phát tri n cây cho t i khi = , ta nh n ư c là cây bao trùm 23
25. ậ a Tp các cnh ư c xây dng dn tng bư c xu t phát t rng. Ti mi bư c cnh (, ) ư c ch n thêm vào là cnh ng n nh t trong các cnh còn li và không to thành chu trình vi các cnh ã có trong . 24