Thuật giải AT, AKT

Chia sẻ: Pham Thien Luat | Ngày: | Loại File: PPT | Số trang:68

Thêm vào BST

Báo xấu

1.950
lượt xem 115
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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.
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
Thuật giải AT Ví dụ 100 1 17 1 D B C A 1 10 20 12 1 1 G H I J E F 1 1 1 1 K N L M 1 1 O P 1 1 Q R 1 1 S T 1 T r a ïn g t h a ù ñ í c h i U 1 V
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 B2: Đóng S; mở A, B, C, D 17 1 D B C A g(A) = g(S) + gt(S→A) = 0 + 100 = 100 1 10 20 12 1 1 G H I J E g(B) = 0 + 17 = 17 F 1 1 1 1 K N g(C) = g(D) = 0 + 1 = 1 (min) L M 1 1 O P Chọn ngẫu nhiên giữa C, D: chọn C 1 1 Q R B3: Đóng C, mở G, H: 1 1 S T g(A) = 100 1 T r a ïn g t h a ù ñ í c h i U g(B) = 17 1 V g(D) = 1 (min) g(G) = 11 g(H) = 21
Thuật giải AT Ví dụ B4: Đóng D, mở I, J: 100 1 g(A) = 100 17 1 D g(B) = 17 B C A 1 g(I) = 13 10 20 12 1 g(J) = 2 (min) 1 G H I J E F g(G) = 11 1 1 1 1 g(H) = 21 K N L M B5: Đóng J, mở N: 1 1 O P g(A) = 100 1 1 g(B) = 17 Q R g(I) = 13 1 g(G) = 11 1 S T g(H) = 21 1 g(N) = 3 (min) T r a ïn g th a ùi ñ í c h U 1 V
Thuật giải AT Ví dụ B6: Đóng N, mở P: 100 1 17 1 g(A) = 100 D B C A g(B) = 17 1 10 20 12 1 g(I) = 13 1 G H I J E F g(G) = 11 1 1 1 1 K N g(H) = 21 L M 1 1 g(P) = 4 (min) O P B7: Đóng P, mở R: 1 1 Q R g(A) = 100 1 g(B) = 17 1 S T g(I) = 13 1 T r a ïn g t h a ù ñ í c h i g(G) = 11 U 1 g(H) = 21 V g(R) = 5 (min) S 1→ D 1→ J 1→ N 1→ P 1→ R      R là đích. Vậy đường đi là: Nhận xét: Thuật toán này chỉ sử dụng 3 thông tin: đỉnh, cung và giá thành của cung.
Thuật giải AKT – Tìm kiếm với tri thức bổ sung (Algorithm for Knowledgeable Tree Search): Thuật giải AT 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 AT 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)
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.
Bài toán Tháp Hà Nội với n = 2 S0 Sn Các trường hợp của bài toán là với trạng thái cột thứ ba: h(n) = 0 1 2 3
g=0 h=2 f=2 g=1 g=1 h=2 h=3 f = 3 (m in ) f=4 g=2 g=2 g=2 h=2 h=3 h=1 f=4 f=5 f = 3 (m in ) g=3 g=3 g=3 h=2 h=1 h=0 f=5 f=4 f = 3 (Ñ ích)
Bài toán taci 2 8 3 1 2 3 1 6 4 8 4 7 7 6 5 5 S0 Sn Cách 1: 0 neáu = b i ai t H = ∑ δ(a i , b i ) vôùi(a i , b i ) =  δ 1 neáu ≠ b i ai i =1
2 8 3 g=0 1 6 4 h = 4 ( c o ù 4 s o á s a i v ò tr í s o v ô ù G o a l ) i f=4 7 5 2 8 3 2 8 3 2 8 3 g=1 g=1 g=1 1 6 4 1 4 1 6 4 h=5 h=3 h=5 f=6 f = 4 (m in ) f=6 7 5 7 6 5 7 5 8 3 3 8 3 2 2 2 g=2 g=2 g=2 1 4 1 8 4 1 4 h=3 h=3 h=4 f=5 f = 5 (m in ) f=6 7 6 5 7 6 5 7 6 5 3 3 2 2 g=3 g=3 1 8 4 1 8 4 h=2 h=4 f = 5 (m in ) f=7 7 6 5 7 6 5 1 2 3 1 2 3 g=4 g=5 8 4 8 4 h=1 h=0 f = 5 (m in ) f = 5 (Ñ ích ) 7 6 5 7 6 5
Bài toán taci t Cách 2: 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 Coäng 1 2 3 4 5 6 7 8 Soá 1 6 4 0 Vò trí 1 1 0 0 0 1 2 5 7 5
Bài toá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.
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.
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)
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.
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.
Bản đồ của Romania với khoảng cách tính theo km
Khoảng cách đường chim bay từ một thành phố đến Bucharest.