Hàm heuristic trong khoa học máy tính là gì năm 2024
1. Giới thiệu chung Show
2. Hàm đánh giá trong tìm kiếm kinh nghiệm
2.1. Hàm đánh giá
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á:
Ví dụ 2: Xét bài toán 8 số, ta có thể xây dựng hàm đánh giá như sau: Hàm H1: - với một trạng thái u, H1(u) là số quân ở sai vị trí. - trong ví dụ trên: H1(u) = 4 Hàm H2: - H2(u) là tổng khoảng cách giữa vị trí quân ở trạng thái u với vị trí ở trạng thái đích. - trong ví dụ trên: H2(u) = 9 3. Tìm kiếm tốt nhất đầu tiên (Best-first search)
Tìm kiếm tốt nhất đầu tiên = Tìm kiếm theo chiều rộng + Hàm đánh giá.
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:
Xét không gian trạng thái sau: 3.2. Cài đặt Best First SearchProcedure Best_First_Search; Begin
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á;
4. Tìm kiếm tham lam tốt nhất đầu tiên (Greedy best-first search)
4.1. Tìm đường đi với giá tính theo km4.2. Ví dụ về GBFS5. Tìm kiếm leo đồi (hill-climbring search)
Tìm kiếm leo đồi = tìm kiếm theo chiều sâu + hàm đánh giá
5.1. Ví dụ về Hill-climbing searchĐầu vào:
Thực hiện:
Xét không gian trạng thái sau: 5.2. Cài đặt Hill-Climbing SearchProcedure Hill_Climbing_Search; Begin
6. Tìm kiếm chùm (Beam search)
Tìm kiếm theo chiều rộng + k node để phát triển + hàm đánh giá
6.1. Ví dụ về Beam SearchĐầu vào:
Thực hiện:
Xét không gian trạng thái sau: 7. Heuristic chấp nhận đượcTrong 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.
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.
f(u) = g(u) + h(u) 7.1. Heuristics chấp nhận được trong A*
7.2. So Sánh các Heuristics
8. A* search
8.1. Tìm đường đi với giá tính theo km8.2. Ví dụ về A* search8.2. 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: Tìm đường đi ngắn nhất từ A đến B bằng A*. Không gian trạng thái với hàm đánh giá Thực hiện: v Phát triển đỉnh A sinh ra các đỉnh con C, D, E, F. v g(C) = 9, h(C) = 15 → f(C) = 9 + 15 = 24 v g(D) = 7, h(D) = 6 → f(D) = 7 + 6 = 13 v g(E) = 13, h(E) = 8 → f(E) = 13 + 8 = 21 v 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) 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 8.3. 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; |