Bên trong một hệ cơ sở tri thức

1BÊN TRONG MỘT HỆ CƠ SỞ TRI THỨC 2 Hệ Cơsơ tri thức= Cơ sơ ûtri thức + Động cơ suy diễn 3 Cấu trúc chung của một hệCSTT 4 Cơ sở tri thức 5Tổng quan quá trình xây dựng hệ CSTT 6 Một số bước cơ bản để xây dựng hệ Cơ sở tri thức • Tiếp cận chuyên gia • Thu thập, tổ chức tri thức • Chọn lựa công cụ phát triển hệ CSTT • Cài đặt hệ CSTT 7 Một số tiêu chuẩn phân loại các hệ CSTT • Tính đóng, mở, kết hợp • Phương pháp biểu diễn tri thức • Lĩnh vực ứng dụng 8 Hệ CSTTđóng • được xây dựng với một số “tri thức lĩnh vực” ban đầu,và chỉ những tri thức đo ùma øthôi trong suốt quátrình hoạt động hay suốt thời gian sống của nó. 9Hệ CSTT mở hệ cơ sở tri thức tiên tiến hơn, có khả năng bổ sung tri thức trong quá trình hoạt động, khám phá 10 Hệ CSTT kết hợp • Bao gồm sự kết hợp giữa hệ đóng và hệ mở,hệ kết hợp giữa CSTT va øCSDL,hệ kết hợp giữa he äCSTT này với một hệ CSTT khác, … • Những hệ CSTT kết hợp thường phát triển mạnh dựa trên tri thức liên ngành. • Ví dụ: những hệ hỗ trợ ra quyết định trong đời sống,kinh tế và khoa học, những hệ chẩn đoán, dự báo 11 Một số hệ CSTT điển hình • Hệ giải toán • Hệ chẩn đoán y khoa MYCIN • Hệ điều khiển tự động • Hệ dự báo thời tiết 12 Ví dụ: Máy điều nhiệt MÙA TRONG NĂM NGÀY TRONG TUẦN GIỜ TRONG NGÀY MÁY ĐIỀU NHIỆT NHIỆT ĐỘ THÍCH HỢP 13 CÁC ĐỐI TƯỢNG Đối tượng Giá trị Tháng Tháng 1, …, Tháng 12 Mùa Xuân, hè, thu, đơng Ngày Thứ 2, …, Thứ 7, Chủ nhật Thời gian Trước 9, Sau 17, Từ 9 -> 17 Sự khởi động Trong giờ làm việc, ngồi giờ làm việc 14 GIẢI PHÁP ĐIỀU NHIỆT 7 giải pháp điều nhiệt -Đặt máy điều nhiệt là “14o C” - Đặt máy điều nhiệt là “15o C” - Đặt máy điều nhiệt là “16o C” - Đặt máy điều nhiệt là “18o C” - Đặt máy điều nhiệt là “20o C” - Đặt máy điều nhiệt là “24o C” - Đặt máy điều nhiệt là “27o C” 15 Luật dẫn 1: Nếu Ngày là Thứ 2 Hoặc Ngày là Thứ 3 Hoặc Ngày là Thứ 4 Hoặc Ngày là Thứ 5 Hoặc Ngày là Thứ 6 Thì Hơm nay là Ngày làm việc CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 16 Luật dẫn 2: Nếu Ngày là Thứ 7 Hoặc Ngày là Chủ nhật Thì Hơm nay là Cuối tuần CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 17 Luật dẫn 3: Nếu Hơm nay là Ngày làm việc Và Thời gian giữa 9 giờ sáng và 5 giờ chiều Thì Sự khởi động là ‘trong thời gian làm việc’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 18 Luật dẫn 4: Nếu Hơm nay là Ngày làm việc Và Thời gian trước 9 giờ sáng Thì Sự khởi động là ‘ngồi thời gian làm việc’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 19 Luật dẫn 5: Nếu Hơm nay là Ngày làm việc Và Thời gian là sau 5 giờ chiều Thì Sự khởi động là ‘ngồi thời gian làm việc’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 20 Luật dẫn 6: Nếu Hơm nay là Cuối tuần Thì Sự khởi động là ‘ngồi thời gian làm việc’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 21 Luật dẫn 7: Nếu Tháng là Tháng 1 Hoặc Tháng là Tháng 2 Hoặc Tháng là Tháng 12 Thì Mùa là Mùa Hè CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 22 Luật dẫn 8: Nếu Tháng là Tháng 3 Hoặc Tháng là Tháng 4 Hoặc Tháng là Tháng 5 Thì Mùa là Mùa Thu CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 23 Luật dẫn 9: Nếu Tháng là Tháng 6 Hoặc Tháng là Tháng 7 Hoặc Tháng là Tháng 8 Thì Mùa là Mùa Đơng CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 24 Luật dẫn 10: Nếu Tháng là Tháng 9 Hoặc Tháng là Tháng 10 Hoặc Tháng là Tháng 11 Thì Mùa là Mùa Xuân CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 25 Luật dẫn 11: Nếu Mùa là Mùa Xuân Và Sự khởi động là ‘trong thời gian làm việc’ Thì Cấu hình điều nhiệt là ’20 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 26 Luật dẫn 12: Nếu Mùa là Mùa Xuân Và Sự khởi động là ‘ngồi thời gian làm việc’ Thì Cấu hình điều nhiệt là ’15 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 27 Luật dẫn 13: Nếu Mùa là Mùa Hè Và Sự khởi động là ‘trong thời gian làm việc’ Thì Cấu hình điều nhiệt là ’24 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 28 Luật dẫn 14: Nếu Mùa là Mùa Hè Và Sự khởi động là ‘ngồi thời gian làm việc’ Thì Cấu hình điều nhiệt là ’27 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 29 Luật dẫn 15: Nếu Mùa là Mùa Thu Và Sự khởi động là ‘trong thời gian làm việc’ Thì Cấu hình điều nhiệt là ’20 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 30 Luật dẫn 16: Nếu Mùa là Mùa Thu Và Sự khởi động là ‘ngồi thời gian làm việc’ Thì Cấu hình điều nhiệt là’16 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 31 Luật dẫn 17: Nếu Mùa là Mùa Đơng Và Sự khởi động là ‘trong thời gian làm việc’ Thì Cấu hình điều nhiệt là ’18 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 32 Luật dẫn 18: Nếu Mùa là Mùa Đơng Và Sự khởi động là ‘ngồi thời gian làm việc’ Thì Cấu hình điều nhiệt là ’14 độ’ CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) 33 MINH HỌA Tháng ? 8 Thứ ? Thứ 6 Giờ ? 9 < Giờ < 17 Luật 9 Mùa = Mùa Đơng Luật 1 Hơm nay= ngày làm việc Luật 3 Sự hoạt động = trong giờ làm việc Máy điều nhiệt = 18o C 34 HỆ GIẢI TOÁN DỰA TRÊN TRI THỨC 35 Hệ giải toán=Tiên đề,định lý+Lập luậnlogic (toán học) 36 Yêu cầu • Cho phép kiểm tra quá trình suy luận bao gồm việc thể hiện cụ thể các bước giải bài toán và trả lời hay giải thích cho quá trình giải. • Cho phép việc hiệu chỉnh và cập nhật cơ sở tri thức như thêm và loại bớt kiến thức trong cơ sở tri thức. • Sử dụng các heuristic (thường không đầy đủ) trong việc suy luận giải bài toán nhằm đạt được các lời giải tốt. 37 Cấu trúc của một hệ giải bài toán dựa trên tri thức 38 Bảo đảm sự tách biệt giữa cơ sở tri thức và bộ suy diễn • Sẽ làm cho việc biểu diễn tri thức được thực hiện một cách tự nhiên hơn. • Các nhà thiết kế hệ thống giải bài toán thông minh sẽ tập trung vào vệc nắm bắt và tổ chức cơ sở tri thức • Sẽ tăng cường tính mô-đun hóa của phần cơ sở tri thức, bộ suy diễn và bộ phận cập nhật, hiệu chỉnh kiến thức • Cho phép cùng một chiến lược điều khiển và giao tiếp có thể được sử dụng cho nhiều hệ thống khác nhau • Giúp ta có thể thử nghiệm nhiều chiến lượt điều khiển khác nhau trên cùng một cơ sở tri thức 39 Cơ sở tri thức • rất đa dạng • bao gồm: – các khái niệm từ đơn giản đến có cấu trúc phức tạp – các hệ thức tính toán với những qui luật nhất định – các liên hệ đa dạng bao gồm cả định tính lẫn định lượng – các luật dẫn và các heuristics 40 Vấn đề Suy diễn Tự động • Phương pháp hợp giải, luật “Modus Ponens”, luật “Modus Tollens” và luật “tam đoạn luận” . • Phương pháp suy diễn tiến • Phương pháp suy diễn lùi • Kết hợp suy diễn tiến và suy diễn lùi 41 Một số kết quả nghiên cứu xây dựng hệ giải toán hình học • Chỉ xét một số luật suy diễn cụ thể trên các quan hệ hình học và ứng với mỗi luật phải viết riêng một thủ tục thi hành luật • Chưa có một cơ sở tri thức có thể hiệu chỉnh được và bộ suy diễn sẽ hoạt động dựa trên cơ sở tri thức • Chưa xem xét đến vấn đề tính toán • Chưa có một ngôn ngữ qui ước cho việc đặc tả các dạng bài toán 42 Một số phần mềm giải toán • bộ phần mềm Engineering 2000 • Chương trình StudyWorks • Chương trình Math Express • Phần mềm toán học MAPLE 43 MẠNG SUY DIỄN-TÍNH TOÁN 44 Vấn đề • Chúng ta phải thực hiện những tính toán hay suy diễn ra những yếu tố cần thiết nào đó từ một số yếu tố đã được biết trước 45 Ví dụ 1 • Một vật thể có khối lượng m chuyển động thẳng với gia tốc không thay đổi là a trong một khoảng thời gian tính từ thời điểm t1 đến thời điểm t2 • Vận tốùc ban đầu của vật thể là v1, vận tốc ở thời điểm cuối là v2, và vận tốc trung bình là v • Khoảng cách giữa điểm đầu và điểm cuối là Δs • Lực tác động của chuyển động là f • Độ biến thiên vận tốc giữa 2 thời điểm là Δv • Độ biến thiên thời gian là Δt 46 Ví dụ 1 • f = m * a; • Δv = a*Δt; • Δs = v*Δt; • 2*v = v1 + v2; • Δv = v2 - v1; • Δt = t2 - t1; 47 Ví dụ 2 • Trong hóa học chúng ta thường phải sử dụng các phản ứng hóa học để điều chế các chất nầy từ các chất khác Ỵ Cho trước một số chất hóa học, hãy tìm cách điều chế ra một hay một số chất nào đó 48 Mục tiêu • Xác định tính giải được của một bài toán trên mạng tính toán • Trong trường hợp bài toán là giải được thì hãy cho một lời giải • Nếu bài toán không giải được thì cần có thêm yếu tố gì để có thể giải được 49 Mạng suy diễn và tính toán Mô hình mạng suy diễn và tính toán là một sự khái quát cho một dạng tri thức dùng cho việc biểu diễn tri thức và thiết kế các chương trình giải toán tự động, 50 Định nghĩa • Mỗi mạng tính toán là một mạng ngữ nghĩa chứa các biến và những quan hệ có thể cài đặt và sử dụng được cho việc tính toá 51 Quan hệ • Cho M = {x1,x2,...,xm} là một tập hợp các biến có thể lấy giá trị trong các miền xác định tương ứng D1,D2,...,Dm • Đối với mỗi quan hệ R ⊆ D1xD2x...xDm trên các tập hợp D1,D2,...,Dm ta nói rằng quan hệ nầy liên kết các biến x1,x2,...,xm ỈR(x1,x2,...,xm) hay R(x) fR,u,v : Du→ Dv 52 f : u → v ta có thể tính được giá trị của các biến thuộc khi biết được giá trị của các biến thuộc u u ∩ v = ∅ 53 Quan hệ đối xứng có hạng k (k>0) • tính được k biến bất kỳ từ m-k biến kia 54 Quan hệ không đối xứng có hạng k (k>0) 55 Ví dụ Quan hệ f giữa 3 góc A, B, C trong tam giác ABC cho bởi hệ thức: A+B+C = 180 (đơn vị: độ) quan hệ đối xứng có hạng 1 56 • quan hệ f giữ a nửa chu vi p với các độ dài của 3 cạnh a, b, c: 57 Mạng tính toán • bao gồm một tập hợp các biến M và một tập hợp các quan hệ (tính toán) F trên các biến • Ký hiệu MTT: – M = {x1,x2,...,xn} – F = {f1,f2,...,fm} – ta ký hiệu M(f) là tập các biến có liên hệ trong quan hệ f 58 Ví dụ • Trong ví dụ 1 ở trên, ta có M(f) = {A,B,C}. • Trong ví dụ 2 ở trên, ta có M(f) = {a,b,c,p}. 59 Ví dụ • Mạng tính toán cho một hình chữ nhật – b1, b2 : hai cạnh của hình chữ nhật; – d : đường chéo của hình chữ nhật; – s : diện tích của hình chữ nhật; – p : chu vi của hình chữ nhật; • có các quan hệ sau đây : – f1 : s = b1 * b2; – f2 : p = 2 * b1 + 2 * b2; – f3 : d2 = b12 + b22; 60 Vi dụ (tt) M = {b1, b2, d, s, p}, F = {f1, f2, f3}. 61 Vấn đề trên mạng tính toán • Cho một mạng tính toán (M,F) – M là tập các biến – F là tập các quan hệ • Giả sử có một tập biến A ⊆M đã được xác định • B là một tập biến bất kỳ trong M 62 Vấn đề trên mạng tính toán • Có thể xác định được tập B từ tập A nhờ các quan hệ trong F hay không? • Nếu có thể xác định được B từ A thì quá trình tính toán giá trị của các biến thuộc B như thế nào? • Trong trường hợp không thể xác định được B, thì cần cho thêm điều kiện gì để có thể xác định được B. 63 Vấn đề trên mạng tính toán • Bài toán xác định B từ A trên mạng tính toán (M,F) được viết dưới dạng : AỈB Hoặc AỈb 64 Định nghĩa • Bài toán A → B được gọi là giải được khi có thể tính toán được giá trị các biến thuộc B xuất phát từ giả thiết A • Ta nói rằng một dãy các quan hệ {f1, f2, ..., fk} ⊆ F là một lời giải của bài toán A → B nếu như ta lần lượt áp dụng các quan hệ fi (i=1,...,k) xuất phát từ giả thiết A thì sẽ tính được các biến thuộc B. 65 Định nghĩa • Lời giải tốt nếu không thể bỏ bớt một số bước tính toán trong quá trình giải • Lời giải tối ưu khi nó có số bước tính toán ít nhất 66 Định nghĩa • Cho D = {f1, f2, ..., fk} là một dãy quan hệ của mạng tính toán (M,F) • A là một tập con của M • D là áp dụng được trên tập A khi và chỉ khi ta có thể lần lượt áp dụng được các quan hệ f1, f2, ..., fk xuất phát từ giả thiết A 67 Định nghĩa • A0 = A, A1 = A0 ∪M(f1), . . . , • Ak = Ak-1 ∪M(fk) • ký hiệu Ak là D(A) ỴA → D(A) : có D là lời giải D(A) là sự mở rộng của tập A nhờ áp dụng dãy quan hệ D 68 Thuật toán tính D(A) Nhập : Mạng tính toán (M,F), A ⊆M, dãy các quan hệ D = {f1, f2, ..., fm}. Xuất : D(A). Thuật toán : 1. A’ ← A; 2. for i=1 to m do if fi áp dụng được trên A’ then A’ ← A’ ∪ M(fi); 3. D(A) ← A’ 69 Định nghĩa • Bao đóng của A là sự mở rộng tối đa của A trên mô hình (M,F). Ký hiệu: • Bài toán A → B là giải được khi và chỉ khi các bài toán A → b là giải được với mọi b ∈ B • Nếu A → B và B → C là các bài toán giải được thì bài toán A → C cũng giải được • Nếu bài toán A → B là giải được và B’ là một tập con của B thì A → B’ cũng là một bài toán giải được A 70 Định nghĩa • bài toán A → B là giải được khi và chỉ khi B ⊆ A 71 Tìm bao đóng của tập A ⊆ M • Nhập : Mạng tính toán (M,F), A ⊆M. • Xuất : 1. B ← A; 2. Repeat B1 ← B; for f ∈ F do if ( f áp dụng được trên B ) then begin B ← B ∪M(f); F ← F \ {f}; end; Until B = B1; 3. ← B;A A 72 Tìm một lời giải cho bài toán A → B Nhập : Mạng tính toán (M,F), tập giả thiết A ⊆M, tập biến cần tính B ⊆M. Xuất : lời giải cho bài toán A → B 73 1.Solution ← empty; // Solution là dãy các quan hệ sẽ áp dụng 2. if B ⊆ A then begin Solution_found ← true; goto 4; end else Solution_found ← false; 74 3. Repeat Aold ← A; Chọn ra một f ∈ F chưa xem xét; while not Solution_found and (chọn được f) do begin if ( f sử dụng được trên A ) then begin A ← A ∪M(f); Solution ← Solution ∪ {f}; end; if B ⊆ A then Solution_found ← true; Chọn ra một f ∈ F chưa xem xét; end; { while } Until Solution_found or (A = Aold); 75 4. if not Solution_found then Bài toán không có lời giải; else Solution là một lời giải 76 Tìm một lời giải tốt từ một lời giải đã biết Nhập : Mạng suy diễn (M,F), lời giải D={f1, f2, ..., fm} của bài toán A→ B. Xuất : lời giải tốt cho bài toán A → B Thuật toán : 1. D ← {f1, f2, ..., fm}; 2. for i=m downto 1 do if D \ {fi} là một lời giải then D ← D \ {fi}; 3. D là một lời giải tốt. 77 Thuật toán kiểm tra lời giải cho bài toán Nhập : Mạng suy diễn (M,F), bài toán A→ B, dãy các quan hệ {f1, f2, ..., fm}. Xuất : thông tin cho biết {f1, f2, ..., fm} có phải là lời giải của bài toán A→ B hay không. 78 1.for i=1 to m do if (fi áp dụng được trên A) then A ← A ∪ M(fi); 2. if A ⊇ B then {f1, f2, ..., fm} là lời giải else {f1, f2, ..., fm} không là lời giải; 79 Ví dụ • Cho tam giác ABC có cạnh a và 2 góc kề là β, γ được cho trước. • Hãy xác định (hay suy ra) S của tam giác 80 Ví dụ Mạng suy diễn của tam giác – M = {a, b, c, α, β, γ, ha, hb, hc, S, p, R, r, ...} – Các quan hệ suy diễn : 81 Ví dụ • A = {a, β, γ} • B = {S} 82 bước 1: Xác định α (áp dụng f1). bước 2: Xác định b (áp dụng f2). bước 3: Xác định S (áp dụng f9). 83 84 MẠNG SUY DIỄN CÓ TRỌNG SỐ VÀ LỜI GIẢI TỐI ƯU (1) a + b + c = 2*p, và (2) a2 = b2 + c2 - 2*b*c*cos(A) 85 MẠNG SUY DIỄN CÓ TRỌNG SỐ VÀ LỜI GIẢI TỐI ƯU mạng suy diễn có trọng số là một mô hình (A, D, w) bao gồm: – một tập hợp các thuộc tính A, – một tập hợp các luật suy diễn D, và – một hàm trọng số dương w : D → R+ • Mỗi luật dẫn r thuộc D có dạng r : u ⇒ v u và v là các tập hợp con khác rỗng và rời nhau của A 86 MẠNG SUY DIỄN CÓ TRỌNG SỐ VÀ LỜI GIẢI TỐI ƯU • r : u ⇒ v • u: phần giả thiết của luật r - hypothesis(r). • v : phần kết luận của luật r - goal(r). • attr(r) = hypothesis(r) ∪ goal(r) : tập hợp các thuộc tính trong luật r 87 Ví dụ • A = {A, B, C, a, b, c, p, S, ha, hb, hc, ...}. • D = { f1: A + B + C = 180; f2: a/sin(A) = b/sin(B); f3: b/sin(B) = c/sin(C); f4: a/sin(A) = c/sin(C); f5: 2*p = a + b + c; f6: S = a*ha/2; f7: S = b * hb / 2; f8: S = c*hc/2; f9: S = sqrt(p*(p-a)*(p-b)*(p-c)); f10: ha = b*sin(C); f11: hb = a*sin(C); f12: hc = b*sin(A) } +, -, * và / được đặt cho trọng số là 1 căn bậc 2 có trọng số là một hằng số dương c1 (c1>>1), hàm lượng giác có trọng số là một hằng số dương c2(c2>>1) 88 Ví dụ w(f1) = 2; w(f2) = w(f3) = w(f4) = 2*c2 + 2; w(f5) = 3; w(f6) = w(f7) = w(f8) = 2; w(f9) = c1 + 6; w(f10) = w(f11) = w(f12) = c2 + 1; (A,D,w) là một mạng suy diễn có trọng số 89 • (A, D, w) là một MSDT • S = {f1,...,fk} là một dãy các luật suy diễn • w(S) = w(f1) + w(f2) + ... + w(fk). • Ta gọi w(S) là trọng số của S. 90 Lời giải tối ưu • Cho một bài toán A → B. Dãy các luật suy diễn S được gọi là một lời giải tối ưu khi: – S là một lời giải của bài toán A → B. – w(S) = min {w(S’) | S’ là một lời giải của bài toán A → B } 91 • Xét bài toán H→ G trên một MSDT (A, D, w), với H và G là các tập con của tập thuộc tính A. • Thuật toán – Bước 1: Tìm một lời giải – Bước 2: Rút gọn lời giải 92 Bước 1: Tìm một lời giải • Khi G ⊄ H ta thực hiện quá trình lặp cho các bước dưới đây: – Bước 1.1: Tìm luật r ∈ D có thể áp dụng được để suy ra các thuộc tính mới: hypothesis(r) bao hàm trong H nhưng goal(r) không bào hàm trong H. – Bước 1.2: Nếu việc tìm kiếm ở bước 1.1 thất bại: bài toán không có lời giải. – Bước 1.3: Ngược lại thì bổ sung thêm goal(r) vào H và ghi nhận r vào danh sách các luật đã được áp dụng. 93 Bước 2: Rút gọn lời giải Bước 2.1: G'← G \ H; Bước 2.2: for k:=p downto 1 do if (goal(rk) ∉ G') then Loại rk ra khỏi danh sách S else G'← (G' \ goal(rk)) ∪ (hypothesis(rk) \ H) 94 Tìm lời giải tối ưu 95 Không gian trạng thái của bài toán • bài toán H→ G trên một MSDT (A, D, w) • r là một cạnh nối từ đỉnh H đến đỉnh H’ : – r có thể áp dụng trên H – H’ = H ∪ goal(r) • trọng số của cạnh r (tức là một luật suy diễn) là w(r) ỴGraph(H→G) 96 • Một dãy S gồm các luật là một lời giải của bài toán H→ G khi và chỉ khi S là một lộ trình trên đồ thị Graph(H→G) nối từ H đến S(H) và S(H) ⊃ G • Độ dài của một lộ trình S trên đồ thị Graph(H→G) là w(S), trọng số của danh sách luật S trên MSDT (A, D, w) • Đối với mỗi đỉnh N trên đồ thị: h(N) = min {w(r) | hypothesis(r) ⊂ N} 97 • Bước 1: Khởi tạo trạng thái xuất phát. – Open ← {H}; // danh sách đỉnh mở ban đầu chỉ có đỉnh xuất phát – Close ← {}; // danh sách đỉnh đóng – g(H) ← 0; // độ dài lộ trình đến H là 0 – f(H) ← h(H); // độ dài lộ trình ước tính từ H đến mục tiêu là h(H) – found ← false; // biến kiểm tra quá trình tìm lời giả 98 Bước 2: Thực hiện quá trình lặp để tìm lời giải tối ưu • While (Open ≠ {}) do • Begin – Bước 2.1: Chọn một đỉnh N trong Open với ước tính đường đi f nhỏ nhất. – Bước 2.2: Chuyển N từ danh sách Open sang danh sách Close – Bước 2.3: if (N là một mục tiêu) then Found ← true; Break; // Kết thúc quá trình lặp – Bước 2.4 else // N không là một mục tiêu 99 Begin Duyệt qua các đỉnh kế S của N mà S ∉ Close, ứng với mỗi S ta xét các trư