Thuật toán và giải thuật - Hoàng Kiếm Part 6

Ứng dụng A* để giải bài toán Ta- canhCác chiến lược tìm kiếm laiTổng quan về trí tuệ nhân tạo chế tạo được những cổ máy thông minh như con người ( thậm trí thông minh hơn con người) là một mơ ước cháy bỏng của loài người hàng trăm năm nay
Nội dung trích xuất từ tài liệu:
Thuật toán và giải thuật - Hoàng Kiếm Part 6III.10. ng d ng A* gi i bài toán Ta-canhBài toán Ta-canh ã t ng là m t trò chơi khá ph bi n, ôi lúc ngư i ta còn g i âylà bài toán 9-puzzle. Trò chơi bao g m m t hình vuông kích th ơc 3x3 ô. Có 8 ô cós , m i ô có m t s t 1 n 8. M t ô còn tr ng. M i l n di chuy n ch ư c dichuy n m t ô n m c nh ô tr ng v phía ô tr ng. V n là t m t tr ng thái ban ub t kỳ, làm sao ưa ư c v tr ng thái cu i là tr ng thái mà các ô ư c s p l n lư tt 1 n 8 theo th t t trái sang ph i, t trên xu ng dư i, ô cu i dùng là ô tr ng.Cho n nay, ngo i tr 2 gi i pháp vét c n và tìm ki m Heuristic, ngư i ta v n chưatìm ư c m t thu t toán chính xác, t i ưu gi i bài toán này. Tuy nhiên, cách gi itheo thu t gi i A* l i khá ơn gi n và thư ng tìm ư c l i gi i (nhưng không ph i lúcnào cũng tìm ư c l i gi i). Nh n xét r ng: T i m i th i i m ta ch có t i a 4 ô cóth di chuy n. V n là t i th i i m ó, ta s ch n l a di chuy n ô nào? Ch ng h n hình trên, ta nên di chuy n (1), (2), (6), hay (7) ? Bài toán này hoàn toàn có c utrúc thích h p có th gi i b ng A* (t ng s tr ng thái có th có c a bàn c là n2!v i n là kích thư c bàn c vì m i tr ng thái là m t hoán v c a t p n2 con s ).T i m t tr ng thái ang xét Tk, t d(i,j)là s ô c n di chuy n ưa con s ô (i,j)v úng v trí c a nó tr ng thái ích.Hàm ư c lư ng h’ t i tr ng thái Tk b t kỳ b ng t ng c a các d(i,j) sao cho v trí (i,j)không ph i là ô tr ng.Như v y i v i tr ng thái hình ban u, hàm f(Tk) s có giá tr là Fk=2+1+3+1+0+1+2+2=12III.11. Các chi n lư c tìm ki m laiChúng ta ã bi t qua 4 ki u tìm ki m : leo èo (L ), tìm theo chi u sâu (MC), tìmtheo chi u r ng (BR) và tìm ki m BFS. B n ki u tìm ki m này có th ư c xem như 4thái c c c a không gian liên t c bao g m các chi n lư c tìm ki m khác nhau. gi ithích i u này rõ hơn, s ti n hơn cho chúng ta n u nhìn m t chi n lư c tìm ki m l igi i dư i hai chi u sau : 37 Sưu t m b i: www.daihoc.com.vn Chi u kh năng quay lui (R): là kh năng cho phép quay l i xem xét nh ng tr ng thái xét n trư c ó n u g p m t tr ng thái không th i ti p. Chi u ph m vi c a s ánh giá (S): s các tr ng thái xét n trong m i quy t nh. Hình : Tương quan gi a các chi n lư c leo èo, quay lui và t t nh tTheo hư ng R, chúng ta th y leo èo n m m t thái c c (nó không cho phép quayl i nh ng tr ng thái chưa ư c xét n), trong khi ó tìm ki m quay lui và BFS m tthái c c khác (cho phép quay l i t t c các hư ng i chưa xét n). Theo hư ng Schúng ta th y leo èo và l n ngư c n m m t thái c c (ch t p trung vào m t ph mvi h p trên t p các tr ng thái m i t o ra t tr ng thái hi n t i) và BFS n m m tthái c c khác (trong khi BF xem xét toàn b t p các con ư ng ã có, bao g m cnh ng con ư ng m i ư c t o ra cũng như t t c nh ng con ư ng không ư c xétt i trư c ây trư c m i m t quy t nh).Nh ng thái c c này ư c tr c quan hóa b ng hình trên. Vùng in m bi u di n m tm t ph ng liên t c các chi n lư c tìm ki m mà nó k t h p m t s c i mc am ttrong ba thái c c (leo èo, chi u sâu, BFS) có ư c m t hòa h p các c tính tínhtoán c a chúng.N u chúng ta không b nh c n thi t áp d ng thu t toán BFS thu n túy. Ta cóth k t h p BFS v i tìm theo chi u sâu gi m b t yêu c u b nh . Dĩ nhiên, cái giámà ta ph i tr là s lư ng các tr ng thái có th xét n t i m t bư c s nh i. M tlo i k t h p như th ư c ch ra trong hình dư i. Trong hình này, thu t gi i BFS ư cáp d ng t i nh c a th tìm ki m (bi u di n b ng vùng tô t m) và tìm ki m theochi u sâu ư c áp d ng t i áy (bi u di n b i tam giác tô nh t). u tiên ta áp d ngBFS vào tr ng thái ban u T0 m t cách bình thư ng. BFS s thi hành cho nm tlúc nào ó, s lư ng tr ng thái ư c lưu tr chi m d ng m t không gian b nh vư tquá m t m c cho phép nào ó. n lúc này, ta s áp d ng tìm ki m chi u sâu xu tphát t tr ng thái t t nh t Tmax trong OPEN cho t i khi toàn b không gian con phíadư i tr ng thái ó ư c duy t h t. N u không tìm th y k t qu , tr ng thái Tmaxnày ư c ghi nh n là không d n n k t qu và ta l i ch n ra tr ng thái t t th haitrong OPEN và l i áp d ng tìm ki m chi u sâu cho cho ph n không gian phía dư itr ng thái này.... 38 Sưu t m b i: www.daihoc.com.vn Hình : Chi n lư c lai BFS-MC trong ó, BFS áp d ng t i nh và MC t i áy.M t cách k t h p khác là dùng tìm ki m chi u sâu t i nh không gian tìm ki m vàBFS ư c dùng t i áy. Chúng ta áp d ng tìm ki m chi u sâu cho t i khi g p m ttr ng thái Tk mà sâu (s tr ng thái trung gian) c a nó vư t quá m t ngư ng d0nào ó. T i i m này, thay vì l n ngư c tr l i, ta áp d ng ki u tìm ...