›
›

Thuật giải AT, AKT

ppt 68 trang phuongnguyen 30
Download
Bạn đang xem 20 trang mẫu của tài liệu "Thuật giải AT, AKT", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptthuat_giai_at_akt.ppt

Nội dung text: Thuật giải AT, AKT

  1. Thuật giải AT, AKT Thuật giải AT (Algorithm for Tree): Mỗi đỉnh n tương ứng với một số g(n): giá thành của đường đi từ đỉnh ban đầu đến đỉnh n. Đỉnh: + Đỉnh đĩng (Closed) : là những đỉnh đã được xem xét. +Đỉnh mở (Open) : là những đỉnh giả thiết sẽ được xem xét ở bước sau. + Đỉnh ẩn (Hiden) : là những đỉnh mà tại đĩ hàm g(n) chưa được xác định.
  2. Thuật giải AT Bước 1: + Mọi đỉnh n, mọi giá trị g(n) đều là ẩn. + Mở đỉnh đầu tiên và gọi đĩ là đỉnh S. Đặt g(S) = 0. Bước 2 : Chọn đỉnh mở với giá thành g tương ứng là nhỏ nhất và gọi đĩ là đỉnh N. + Nếu N là mục tiêu: đường đi từ đỉnh ban đầu đến N là đường đi ngắn nhất và bằng g(N). Dừng (Success). + Nếu khơng tồn tại một đỉnh mở nào nữa: cây biểu diễn vấn đề khơng cĩ đường đi tới mục tiêu. Dừng (Fail). + Nếu tồn tại nhiều hơn 1 đỉnh N (nghĩa là cĩ 2 đỉnh N trở lên) mà cĩ cùng giá thành g(N) nhỏ nhất. Kiểm tra xem trong số đĩ cĩ đỉnh nào là đích hay khơng. Nếu cĩ: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N), dừng (Success). Nếu khơng cĩ: Chọn ngẫu nhiên một trong các đỉnh đĩ và gọi là đỉnh N. Bước 3: Đĩng đỉnh N và mở các đỉnh sau N (là những đỉnh cĩ cung hướng từ N tới). Tại mọi đỉnh S sau N tính : g(S) = g(N) + cost(N→S) Bước 4: Quay lại bước 2
  3. Thuật giải AT- Ví dụ 100 1 17 1 D A B C 10 1 1 20 12 E 1 G H I J F 1 1 1 1 K N 1 L M 1 O P 1 1 Q R 1 1 S T 1 U Trạng thái đích 1 V
  4. Thuật giải AT- Ví dụ Mọi đỉnh n, g(n) chưa biết. B1: Mở S, đặt g(S) = 0. 100 1 17 1 D B2: Đĩng S; mở A, B, C, D A B C 10 1 g(A) = g(S) + gt(S→A) = 0 + 100 = 100 1 20 12 E 1 G H I J F 1 g(B) = 0 + 17 = 17 1 1 1 K N 1 L M 1 g(C) = g(D) = 0 + 1 = 1 (min) O P 1 1 Chọn ngẫu nhiên giữa C, D: chọn C Q R 1 B3: Đĩng C, mở G, H: 1 S T g(A) = 100 1 U Trạng thái đích 1 g(B) = 17 V g(D) = 1 (min) g(G) = 11 g(H) = 21
  5. Thuật giải AT- Ví dụ B4: Đĩng D, mở I, J: 100 1 g(A) = 100 17 1 D g(B) = 17 A B C 10 1 g(I) = 13 1 20 12 g(J) = 2 (min) E 1 G H I J g(G) = 11 F 1 1 1 1 g(H) = 21 K N B5: Đĩng J, mở N: 1 L M 1 g(A) = 100 O P g(B) = 17 1 1 Q R g(I) = 13 1 g(G) = 11 1 g(H) = 21 S T g(N) = 3 (min) 1 U Trạng thái đích 1 V
  6. Thuật giải AT- Ví dụ B6: Đĩng N, mở P: 100 1 17 1 D g(A) = 100 A B C g(B) = 17 10 1 1 20 12 g(I) = 13 E 1 G H I J F 1 g(G) = 11 1 1 1 g(H) = 21 K N 1 L M 1 g(P) = 4 (min) O P B7: Đĩng P, mở R: 1 1 Q R g(A) = 100 1 1 g(B) = 17 S T g(I) = 13 1 Trạng thái đích g(G) = 11 U 1 g(H) = 21 V g(R) = 5 (min) 1 1 1 1 1 R là đích. Vậy đường đi là: S⎯⎯→D ⎯⎯→J ⎯⎯→N ⎯⎯→P ⎯⎯→R Nhận xét: Thuật tốn này chỉ sử dụng 3 thơng tin: đỉnh, cung và giá thành của cung.
  7. Thuật giải AKT – Tìm kiếm với tri thức bổ sung (Algorithm for Knowledgeable Tree Search): T ◼ Thuật giải A là thuật giải tìm kiếm đường đi tốt nhất đối với cây chỉ cĩ các thơng tin về đỉnh, cung và giá trị của cung. Trong nhiều trường hợp việc tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các tri thức thu được dựa trên các hiểu biết về tình huống vấn đề ở mỗi bước. Tri thức bổ sung ở mỗi đỉnh được tương ứng với một giá trị h(n). Chẳng hạn đĩ là ước lượng giá thành đường đi từ n đến mục tiêu. Ở ví dụ của giải thuật AT, ở bước đầu tiên : g(c) = g(d) = 1 T ◼ A chọn tùy ý một trong hai đỉnh c và d để xét tiếp. Nhưng thay vì chọn tùy ý chúng ta cĩ thể đặt câu hỏi “Đỉnh nào trong các đỉnh c và d gần mục tiêu hơn”, chúng ta ước lượng được: h(c) = 11 h(d) = 4 thì việc chọn đỉnh kế tiếp sẽ là d chứ khơng phải c. Do vậy tri thức bổ sung sẽ dựa trên cơ sở cực tiểu hĩa giá thành f ở mỗi bước : f(n) = g(n) + h(n)
  8. Thuật giải AKT Bước 1: Mọi đỉnh, cũng như các hàm g, h, f chưa biết. Mở đỉnh đầu tiên S, gán g(S) = 0 Sử dụng tri thức bổ sung để ước tính hàm h(S) Tính f(S) = g(S) + h(S) Bước 2: Chọn đỉnh mở cĩ f là nhỏ nhất và gọi là đỉnh N Nếu N là đích: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và và bằng g(N). Dừng (Success). Nếu khơng tồn tại đỉnh mở nào: cây biểu diễn vấn đề khơng tồn tại đường đi tới mục tiêu. Dừng (Fail). Nếu cĩ 2 đỉnh mở trở lên cĩ cùng giá trị f nhỏ nhất: Chúng ta phải kiểm tra xem những đỉnh đĩ cĩ đỉnh nào là đích hay khơng. + Nếu cĩ: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng (Success). + Nếu khơng cĩ: chọn ngẫu nhiên một trong các đỉnh đĩ và gọi đỉnh đĩ là N. Bước 3: Đĩng đỉnh N, mở mọi đỉnh sau N. Với mỗi đỉnh S sau N, tính: g(S) = g(N) + cost(S→N) Sử dụng tri thức bổ sung để tính h(S) và f(S): f(S) = g(S) + h(S) Bước 4: Quay lại bước 2.
  9. Bài tốn Tháp Hà Nội với n = 2 S0 Sn Các trường hợp của bài tốn là với trạng thái cột thứ ba: h(n) = 0 1 2 3
  10. g = 0 h = 2 f = 2 g = 1 g = 1 h = 2 h = 3 f = 3 (min) f = 4 g = 2 g = 2 g = 2 h = 2 h = 3 h = 1 f = 4 f = 5 f = 3 (min) g = 3 g = 3 g = 3 h = 2 h = 1 h = 0 f = 5 f = 4 f = 3 (Đích)
  11. Bài tốn taci 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 S0 Sn Cách 1: t 0 nếu ai = bi H = (ai , bi ) với (ai , bi ) = i=1 1 nếu ai bi
  12. 2 8 3 g = 0 1 6 4 h = 4 (có 4 số sai vị trí so với Goal) 7 5 f = 4 2 8 3 2 8 3 2 8 3 g = 1 g = 1 g = 1 1 6 4 h = 5 1 4 h = 3 1 6 4 h = 5 7 5 f = 6 7 6 5 f = 4 (min) 7 5 f = 6 2 8 3 2 3 2 8 3 g = 2 g = 2 g = 2 1 4 h = 3 1 8 4 h = 3 1 4 h = 4 7 6 5 f = 5 7 6 5 f = 5 (min) 7 6 5 f = 6 2 3 2 3 g = 3 g = 3 1 8 4 h = 2 1 8 4 h = 4 7 6 5 f = 5 (min) 7 6 5 f = 7 1 2 3 1 2 3 g = 4 g = 5 8 4 h = 1 8 4 h = 0 7 6 5 f = 5 (min) 7 6 5 f = 5 (Đích)
  13. Bài tốn taci Cách 2: t H = (ai ,bi ) i=1 với (ai,bi) là số lần ít nhất phải đẩy ơ ai = a theo chiều dọc hay ngang về đúng vị trí bi = b. Giả sử: 2 8 3 1 6 4 Số 1 2 3 4 5 6 7 8 Cộng Vị trí 1 1 0 0 0 1 2 5 7 5 0
  14. Bài tốn taci (tt) The algorithm tries to reach a state in G from SI as follows. 1. OPEN := {SI}, CLOSED := ;. 2. If some state in G is in OPEN, then stop: solution found. 3. If OPEN = ;, then stop: no solution. 4. Choose an element S 2 OPEN with the least f(S). 5. OPEN := OPEN\{S}, CLOSED := CLOSED[{S}. 6. OPEN := OPEN [ neighbors/successors of S not in OPEN nor in CLOSED. 7. Go to 2.
  15. Thuật giải A* - tìm kiếm đường đi trên đồ thị tổng quát Mở rộng thuật giải AKT thành thuật giải A* như sau: Bước 1: Mở đỉnh đầu tiên: S0 = E; {Trang thái ban đầu} g(S0) = 0; f(S0) = g(S0)+ h(S0) ; = {S0}; {Gán S0 cho tập đỉnh mở} C={}; {Gán tập đĩng C bằng rỗng} while  {} do Bước 2: Chọn một S trong  với f(S) nhỏ nhất:  =  - {S} C = C + {S} {Đĩng đỉnh S} Nếu S là đích thì dừng. Ngược lại qua bước 3.
  16. Thuật giải A* - tìm kiếm đường đi trên đồ thị tổng quát (tt) Bước 3: Xây dựng các đỉnh Si cĩ thể đến từ S nhờ các hành động cĩ thể chọn để thực hiện.Si sau S: •Tính g(Si) ứng với mỗi i: g(Si) = g(S) + cost(S->Si). •Ước lượng h(Si) •Gán f(Si)=g(Si)+h(Si) Bước 4: Đặt vào trong  những Si khơng cĩ trong  lẫn trong C. Với các Si đã cĩ trong  hoặc trong C thì gán: f(Si) = Min( fcũ(Si), fmới(Si) ). If Si cĩ trong C and fcũ(Si)< fmới(Si) then C := C – {Si}  :=  + {Si} {Mở Si} End A*
  17. Thuật giải A* - tìm kiếm đường đi trên đồ thị tổng quát (tt) Thuật giải này được diễn giải như sau : Bước 1: Mọi đỉnh và Mọi đỉnh, cũng như các hàng g, h, f chưa biết. Mở đỉnh đầu tiên S, gán g(S) = 0 Ước lượng hàm h(S) Gán f(S) = h(S)+ g(S) Bước 2: Chọn đỉnh mở cĩ f(S) là nhỏ nhất và gọi là đỉnh N •Nếu N là đích: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và và bằng g(N). Dừng (Success). •Nếu khơng tồn tại đỉnh mở nào: cây biểu diễn vấn đề khơng tồn tại đường đi tới mục tiêu. Dừng (Fail). •Nếu cĩ 2 đỉnh mở trở lên cĩ cùng giá trị f(S) nhỏ nhất: ta phải kiểm tra xem những đỉnh đĩ cĩ đỉnh nào là đích hay khơng.
  18. Thuật giải A* - tìm kiếm đường đi trên đồ thị tổng quát (tt) + Nếu cĩ: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N). Dừng (Success). + Nếu khơng cĩ: chọn ngẫu nhiên một trong các đỉnh đĩ và gọi đỉnh đĩ là N. Bước 3: Đĩng đỉnh N, và đối với mỗi đỉnh S sau N, chúng ta tính: g’(S) = g(N) + cost(S→N) Nếu đỉnh S đã mở và g(S) g’(S) thì bỏ qua S Ngược lại mở S và đặt g(S) = g’(S), tính h(S) và f(S): f(S) = g(S) + h(S) Bước 4: Quay lại bước 2.
  19. Bản đồ của Romania với khoảng cách tính theo km
  20. Khoảng cách đường chim bay từ một thành phố đến Bucharest.
  21. Ví dụ 1 Ban đầu (bước 1) : OPEN = {(Arad,g= 0,h’= 0,f’= 0)} CLOSE = {} Do trong OPEN chỉ chứa một thành phố duy nhất nên thành phố này sẽ là thành phố tốt nhất. Nghĩa là S0 = Arad.Ta lấy Arad ra khỏi OPEN và đưa vào CLOSE(bước 2). OPEN = {} CLOSE = {(Arad,g= 0,h’= 0,f’= 0)} Từ Arad cĩ thể đi đến được 3 thành phố là Sibiu, Timisoara và Zerind. Ta lần lượt tính giá trị f’, g và h’ của 3 thành phố này (bước 3).
  22. Ví dụ 1(tt) h’(Sibiu) = 253 g(Sibiu) = g(Arad)+cost(Arad,Sibiu) = 0+140= 140 f’(Sibiu) = g(Sibiu)+h’(Sibiu) = 140+253 = 393 h’(Timisoara) = 329 g(Timisoara) = g(Arad)+cost(Arad, Timisoara) = 0+118= 118 f’(Timisoara) = g(Timisoara)+ h’(Timisoara) = 118+329 = 447 h’(Zerind) = 374 g(Zerind) = g(Arad)+cost(Arad, Zerind) = 0+75= 75 f’(Zerind) = g(Zerind)+h’(Zerind) = 75+374 = 449 Do cả 3 nút Sibiu, Timisoara, Zerind đều khơng cĩ trong cả OPEN và CLOSE nên ta bổ sung 3 nút này vào OPEN (bước 4). OPEN = { (Sibiu,g= 140,h’= 253,f’= 393) (Timisoara,g= 118,h’= 329,f’= 447) (Zerind,g= 75,h’= 374,f’= 449)} CLOSE = {(Arad,g= 0,h’= 0,f’= 0)}
  23. Ví dụ 1(tt) Trong tập OPEN, nút Sibiu là nút cĩ giá trị f’ nhỏ nhất nên ta sẽ chọn Si = Sibiu. Ta lấy Sibiu ra khỏi OPEN và đưa vào CLOSE. OPEN = {(Timisoara,g= 118,h’= 329,f’= 447) (Zerind,g= 75,h’= 374,f’= 449)} CLOSE = {(Arad,g= 0,h’= 0,f’= 0) (Sibiu,g= 140,h’= 253,f’= 393)} Từ Sibiu cĩ thể đi đến được 4 thành phố là : Arad, Fagaras, Oradea, Rimnicu. Ta lần lượt tính các giá trị g, h’, f’ cho các nút này. h’(Arad) = 366 g(Arad) = g(Sibiu)+cost(Sibiu,Arad)= 140+140= 280 f’(Arad) = g(Arad)+h’(Arad)= 280+366 = 646
  24. Ví dụ 1(tt) h’(Fagaras) = 178 g(Fagaras) = g(Sibiu)+cost(Sibiu, Fagaras) = 140+99= 239 f’(Fagaras) = g(Fagaras)+ h’(Fagaras) = 239+178= 417 h’(Oradea) = 380 g(Oradea) = g(Sibiu)+cost(Sibiu, Oradea) = 140+151 = 291 f’(Oradea) = g(Oradea)+ h’(Oradea) = 291+380 = 671 h’(R.Vilcea) = 193 g(R.Vilcea) = g(Sibiu)+cost(Sibiu, R.Vilcea) = 140+80 = 220 f’(R.Vilcea) = g(R.Vilcea)+ h’(R.Vilcea) = 220+193 = 413 Nút Arad đã cĩ trong CLOSE. Tuy nhiên, do g(Arad) mới được tạo ra (cĩ giá trị 280) lớn hơn g(Arad) lưu trong CLOSE (cĩ giá trị 0) nên ta sẽ khơng cập nhật lại giá trị g và f’ của Arad lưu trong CLOSE. 3 nút cịn lại : Fagaras, Oradea, Rimnicu đều khơng cĩ trong cả OPEN và CLOSE nên ta sẽ đưa 3 nút này vào OPEN, đặt cha của chúng là Sibiu. Như vậy, đến bước này OPEN đã chứa tổng cộng 5 thành phố.
  25. Minh hoạ GT A*
  26. Minh hoạ GT A*
  27. Minh hoạ GT A*
  28. Minh hoạ GT A*
  29. Minh hoạ GT A*
  30. Minh hoạ GT A*
  31. Gọi n là tổng số đĩa cần chuyển. m là số đĩa đã nằm đúng vị trí ở cột thứ 3. k là số đĩa nằm sai vị trí ở cột thứ 3. Cĩ thể thấy bạn cần chuyển các đĩa nằm sai vị trí ra khỏi cột 3 (k đĩa), sau đĩ chuyển các đĩa chưa đúng vị trí vào đúng vị trí của nĩ (n-m-k đĩa), cuối cùng chuyển k đĩa sai vị trí vào lại. Như vậy bạn sẽ cĩ cơng thức là: k + (n-m-k) + k = n-m+k.
  32. VI DU 2 - THAP HA NO N=3 G=0 H=3 F=3 G=1 G=1 H=4 H=3 F=5 F=4 G=2 H=4 H=4 H=3 H=4 H=3 H=3 F=6 F=6 F=5 F=6 F=5 F=5
  33. VI DU VE GT A* - THAP HA NOI N=3 G=3 H=3 H=3 F=6 F=6 H=5 H=2 H=3 H=3 H=6 H=3 F=9 F=6 F=7 F=7 F=10 F=7 H=3 H=2 H=4 F=8 F=7 F=9
  34. Nhận xét AT AKT A* đỉnh đỉnh đỉnh Cung Cung Cung Giá thành cung Giá thành cung Giá thành cung Tri thức bổ sung Tri thức bổ sung Thao tác trên cây Thao tác trên cây Thao tác trên đồ thị Mối quan hệ giữa AT, AKT, A*: f(S) = (1 - ) g(S) + h(S) với 0 1 - Nếu = 0 → AT (khơng cĩ tri thức bổ sung) - Nếu = 1 → AKT (Phụ thuợc vào tri thức bổ sung) - Nếu = ½ → A*
  35. Thuật giải GTS (Greedy-Traveling Saleman) GTS1: Xây dựng một lịch trình du lịch cĩ chi phí Cost tối thiểu cho bài tốn trong trường hợp phải qua n thành phố với ma trận chi phí C và bắt đầu tại một đỉnh U nào đĩ. Thuật giải: Bước 1: {Khởi đầu} Đặt Tour := {}; Cost := 0; V := U; {V là đỉnh hiện tại đang làm việc} Bước 2: {Thăm tất cả các thành phố} For k := 1 To n Do qua bước 3;
  36. Thuật giải GTS (Greedy-Traveling Saleman) Bước 3: {Chọn cung kế tiếp} Đặt (V, W) là cung cĩ chi phí nhỏ nhất tình từ V đến các đỉnh W chưa dùng: Tour := Tour + {(V,W)}; Cost := Cost + Cost(V,W); Nhãn W được sử dụng Đặt V := W; {Gán để xét bước kế tiếp} Bước 4: {Chuyến đi hồn thành} Đặt Tour := Tour + {(V,U)}; Cost := Cost + Cost(V,U); Dừng.
  37. A 5 1 2 7 5 1 1 4 4 3 Ví dụ E C = 2 4 1 2 3 B 7 4 1 3 7 2 5 3 2 3 2 U = A 3 4 Tour = {} 4 Cost = 0 D 1 V = A C W {B, C, D, E} {Các đỉnh cĩ thể đến từ A} → W = B {Vì qua B cĩ giá thành bé nhất} Tour = {(A, B)} Cost = 1 V = B W {C, D, E} → W = E Tour = {(A, B),(B, E)} Cost = 1 + 3 = 4 V = E W {C, D}
  38. A 5 Ví dụ 1 E 3 B → W = C 7 2 2 Tour = {(A, B), (B, E), (E, C)} 3 4 Cost = 4 + 2 = 6 4 V = C D 1 W {D} C → W = D Tour = {(A, B), (B, E), (E, C), (C, D)} Cost = 6 + 1 = 7 V = D Tour = {(A, B), (B, E), (E, C), (C, D), (D, A)} Cost = 7 + 7 = 14 Kết quả: Tour du lịch A → B → E → C → D → A với giá thành Cost = 14. Nhận xét: Tuy nhiên kết quả nhỏ nhất sẽ là A → B → D → C → E → A với Cost=13. Sở dĩ khơng tối ưu do “háu ăn”: cứ hướng nào cĩ chi phí thấp thì đi, bất chấp về sau.
  39. GTS2 GTS2: Tạo ra lịch trình từ p thành phố xuất phát riêng biệt. Tìm chu trình của người bán hàng qua n thành phố (1<p<n) và p chu trình được tạo ra và chỉ chu trình tốt nhất trong p chu trình được giữ lại mà thơi (thuật giải này địi hỏi phải nhập n, p và C) Thuật giải: Bước 1: {Khởi đầu} k := 0; {Đếm số thành phố đi qua} Best := {}; {Ghi nhớ chu trình tốt nhất tìm thấy cĩ chi phí là Cost} Cost := ; Bước 2: {Bắt đầu chu trình mới} Chuyển qua bước 3 khi k<p, ngược lại dừng. Bước 3: {Tạo chu trình mới} k := k + 1; Call (GTS1(Vk)) : Trả về một chu trình T(k) ứng với chi phí C(k). Bước 4: {Cập nhật chu trình tốt nhất} Nếu C(k)< Cost thì Best := T(k); Cost := C(k);
  40. A 5 1 E 3 B GTS2 (tt) 7 2 2 3 4 4 Ví dụ:(Giải lại ví dụ trên) D 1 p=3 C K=0 Best={} Cost=∞ K=0 T(0)={(A,B),(B,E),(E,C),(C,D),(D,A)}, C(0)=14 C(0)=14 Best=T(0) Cost=14 K=1 T(1)={(B,A),(A,C),(C,D),(D,E),(E,B)}, C(1)=10 C(1)=10 Best=T(1) Cost=10 K=2 T(2)={(C,D),(D,E),(E,B),(B,A),(A,C)}, C(2)=10 C(2)=10>=Cost K=3>=p Dừng. Vậy nếu nhập p=3 chu trình thì chúng ta bắt đầu từ thành phố B và cĩ Cost nhỏ nhất. Nếu ta chọn p khác thì ta sẽ cĩ kết quả khác cĩ thể tốt hơn kết quả trên. Ví dụ p= 4 các bạn gỉai thử xem.
  41. Thuật tốn tơ màu tối ưu trên đồ thị Giả thiết 4 màu: Chúng ta nĩi 2 nước trên bản đồ vẽ trên mặt cầu hoặc là mặt phẳng là láng giềng của nhau nếu như chúng cĩ chung đường biên giới (chỉ xét những nước cĩ đường biên giới là một đường cong khép kín). ◼ Yêu cầu: tơ tồn bộ bản đồ mà chỉ sử dụng 4 màu sao cho khơng cĩ bất kỳ 2 nước láng giềng nào cĩ cùng chung một màu
  42. Đỉnh Lisbon Madrid Paris Berne Rome Viene Berlin Luxemburg Brusen Hague L M P Be R V Ber Lx Bru H Bậc 1 2 6 4 3 3 6 3 4 2 Lisbon 3 1 Brusels Paris Luxemburg 1 4 The Hague 4 4 Madrid Berne 3 2 2 Rome Berlin 1 Viene
  43. Thuật tốn: Lặp lại các bước sau cho đến khi nào tơ màu hết các đỉnh Bước 1: Chọn đỉnh cĩ bậc lớn nhất tơ màu i. Bước 2: Hạ bậc: - Đỉnh đã tơ màu: bậc = 0 - Những đỉnh cĩ liên hệ: bậc := bậc – 1 Bước 3: Đánh dấu các đỉnh liên hệ (bậc vừa trừ đi 1) cấm tơ màu i.
  44. Màu cấm tơ 3 2 3 2 2 3 1 1 1 2 1 1 1 2 Đỉnh L M P Be R V Ber Lx Bru H Màu tơ 1 2 1 3 2 1 2 4 3 1 Bậc 1 2 6* 4 3 3 6 3 4 2 Hạ bậc lần 1 1 1 0 3 2 3 5* 2 3 2 Hạ bậc lần 2 1 1 2 2* 2 0 1 2 1 Hạ bậc lần 3 1 1 1 0 1 1 2* 1 Hạ bậc lần 4 1* 1 1 1 0 0 0 Hạ bậc lần 5 0 1* 1 0 0 Hạ bậc lần 6 0 0 0 0 0
  45. Ví dụ 2: Phân cơng, lịch cơng tác, lịch thi đấu: •Cĩ một cuộc hội thảo khoa học với 9 chủ đề khác nhau, mỗi chủ đề diễn ra trong một buổi. •Các chủ đề sau khơng được đồng thời: AE, BC, CD, ED, ABD, AHI, BHI, DFI, DHI, FGH. •Xây dựng lịch sao cho số buổi diễn ra là ít nhất. •Gợi ý: số màu = số buổi.
  46. B A C I D H E G F
  47. 4 3 3 2 2 4 3 2 3 2 Màu cấm 1 1 1 1 1 2 1 1 tơ Đỉnh A B C D E F G H I Màu tơ 3 4 2 1 2 3 1 2 5 Bậc 5 5 2 7* 2 4 2 6 5 Hạ bậc 4 4 1 0 1 3 2 5* 4 3* 3 1 1 2 1 0 3 0 2* 1 0 2 1 2 0 0 2* 1 1 0 0 0
  48. Kết luận: ◼ Buổi 1: G, D ◼ Buổi 2: C, E, H ◼ Buổi 3: A, F ◼ Buổi 4: B ◼ Buổi 5: I
  49. Tìm kiếm leo đồi 1. Leo đồi đơn giản 2. Leo đồi dốc đứng 3. Đánh giá
  50. 1. Leo đồi đơn giản a. Định nghĩa: Tìm kiếm leo đồi là một trường hợp đặc biệt của tìm kiếm theo chiều sâu nhưng khơng thể quay lui. Trong tìm kiếm leo đồi, việc lựa chọn trạng thái tiếp theo được quyết định dựa trên một hàm Heuristic. b. Hàm heuristic là gì ? là ước lượng về khả năng dẫn đến lời giải . Ký hiệu là h
  51. 1. Leo đồi đơn giản (tt) c. Tư tưởng 1) Nếu trạng thái bắt đầu (T0) là trạng thái đích: thốt và báo là đã tìm được lời giải. Ngược lại, đặt trạng thái hiện hành (Ti) là trạng thái khởi đầu (T0) 2) Lặp lại cho đến khi đạt đến trạng thái kết thúc hoặc cho đến khi khơng tồn tại một trạng thái tiếp theo hợp lệ (Tk) của trạng thái hiện hành : a. Đặt Tk là một trạng thái tiếp theo hợp lệ của trạng thái hiện hành Ti. b. Đánh giá trạng thái Tk mới : b.1. Nếu là trạng thái kết thúc thì trả về trị này và thốt. b.2. Nếu khơng phải là trạng thái kết thúc nhưng tốt hơn trạng thái hiện hành thì cập nhật nĩ thành trạng thái hiện hành. b.3. Nếu nĩ khơng tốt hơn trạng thái hiện hành thì tiếp tục vịng lặp.
  52. 2. Leo đồi dốc đứng a. Định nghĩa: Giống như leo đồi đơn giản, chỉ khác ở điểm là leo đồi dốc đứng sẽ duyệt tất cả các hướng đi cĩ thể và chọn đi theo trạng thái tốt nhất trong số các trạng thái kế tiếp cĩ thể cĩ (trong khi đĩ leo đồi đơn giản chỉ chọn đi theo trạng thái kế tiếp đầu tiên tốt hơn trạng thái hiện hành mà nĩ tìm thấy).
  53. 2. Leo đồi dốc đứng (tt) b. Tư tưởng 1) Nếu trạng thái bắt đầu cũng là trạng thái đích thì thốt và báo là đã tìm được lời giải. Ngược lại, đặt trạng thái hiện hành (Ti) là trạng thái khởi đầu (T0) 2) Lặp lại cho đến khi đạt đến trạng thái kết thúc hoặc cho đến khi (Ti) khơng tồn tại một trạng thái kế tiếp (Tk) nào tốt hơn trạng thái hiện tại (Ti) a) Đặt S bằng tập tất cả trạng thái kế tiếp cĩ thể cĩ của Ti và tốt hơn Ti. b) Xác định Tkmax là trạng thái tốt nhất trong tập S Đặt Ti = Tkmax
  54. Ví dụ ◼ Bước 1: n:=Startnode; ◼ Bước 2: Nếu n là đích thì dừng (Success). ▪ Bước 3: Triển khai n, Tính hàm h với ni là con của n. Chọn ni tương ứng với h nhỏ nhất và gọi là nextn. ◼ Bước 4: Nếu khơng cĩ ni thì thốt (Fail). ◼ Bước 5: n:=nextn; ◼ Bước 6: Nhảy sang bước 2.
  55. H(n)=Tọa độ x của đích – Tọa độ x của n + Tọa độ y của đích – Tọa độ y của n n:=S h(S)=|4-1|+|4-1|=6 (min) h(A)=|4-2|+|4-3|=3 (min) <h(S) NextS = A n:=A h(B)=|4-2|+|4-4|=2 (min) h(C)=|4-2|+|4-2|=4 h(B)<h(A) NextA = B n:=B h(E)=|4-3|+|4-4|=1 (min) < h(B) NextB = E n:=E h(G)=|4-4|+|4-4|=0 (min) h(H)=|4-3|+|4-3|=2 h(G)<h(E) NextE = G (Đích- Dừng)
  56. 3. Đánh giá
  57. Một trường hợp thất bại của leo đèo kết hợp quay lui
  58. Thủ tục Min-Max: Áp dụng trong các trị chơi đối kháng 2 phía. Để ước lượng nước đi tốt dựa trên hàm ước lượng, chúng ta dùng thủ tục Min-Max như sau: Giả sử một trong hai người chơi: •Gọi một người là Max: tìm cách làm cực đại hàm ước lượng qua việc xác định giá trị hàm ước lượng ở mỗi nước đi cĩ khả năng rồi chọn nước đi tương ứng với giá trị lớn nhất. •Nhưng khi đĩ đối thủ của Max là Min thì lại tìm cách làm cực tiểu giá trị hàm ước lượng này.
  59. Như vậy ở mỗi mức của cây biểu diễn trị chơi: Nếu 1 đỉnh tương ứng với 1 nước đi của Max thì giá trị của đỉnh này sẽ lấy giá trị cực đại của các đỉnh tiếp sau đĩ. Nếu 1 đỉnh tương ứng với 1 nước đi của Min thì giá trị của đỉnh này sẽ lấy giá trị cực tiểu của các đỉnh tiếp sau đĩ.
  60. ◼ Ví dụ: Trị chơi Tic-Tac-Toe: ◼ Max = X (đi trước) ◼ Min = O ◼ Nguyên tắc: Nếu cĩ 3 con thẳng hàng thì thắng. ◼ Hàm ước lượng: ◼ f(x) = (Số dịng, số cột, số đường chéo cịn mở đối với Max)-(Số dịng, số cột, số đường chéo cịn mở đối với Min)
  61. 1 2 3 4 5 6 7 8 Ví dụ: Bài tốn 8 hậu: 1 + Cho 3 quân hậu đặt X trước vào bàn cờ A0 2 X {(1,4), (2,2), (3,8)} + Hãy đặt tiếp 5 quân 3 X hậu khác sao cho các con hậu khơng ăn nhau: 4 A B C 5 6 7 8
  62. int KTraXH(int A[][N], int x, int n) { int i, j, kq = 0; for(I = 0; I < n; i++) for(j = 0; j<n; j++) if(A[i][j] == x) kq++; return kq; } void Solve(int A[][N], int n) { while(!KTraMT(A,n)) { TimBuocDi(A,n); Xuat(A,n); } }
  63. int KTraMT(int A[][N], int x, int n) { int kq = 1; if(A[0][0] != 1) kq = 0; if(A[0][1] != 2) kq = 0; if(A[0][2] != 3) kq = 0; if(A[1][0] != 8) kq = 0; if(A[1][1] != 0) kq = 0; if(A[1][2] != 4) kq = 0; if(A[2][0] != 7) kq = 0; if(A[2][1] != 6) kq = 0; if(A[2][2] != 5) kq = 0; return kq; }
  64. Void TimBuocDi(int A[][N], int n) { int i, d, c; int h[4]; for(i = 0;I 0) swap(A[d][c],A[d][c-1]); h[0] = Heuristic(A,n); swap(A[d][c],A[d][c-1]); if(d-1>0) swap(A[d][c],A[d-1][c]); h[1] = Heuristic(A,n); swap(A[d][c],A[d-1][c]); if(c+1<n) swap(A[d][c],A[d][c+1]); h[2] = Heuristic(A,n); swap(A[d][c],A[d][c+1]); if(d+1<n) swap(A[d][c],A[d+1][c]); h[3] = Heuristic(A,n); swap(A[d][c],A[d+1][c]);
  65. Void TimBuocDi(int A[][N], int n) { int cs = 0; for (int i = 0 ; i h[i]) cs = i; if(cs == 0) swap(A[d][c],A[d][c-1]); if(cs == 1) swap(A[d][c],A[d-1][c]); if(cs == 2) swap(A[d][c],A[d][c+1]); if(cs == 3) swap(A[d][c],A[d+1][c]); }
  66. int Heuristic(int A[][N], int n) { int kq = 0; if(A[0][0] != 1) kq++; if(A[0][1] != 2) kq++; if(A[0][2] != 3) kq++; if(A[1][0] != 8) kq++; if(A[1][1] != 0) kq++; if(A[1][2] != 4) kq++; if(A[2][0] != 7) kq++; if(A[2][1] != 6) kq++; if(A[2][2] != 5) kq++; return kq; }