›

Bài giảng Nhập môn trí tuệ nhân tạo - Chương 4, Phần 1: Các phương pháp tìm kiếm có sử dụng thông tin - Ngô Hữu Phúc

pdf 69 trang cucquyet12 8160
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Nhập môn trí tuệ nhân tạo - Chương 4, Phần 1: Các phương pháp tìm kiếm có sử dụng thông tin - Ngô Hữu Phúc", để 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:

  • pdfbai_giang_nhap_mon_tri_tue_nhan_tao_chuong_4_phan_1_cac_phuo.pdf

Nội dung text: Bài giảng Nhập môn trí tuệ nhân tạo - Chương 4, Phần 1: Các phương pháp tìm kiếm có sử dụng thông tin - Ngô Hữu Phúc

  1. Nhập môn Trí tuệ nhân tạo Chương 4-1 Các phương pháp tìm kiếm có sử dụng thông tin Biên soạn: TS Ngô Hữu Phúc Bộ môn Khoa học máy tính ĐT: 098 56 96 580 eMail: ngohuuphuc76@gmail.com 1 Các phương pháp tìm kiếm có kinh nghiệm
  2. Thông tin chung  Thông tin về nhóm môn học: TT Họ tên giáo viên Học hàm Học vị Đơn vị công tác (Bộ môn) 1 Ngô Hữu Phúc GVC TS BM Khoa học máy tính 2 Trần Nguyên Ngọc GVC TS BM Khoa học máy tính 3 Hà Chí Trung GVC TS BM Khoa học máy tính 4 Trần Cao Trưởng GV ThS BM Khoa học máy tính  Thời gian, địa điểm làm việc: Bộ môn Khoa học máy tính Tầng 2, nhà A1.  Địa chỉ liên hệ: Bộ môn Khoa học máy tính, khoa Công nghệ thông tin.  Điện thoại, email: 069-515-329, ngohuuphuc76.mta@gmail.com. 2 Các phương pháp tìm kiếm có kinh nghiệm
  3. Cấu trúc môn học  Chương 1: Giới thiệu chung.  Chương 2: Logic hình thức.  Chương 3: Các phương pháp tìm kiếm mù.  Chương 4: Các phương pháp tìm kiếm có sử dụng thông tin.  Chương 5: Các chiến lược tìm kiếm có đối thủ.  Chương 6: Các bài toán thỏa rằng buộc.  Chương 7: Nhập môn học máy. 3 Các phương pháp tìm kiếm có kinh nghiệm
  4. Bài 4: Các phương pháp tìm kiếm có kinh nghiệm Chương 4, mục: 4.1 – 4.12 Tiết: 1-3; 4-6; Tuần thứ: 5,6. Mục đích, yêu cầu: 1. Nắm được phương pháp xây dựng hàm đánh giá. 2. Nắm được một số phương pháp tìm kiếm dựa trên chiều sâu và chiều rộng có sử dụng thông tin. 3. Nắm được các phương pháp tìm kiếm phần tử tốt nhất. 4. Nắm được phương pháp tiếp cận giải thuật GEN. Hình thức tổ chức dạy học: Lý thuyết. Thời gian: 6 tiết. Địa điểm: Giảng đường do Phòng Đào tạo phân công Nội dung chính: (Slides) 4 Các phương pháp tìm kiếm có kinh nghiệm
  5. Nội dung 1. Giới thiệu chung; 2. Hàm đánh giá trong tìm kiếm kinh nghiệm; 3. Tìm kiếm tốt nhất đầu tiên (Best-first search); 4. Tìm kiếm ăn tham tốt nhất đầu tiên (Greedy best-first search); 5. Thuật toán leo đồi (Hill-climbing search); 6. Tìm kiếm beam (Beam search); 7. Heuristic chấp nhận được; 8. Tìm kiếm A* (A* search) 9. Tìm kiếm nhánh và cận (Branch and Bound) 10. Các phương pháp tìm kiếm cục bộ (Local search algorithms) 11. Tìm kiếm mô phỏng luyện kim (Simulated annealing search) 12. Thuật toán gen (Genetic algorithms) 5 Các phương pháp tìm kiếm có kinh nghiệm
  6. 1. Giới thiệu chung  Các kỹ thuật tìm kiếm mù rất kém hiệu quả, trong nhiều trường hợp không sử dụng được.  Trong chương này, nghiên cứu: Các phương pháp tìm kiếm kinh nghiệm (tìm kiếm heuristic). Các phương pháp sử dụng hàm đánh giá. 6 Các phương pháp tìm kiếm có kinh nghiệm
  7. 2. Hàm đánh giá trong tìm kiếm kinh nghiệm  Trong tìm kiếm sử dụng kinh nghiệm, với mỗi trạng thái u, xác định một hàm h(u), hàm đánh giá, hàm này được dùng để đánh giá trạng thái “tốt”, sao cho hy vọng sẽ tới đích tốt nhất.  Các kỹ thuật này được gọi chung là tìm kiếm kinh nghiệm (heuristic search).  Các giai đoạn cơ bản của tìm kiếm kinh nghiệm:  Tìm biểu diễn thích hợp mô tả các trạng thái và các toán tử.  Xây dựng hàm đánh giá,  Thiết kế chiến lược chọn trạng thái để phát triển ở mỗi bước. 7 Các phương pháp tìm kiếm có kinh nghiệm
  8. 2.1. Hàm đánh giá  Trong tìm kiếm có kinh nghiệm, hàm đánh giá đóng vai trò quan trọng.  Nếu xây dựng hàm đánh giá đúng bản chất vấn đề → tìm kiếm có hiệu quả,  Ngược lại, xây dựng không tốt có thể đi lệch hướng và tìm kiếm kém hiệu quả.  Việc xây dựng hàm đánh giá tùy thuộc vào vấn đề cần giải quyết. 8 Các phương pháp tìm kiếm có kinh nghiệm
  9. 2.2. Một số ví dụ về hàm đánh giá Ví dụ 1: Trong bài toán tìm kiếm đường đi trên bản đồ, có thể xây dựng hàm đánh giá:  Đường chim bay từ thành phố này sang thành phố khác, hoặc  Sử dụng khoảng cách thực trên đường đi giữa các thành phố, hoặc  Sử dụng cả khoảng cách và một số trọng số khác ảnh hưởng tới việc tìm kiếm (đóng vai trò làm tăng thời gian di chuyển giữa các thành phố),  9 Các phương pháp tìm kiếm có kinh nghiệm
  10. 2.2. Một số ví dụ về hàm đánh giá (tiếp) Ví dụ 2: 2 8 3 5 7 Xét bài toán 8 số, ta có thể xây dựng hàm đánh giá 6 4 1 như sau: Hàm H : 1 1 2 3 8 4 - với một trạng thái u, H1(u) là số quân ở sai vị trí. 7 6 5 - trong ví dụ trên: H1(u) = 4 Hàm H2: 3 2 8 - H2(u) là tổng khoảng cách giữa vị trí quân ở trạng 6 4 thái u với vị trí ở trạng thái đích. 7 1 5 - trong ví dụ trên: H2(u) = 9 10 Các phương pháp tìm kiếm có kinh nghiệm
  11. 3. Tìm kiếm tốt nhất đầu tiên (Best-first search)  Ý tưởng: Tìm kiếm tốt nhất đầu tiên = Tìm kiếm theo chiều rộng + Hàm đánh giá.  Ý nghĩa: khác với phương pháp tìm kiếm theo chiều rộng, các node không được phát triển lần lượt mà được lựa chọn dựa trên hàm đánh giá (tốt nhất), đỉnh này có thể ở mức hiện tại hoặc ở mức trên.  Cài đặt: Dùng hàng đợi ưu tiên. Sắp xếp các node trong hàng theo thứ tự giảm dần của hàm đánh giá.  Một số dạng mở rộng:  Tìm kiếm tham lam tốt nhất đầu tiên (Greedy best-first search).  Tìm kiếm A* (A* search). 11 Các phương pháp tìm kiếm có kinh nghiệm
  12. 3.1. Ví dụ về Best First Search Đầu vào: - Trạng thái đầu là A; - Trạng thái kết thúc là B. Thực hiện:  A được xét → C, D, E.  Chọn D, vì h(D) = 6 (min), sinh ra F,I. Xét không gian trạng thái sau  Trong số các đỉnh chưa xét C,E,F,I; chọn E vì h(E) = 7; sinh ra G và K.  Chọn G để phát triển; sinh ra B và H.  B là trạng thái kết thúc. 12 Các phương pháp tìm kiếm có kinh nghiệm
  13. 3.2. Cài đặt Best First Search Procedure Best_First_Search; Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu; 2. Loop do 1. If L rỗng then { thông báo thất bại; stop; } 2. Loại trạng thái u ở đầu danh sách L; 3. If u là trạng thái kết thúc then { thông báo thành công; stop; } 4. For mỗi trạng thái v kề u do Xen v vào danh sách L sao cho L được sắp theo thứ tự tăng dần của hàm đánh giá; 3. End; 13 Các phương pháp tìm kiếm có kinh nghiệm
  14. 4. Tìm kiếm tham lam tốt nhất đầu tiên (Greedy best-first search)  Ý tưởng:  Sử dụng hàm đánh giá f(n) = h(n) (heuristic);  Hàm f(n): ước lượng giá đến trạng thái đích.  Ý nghĩa:  Khác với phương pháp tìm kiếm tốt nhất đầu tiên, phương pháp này sử dụng hàm đánh giá đến trạng thái đích.  Ví dụ:  Trong tìm kiếm trên bản đồ, hàm h(n) = Khoảng cách theo đường chim bay từ n to thành phố đích.  Nhận xét:  GBFS chọn node “được cho là” gần với node đích để phát triển. 14 Các phương pháp tìm kiếm có kinh nghiệm
  15. 4.1. Tìm đường đi với giá tính theo km 15 Các phương pháp tìm kiếm có kinh nghiệm
  16. 4.1. Ví dụ về GBFS 16 Các phương pháp tìm kiếm có kinh nghiệm
  17. 4.1. Ví dụ về GBFS 17 Các phương pháp tìm kiếm có kinh nghiệm
  18. 4.1. Ví dụ về GBFS 18 Các phương pháp tìm kiếm có kinh nghiệm
  19. 4.1. Ví dụ về GBFS 19 Các phương pháp tìm kiếm có kinh nghiệm
  20. 4.2. Đánh giá GBFS  Đủ? Không – Có thể vào vòng lặp quẩn.  Độ phức tạp thời gian? O(bm) – nếu hàm heuristic xấp xỉ tốt trong thực tế thì thời gian chạy sẽ giảm đi rất nhiều.  Độ phức tạp không gian? O(bm) – lưu trữ tất cả các nodes.  Tối ưu? Không. 20 Các phương pháp tìm kiếm có kinh nghiệm
  21. 5. Tìm kiếm leo đồi (hill-climbring search)  Ý tưởng: Tìm kiếm leo đồi = tìm kiếm theo chiều sâu + hàm đánh giá  Ý nghĩa: Phương pháp này được thực hiện nhờ hàm đánh giá. Khác với phương pháp tìm kiếm theo chiều sâu, khi phát triển đỉnh u, chọn trong số các đỉnh con của u, đỉnh nào có nhiều hứa hẹn nhất thì phát triển.  Cài đặt: Sử dụng ngăn xếp có ưu tiên. 21 Các phương pháp tìm kiếm có kinh nghiệm
  22. 5.1. Ví dụ về Hill-climbing search Đầu vào:  Trạng thái đầu là A,  Trạng thái kết thúc là B. Thực hiện:  A được xét → C, D, E.  Chọn D, vì h(D) = 6 (min), sinh ra F,I. Xét không gian trạng thái sau  Trong số các đỉnh con của D, chọn I, vì h(I) = 8.  Với I được chọn, sinh ra B và G.  B là trạng thái kết thúc. 22 Các phương pháp tìm kiếm có kinh nghiệm
  23. 5.2. Cài đặt Hill-Climbing Search Procedure Hill_Climbing_Search; Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái đầu; 2. Loop do 1. If L rỗng then { thông báo thất bại; stop; } 2. Loại trạng thái u đầu danh sách L; 3. If u là trạng thái kết thúc then { thông báo thành công; stop; } 4. For mỗi trạng thái v kề u đặt v vào L sao cho các phần tử được đưa vào đầu danh sách L có đánh giá giảm dần; 3. End; 23 Các phương pháp tìm kiếm có kinh nghiệm
  24. 6. Tìm kiếm chùm (Beam search)  Ý tưởng: Tìm kiếm theo chiều rộng + k node để phát triển + hàm đánh giá  Ý nghĩa:  Tìm kiếm beam giống tìm kiếm theo chiều rộng,  Tuy nhiên trong tìm kiếm beam, hạn chế k đỉnh tốt nhất để phát triển. Như vậy, số đỉnh cần phát triển ở mức d là kd. 24 Các phương pháp tìm kiếm có kinh nghiệm
  25. 6.1. Ví dụ về Beam Search Đầu vào:  Trạng thái đầu là A,  Trạng thái kết thúc là B. Thực hiện: . Ví dụ lấy k = 2. . A được xét → C, D, E. Xét không gian trạng thái sau . Chọn D và E để phát triển, với D sinh ra F và I, với E sinh ra G và K. . Chọn I và G để phát triển, sinh ra B, G, B, H . Chọn được B (qua I) và B (qua G). . B là trạng thái kết thúc. 25 Các phương pháp tìm kiếm có kinh nghiệm
  26. 7. Heuristic chấp nhận được Trong kỹ thuật tìm kiếm, để việc tìm kiếm có hiệu quả sẽ sử dụng hàm đánh giá để hướng dẫn tìm kiếm. Các kỹ thuật này thuộc nhóm tìm kiếm Heuristic.  Giả sử u là một trạng thái đạt tới (có đường đi từ trạng thái đầu u0 tới u); hàm đánh giá được xác định như sau:  g(u): đánh giá độ dài đường đi ngắn nhất từ u0 tới u.  h(u): đánh giá độ dài đường đi ngắn nhất từ u tới trạng thái đích. Hàm h(u) được gọi là chấp nhận được nếu với mọi trạng thái u, thì h(u) ≤ độ dài đường đi ngắn nhất thực tế từ u tới trạng thái đích.  Để tăng hiệu quả của quá trình tìm kiếm: f(u) = g(u) + h(u) 26 Các phương pháp tìm kiếm có kinh nghiệm
  27. 7.1. Heuristics chấp nhận được trong A*  Hàm heuristic h(u) là chấp nhận được nếu với mọi node u, h(u) ≤ h*(u), Trong đó h*(u) là chi phí thực để đi đến đích từ u.  Ý nghĩa: Heuristic chấp nhận được không bao giờ đánh giá chi phí cao quá thực tế.  Ví dụ: hSLD(u) là Heuristic chấp nhận được.  Định lý: Nếu h(n) là chấp nhận được, A* là thuật toán cho lời giải tối ưu. 27 Các phương pháp tìm kiếm có kinh nghiệm
  28. 7.1. Ví dụ về heuristics chấp nhận được Ví dụ, bài toán 8-số:  h1(u) = Số lượng ô sai vị trí.  h2(u) = Tổng khoảng cách theo Mahattan Metric (i.e., Số lượng ô từ ô hiện tại đến vị trí mong muốn)  h1(S) = ?  h2(S) = ? 28 Các phương pháp tìm kiếm có kinh nghiệm
  29. 7.1. Ví dụ về heuristics chấp nhận được (tiếp) Ví dụ, bài toán 8-số:  h1(u) = Số lượng ô sai vị trí.  h2(u) = Tổng khoảng cách theo Mahattan Metric (i.e., Số lượng ô từ ô hiện tại đến vị trí mong muốn)  h1(S) = 8  h2(S) = 3+1+2+2+2+3+3+2 = 18 29 Các phương pháp tìm kiếm có kinh nghiệm
  30. 7.2. So Sánh các Heuristics  Nếu h2(u) ≥ h1(u) với mọi u (cả hai đều chấp nhận được) thì h2 được coi là mạnh hơn h1 h2 là heuristic tốt hơn  Ví dụ tìm kiếm trên bài toán 8-số (số lượng node trung bình phải xét):  d=12 IDS = 3,644,035 nodes * A (h1) = 227 nodes * A (h2) = 73 nodes  d=24 IDS = too many nodes * A (h1) = 39,135 nodes * A (h2) = 1,641 nodes 30 Các phương pháp tìm kiếm có kinh nghiệm
  31. 7.3. Nới lỏng ràng buộc của bài toán  Bài toán có thể nới lỏng bằng cách bớt các ràng buộc trên toán tử;  Chi phí cho lời giải tối ưu của bài toán nới lỏng là một Heuristic chập nhận được đối với bài toán gốc;  Ví dụ:  Nếu bài toán 8-số được nới lỏng sao cho có thể dịch chuyển mỗi ô đến nơi tuỳ ý, ta có h1(n) cho lời giải tối ưu.  Nếu bài toán được nới lỏng sao cho mỗi ô có thể dịch chuyển đến ô bất kỳ liền kề thì ta có h2(n) cho lời giải tối ưu. 31 Các phương pháp tìm kiếm có kinh nghiệm
  32. 8. A* search  Ý tưởng:  Sử dụng hàm Heuristics chấp nhận được + tìm kiếm theo chiều rộng → Loại bỏ những đường đi có chi phí cao.  Hàm lượng giá: f(u) = g(u) + h(u)  g(u) = Chi phí để đến u  h(u) = Lượng giá từ u đến đích  f(u) = Ước lượng tổng giá đến đích qua u. 32 Các phương pháp tìm kiếm có kinh nghiệm
  33. 8.1. Tìm đường đi với giá tính theo km 33 Các phương pháp tìm kiếm có kinh nghiệm
  34. 8.1. Ví dụ về A* search 34 Các phương pháp tìm kiếm có kinh nghiệm
  35. 8.1. Ví dụ về A* search 35 Các phương pháp tìm kiếm có kinh nghiệm
  36. 8.1. Ví dụ về A* search 36 Các phương pháp tìm kiếm có kinh nghiệm
  37. 8.1. Ví dụ về A* search 37 Các phương pháp tìm kiếm có kinh nghiệm
  38. 8.1. Ví dụ về A* search 38 Các phương pháp tìm kiếm có kinh nghiệm
  39. 8.1. Ví dụ về A* search 39 Các phương pháp tìm kiếm có kinh nghiệm
  40. 8.1. Ví dụ về A* search (ví dụ 2) Đầu vào: . Trạng thái đầu A, . Trạng thái đích B. . Các giá trị ghi trên cạnh là độ dài đường đi; . Các số cạnh các đỉnh là giá trị hàm h. Yêu cầu: Không gian trạng thái với hàm đánh giá  Tìm đường đi ngắn nhất từ A đến B bằng A*. 40 Các phương pháp tìm kiếm có kinh nghiệm
  41. 8.1. Ví dụ về A* search (ví dụ 2) Thực hiện:  Phát triển đỉnh A sinh ra các đỉnh con C, D, E, F.  g(C) = 9, h(C) = 15 → f(C) = 9 + 15 = 24  g(D) = 7, h(D) = 6 → f(D) = 7 + 6 = 13  g(E) = 13, h(E) = 8 → f(E) = 13 + 8 = 21  g(F) = 20, h(F) = 7 → f(F) = 20 + 7 = 27 → Như vậy, đỉnh D được chọn để phát triển (f(D) = 13) 41 Các phương pháp tìm kiếm có kinh nghiệm
  42. 8.1. Ví dụ về A* search (ví dụ 2)  Phát triển D, nhận được các đỉnh con H và E (mới). Trong đó:  g(H) = g(D) + độ dài cung (D,H) = 7 + 8 = 15  h(H) = 10  → f(H) = g(H) + h(H) = 15 + 10 = 25.  g(E) = g(D) + độ dài cung (D,E) = 7 +4 = 11  h(E) = 8 → f(E) = g(E) + h(E) = 11 + 8 = 19.  Như vậy đỉnh E sẽ được dùng để phát triển tiếp  Tương tự sẽ chọn được các đỉnh K, B (đích).  Với g(B) = 19, h(B) = 0.  Đường đi: A → D → E → I →B 42 Các phương pháp tìm kiếm có kinh nghiệm
  43. 8.2. Cài đặt thuật toán A* Procedure A*; Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái đầu. 2. Loop do 2.1. if L rỗng then {thông báo thất bại; stop;} 2.2. Loại trạng thái u ở đầu danh sách L; 2.3. if u là trạng thái đích then {thông báo thành công; stop} 2.4. for mỗi trạng thái v kề u do { g(v) ← g(u)+ k(u,v); f(v) ← g(v)+h(v); Đặt v vào danh sách L; } 2.5. Sắp xếp L theo thứ tự giảm dần của hàm f sao cho trạng thái có giá trị của hàm f nhỏ nhất ở đầu danh sách; 3. End; 43 Các phương pháp tìm kiếm có kinh nghiệm
  44. 8.3. Chứng minh tính tối ưu của A*  Giả sử thuật toán dừng ở G, với độ dài đường đi là g(G) và ta có h(G)=0 nên f(G)=g(G).  Giả sử nghiệm tối ưu không phải là G, tối ưu là G1, với độ dài đường đi là S.  Như vậy, đường đi này bị tách ra ở vị trí N nào đó. Khi đó có 2 khả năng:  N trùng G1, hoặc  N không trùng G1. 44 Các phương pháp tìm kiếm có kinh nghiệm
  45. 8.3. Chứng minh tính tối ưu của A* (tiếp)  Nếu N ≡ G1:  G được chọn trước G1, nên f(G) ≤ f(G1) vì g(G) ≤ g(G1) = S  Nếu N ≠ G1:  Do h(u) là đánh giá thấp → f(N) = g(N) + h(N) ≤ S.  Do G được chọn trước → f(G) ≤ f(N) ≤ S.  Vậy G là đường đi tối ưu. 45 Các phương pháp tìm kiếm có kinh nghiệm
  46. 8.4. Nhận xét về A*  Nếu hàm h(u) đánh giá thấp nhất thì thuật toán A* là tối ưu.  Nếu các cung không nhỏ hơn một số α nào đó thì A* là đầy đủ.  Nếu h(u)=0 với mọi u, thuật toán A* chính là thuật toán tìm kiếm tốt nhất đầu tiên với hàm đánh giá g(u). 8.5. Phân tích A* • Đủ? . Có (Trừ phi có vô hạn node với f ≤ f(G) ). • Độ phức tạp thời gian? . Hàm mũ • Không gian? . Lưu trữ tất cả các node • Tối ưu? Có 46 Các phương pháp tìm kiếm có kinh nghiệm
  47. 9.Tìm kiếm nhánh và cận (Branch and Bound) Ý tưởng:  Thuật toán nhánh và cận sử dụng tìm kiếm leo đồi với hàm đánh giá f(u).  Tại trạng thái u, chọn trạng thái v trong số các trạng thái kề với u, với f(v) đạt min.  Tương tự cho đến khi:  v là đích, hoặc  v không có đỉnh kề, hoặc  v có f(v) lớn hơn độ dài đường đi tối ưu hiện thời. → Không phát triển v nữa, quay về cha của v để tìm trạng thái tốt nhất trong các trạng thái còn lại chưa xét. 47 Các phương pháp tìm kiếm có kinh nghiệm
  48. 9.1. Ví dụ về nhánh và cận Xét không gian trạng thái bên.  Phát triển A, có các đỉnh con C, D, E, F với f(C) = 24; f(D) = 13; f(E) = 21; f(F) = 27.  Chọn D, sinh các con H, E (mới) với f(H) = 25; f(E) = 19. Không gian trạng thái với hàm đánh giá  Chọn E, sinh ra K, I với f(K) = 17; f(I) = 18.  Chọn K, sinh ra B với f(B) = g(B) = 21 → đường đi tạm thời là 21. 48 Các phương pháp tìm kiếm có kinh nghiệm
  49. 9.1. Ví dụ về nhánh và cận (tiếp)  Từ B, quay về K. Từ K quay về E.  Từ E, sang I, f(I) = 18 < độ dài tạm thời 21. Sinh ra K, B với f(K) = 25, f(B) = g(B) = 19 → đường đi tạm thời là 19. Không gian trạng thái với hàm đánh giá  Với B, không tìm được điểm nào có chi phí tốt hơn nữa.  Vậy đường đi tối ưu có độ dài 19. 49 Các phương pháp tìm kiếm có kinh nghiệm
  50. 9.2. Cài đặt thuật toán nhánh và cận Procedure Branch_and_Bound; Begin 1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu; Gán giá trị ban đầu cho cost; 2. Loop do 2.1. If L rỗng then stop; 2.2. Loại trạng thái u ở đầu danh sách L; 2.3. If u là trạng thái kết thúc then if g(u) ≤ cost then { cost ← g(u); quay lại 2.1;} 2.4. If f(u) > cost then quay về 2.1; 2.5. For mỗi trạng thái v kề u do { g(v) ← g(u)+k(u,v); f(v) ← g(v)+h(v); đặt v vào danh sách L1} 2.6. Sắp xếp L1 theo thứ tự tăng của hàm f; 2.7. Chuyển L1 vào đầu danh sách L sao cho L trạng thái đầu của L1 vào đầu L; 3. End; 50 Các phương pháp tìm kiếm có kinh nghiệm
  51. 9.3. Nhận xét thuật toán nhánh và cận  Thuật toán nhánh và cận cũng là thuật toán đầy đủ và tối ưu nếu hàm đánh giá h(u):  Đánh giá thấp và  Độ dài các cung không nhỏ hơn một số dương α nào đó. 51 Các phương pháp tìm kiếm có kinh nghiệm
  52. 10. Tìm đối tượng tốt nhất  Khác với quá trình tìm kiếm trước, tìm đối tượng tốt nhất x, x U, chưa xác định được đích của quá trình tìm kiếm. Một số kỹ thuật được sử dụng trong phần này gồm:  Kỹ thuật tìm kiếm leo đồi để tìm đối tượng tốt nhất.  Kỹ thuật tìm kiếm gradient (gradient search).  Kỹ thuật tìm kiếm mô phỏng luyện kim (simulated annealing) 52 Các phương pháp tìm kiếm có kinh nghiệm
  53. 10.1. Kỹ thuật tìm kiếm leo đồi tìm đối tượng tốt nhất  Kỹ thuật này không khác nhiều so với thuật toán tìm kiếm leo đồi trước.  Với thuật toán leo đồi, từ trạng thái u chuyển sang trạng thái tốt nhất v (theo hàm lượng giá). Nếu không đến đích và không “leo” đượ nữa, “quay về” trạng thái trước và leo lên trạng thái tốt nhất còn lại.  Với kỹ thuật tìm kiếm leo đồi tìm đối tượng tốt nhất, từ trạng thái u, chuyển sang trạng thái v tốt hơn. Nếu không tìm được thì dừng thuật toán. 53 Các phương pháp tìm kiếm có kinh nghiệm
  54. 10.1.1. Cài đặt thuật toán HC  Trong thủ tục, u là đỉnh hiện thời, v là trạng thái tốt nhất của lân cận u. Procedure Hill_Climbing; Begin 1. u ← một đối tượng ban đầu nào đó; 2. Loop do với v là con tốt nhất của u if cost(v) > cost(u) then u ← v else stop; End; 54 Các phương pháp tìm kiếm có kinh nghiệm
  55. 10.1.2. Nhận xét về Hill-Climbing  Yếu điểm: phụ thuộc vào trạng thái khởi đầu, có thể bị tắc tại cực trị địa phương. (Vấn đề ridge, valley).  Khắc phục: Có thể lặp lại quá trình leo đồi với nhiều điểm xuất phát khác nhau 55 Các phương pháp tìm kiếm có kinh nghiệm
  56. 10.1.3. Ví dụ: n-queens 56 Các phương pháp tìm kiếm có kinh nghiệm
  57. 10.1.3. Ví dụ bài toán 8-queens  h = số lượng con hậu tấn công lẫn nhau (trực tiếp và gián tiếp)  h = 17 trong hình trên 57 Các phương pháp tìm kiếm có kinh nghiệm
  58. 10.1.3. Ví dụ bài toán 8-queens • Một cực trị địa phương với h = 1. 58 Các phương pháp tìm kiếm có kinh nghiệm
  59. 10.1.3. Bài toán người du lịch • biểu diễn: dãy hoán vị. • h=tổng giá chi phi đường di trên dẫy hoán vị. • Toán tử: đổi chỗ hai đỉnh. 59 Các phương pháp tìm kiếm có kinh nghiệm
  60. 10.2. Tìm kiếm địa phương trong tối ưu không ràng buộc xk + 1 = xk + k pk hoặc là xk = xk + 1 – x k = kpk x k + 1 kpk xk pk - hướng tìm kiếm k - hệ số học 60 Các phương pháp tìm kiếm có kinh nghiệm
  61. 10.2.1. Tìm kiếm Gradient  Ý tưởng: Tìm kiếm gradient là kỹ thuật tìm kiếm leo đồi để tìm giá trị lớn nhất (hoặc nhỏ nhất) của hàm khả vi liên tục f(x) trong không gian các vector thực n-chiều.  Trong lân cận đủ nhỏ của điểm = ( 1, 2, , 푛), hàm f tăng nhanh nhất theo hướng gradient, với hướng được xác định: 휕 휕 휕 훻 = , , , 휕 1 휕 2 휕 푛 61 Các phương pháp tìm kiếm có kinh nghiệm
  62. 10.2.2. Thuật toán giảm gradient Chọn bước tiếp theo sao cho: F x k + 1 F xk với thay đổi nhỏ của x ta có thể xấp xỉ hàm F(x): T F xk + 1 = F xk + xk F xk + gk xk trong đó g k  F x x = xk Muốn hàm giảm thì: T T gk xk = kgkpk 0 Giảm nhiều nhất: pk = –gk xk +1 = xk – kgk 62 Các phương pháp tìm kiếm có kinh nghiệm
  63. 10.2.3. Cài đặt tìm kiếm Gradient Procedure Gradient_Search; Begin x ← điểm xuất phát nào đó; repeat ← + 훼. 훻 ; until 훻 < 휀 End; Với 훼 nhỏ, xác định bước chuyển, 휀 xác định tiêu chuẩn dừng. 63 Các phương pháp tìm kiếm có kinh nghiệm
  64. 10.2.4. Ví dụ về tìm kiếm gradient F = x2 + 2 x x + 2x 2 + x x 1 1 2 2 1 0.5 x 0 = = 0.1 0.5  F x x1 2x 1 + 2x2 + 1 3 F x = = g0 = F x = x = x0  2x + 4x 3 F x 1 2 x2 0.5 3 0.2 x 1 = x 0 – g 0 = – 0.1 = 0.5 3 0.2 0.2 1.8 0.02 x2 = x1 – g1 = – 0.1 = 0.2 1.2 0.08 64 Các phương pháp tìm kiếm có kinh nghiệm
  65. 10.2.5. Hình minh hoạ 2 1 0 -1 -2 -2 -1 0 1 2 65 Các phương pháp tìm kiếm có kinh nghiệm
  66. 10.3. Tìm kiếm mô phỏng luyện kim Ý tưởng:  Với phương pháp tìm kiếm leo đồi không đảm bảo cho việc tìm kiếm nghiệm tối ưu toàn cục. Để có được nghiệm tối ưu toàn cục, kỹ thuật leo đồi sử dụng việc xuất phát từ lựa chọn ngẫu nhiên, lặp nào đó.  Tư tưởng chính của mô phỏng luyện kim là cho phép chọn cả lựa chọn “xấu” với xác suất nào đó. 66 Các phương pháp tìm kiếm có kinh nghiệm
  67. 10.3.1. Mô tả tìm kiếm mô phỏng luyện kim  Giả sử đang ở trạng thái u nào đó. Chọn ngẫu nhiên trạng thái v trong lân cận u.  Nếu v tốt hơn u: sang v.  Nếu v không tốt hơn u: chỉ sang v với xác suất nào đó.  Xác suất này giảm theo hàm mũ của “độ tồi” của trạng thái v. Xác suất phụ thuộc vào tham số T (nhiệt độ), T càng lớn khả năng sang trạng thái tồi càng cao.  Xác suất được xác định: ∆ 푒 푣ớ푖 ∆ = 표푠푡(푣) – 표푠푡( ) 67 Các phương pháp tìm kiếm có kinh nghiệm
  68. 10.3.2. Cài đặt thuật toán SA Procedure Simulated_Anneaning; Chú ý: Begin t ← 0; g(T,t) thỏa mãn u ← trạng thái ban đầu nào đó; điều kiện T ← nhiệt độ ban đầu; repeat g(T,t) cost(u) then u ← v; Hàm này xác else u ← v với xác suất e∆/T; T ← g(T,t); định tốc độ giảm t ← t + 1; nhiệt độ. until T đủ nhỏ; End; 68 Các phương pháp tìm kiếm có kinh nghiệm
  69. 10.3.3. Nhận xét về SA  Đã chứng minh được bằng lý thuyết, nếu T giảm đủ chậm thì thuật toán sẽ tìm được nghiệm tối ưu toàn cục.  Thuật toán mô phỏng luyện kim (SA) đã áp dụng thành công cho các bài toán tối ưu cỡ lớn. 69 Các phương pháp tìm kiếm có kinh nghiệm