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

Chia sẻ: Mr Yukogaru | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

87
lượt xem 22
download

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

Ứng dụng A* để giải bài toán Ta- canh Các chiến lược tìm kiếm lai Tổ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

Chủ đề:

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

Lưu

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

III.10. ng d ng A* gi i bài toán Ta-canh Bà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 ây là 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 di chuy 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 u b 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ư t t 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ưa tì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 i theo 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úc nà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 u trú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=12 III.11. Các chi n lư c tìm ki m lai Chúng ta ã bi t qua 4 ki u tìm ki m : leo èo (L ), tìm theo chi u sâu (MC), tìm theo 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ư 4 thá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 i thí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 i gi 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 t Theo hư ng R, chúng ta th y leo èo n m m t thái c c (nó không cho phép quay l i nh ng tr ng thái chưa ư c xét n), trong khi ó tìm ki m quay lui và BFS m t thá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 S chú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 m vi 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 t thái c c khác (trong khi BF xem xét toàn b t p các con ư ng ã có, bao g m c nh ng con ư ng m i ư c t o ra cũng như t t c nh ng con ư ng không ư c xét t 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 t m 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 t trong 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ính toá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 t lo 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 theo chi 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 ng BFS vào tr ng thái ban u T0 m t cách bình thư ng. BFS s thi hành cho nm t lú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ư t quá 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 t phá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ía "dư 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 Tmax nà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 hai trong 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ư i" tr 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 t tr ng thái Tk mà sâu (s tr ng thái trung gian) c a nó vư t quá m t ngư ng d0 nào ó. T i i m này, thay vì l n ngư c tr l i, ta áp d ng ki u tìm ki m BFS cho ph n không gian phía "dư i" b t u t Tk cho t i khi nó tr v m t gi i pháp ho c không tìm th y. N u nó không tìm th y k t qu , chúng ta l n ngư c tr l i và l i dùng BFS khi t sâu d0. Tham s d0 s ư c ch n sao cho b nh dùng cho tìm ki m BFS trên không gian "dư i" m c d0 s không vư t quá m t h ng s cho trư c. Rõ ràng ta ta không d gì xác nh ư c d0 (vì nói chung, ta khó ánh giá ư c không gian bài toán r ng n m c nào). Tuy nhiên, ki u k t h p này l i có m t thu n l i. Ph n áy không gian tìm ki m thư ng ch a nhi u thông tin "b ích" hơn là ph n nh. (Ch ng h n, tìm ư ng i n khu trung tâm c a thành ph , khi càng n g n khu trung tâm – áy th – b n càng d dàng ti n n trung tâm hơn vì có nhi u "d u hi u" c a trung tâm xu t hi n xung quanh b n!). Nghĩa là, càng ti n v phía áy c a không gian tìm ki m, ư c lư ng h’ thư ng càng tr nên chính xác hơn và do ó, càng d d n ta n k t qu hơn. Hình : Chi n lư c lai BFS-MC trong ó, MC áp d ng t i nh và BFS t i áy. Còn m t ki u k t h p ph c t p hơn n a. Trong ó, BFS ư c th c hi n c c b và chi u sâu ư c th c hi n toàn c c. Ta b t u tìm ki m theo BFS cho t i khi m t s lư ng b nh xác nh M0 ư c dùng h t. T i i m này, chúng ta xem t t c nh ng 39 Sưu t m b i: www.daihoc.com.vn
tr ng thái trong OPEN như nh ng tr ng thái con tr c ti p c a tr ng thái ban u và chuy n giao chúng cho tìm ki m chi u sâu. Tìm ki m chi u sâu s ch n tr ng thái t t nh t trong nh ng tr ng thái con này và "bành trư ng" nó dùng BFS, nghĩa là nó chuy n tr ng thái ã ch n cho tìm ki m BFS c c b cho n khi m t lư ng b nh M0 l i ư c dùng h t và tr ng thái con m i trong OPEN l i ti p t c ư c xem như nút con c a nút "bành trư ng"...N u vi c "bành trư ng" b ng BFS th t b i thì ta quay lui l i và ch n nút con t t th hai c a t p OPEN trư c ó, r i l i ti p t c bành trư ng b ng BFS... Hình : Chi n lư c lai BFS-MC trong ó, BFS ư c áp d ng c c b và chi u sâu ư c áp d ng toàn c c. Có m t cách ph i h p n i ti ng khác ư c g i là tìm ki m theo giai o n ư c th c hi n như sau. Thay vì lưu tr trong b nh toàn b cây tìm ki m ư c sinh ra b i BFS, ta ch gi l i cây con có tri n v ng nh t. Khi m t lư ng b nh M0 ư c dùng h t, ta s ánh d u m t t p con các tr ng thái trong OPEN (nh ng tr ng thái có giá tr hàm f th p nh t) gi l i; nh ng ư ng i t t nh t qua nh ng tr ng thái này cũng s ư c ghi nh và t t c ph n còn l i c a cây b lo i b . Quá trình tìm ki m sau ó s ti p t c theo BFS cho t i khi m t lư ng b nh M0 l i ư c dùng h t và c th . Chi n lư c này có th ư c xem như là m t s lai ghép gi a BF và leo èo. Trong ó, leo èo thu n túy lo i b t t c nhưng ch gi l i phương án t t nh t còn tìm ki m theo giai o n lo i b t t c nhưng ch gi l i t p các phương án t t nh t. 40 Sưu t m b i: www.daihoc.com.vn
A. T NG QUAN TRÍ TU NHÂN T O I. M U Ch t o ư c nh ng c máy thông minh như con ngư i (th m chí thông minh hơn con ngư i) là m t ư c mơ cháy b ng c a loài ngư i t hàng ngàn năm nay. H n b n c còn nh n nhà khoa h c Alan Turing cùng nh ng óng góp to l n c a ông trong lĩnh v c trí tu nhân t o. Năng l c máy tính ngày càng m nh m là m t i u ki n h t s c thu n l i cho trí tu nhân t o. i u này cho phép nh ng chương trình máy tính áp d ng các thu t gi i trí tu nhân t o có kh năng ph n ng nhanh và hi u qu hơn trư c. S ki n máy tính Deep Blue ánh b i ki n tư ng c vua th gi i Casparov là m t minh ch ng hùng h n cho m t bư c ti n dài trong công cu c nghiên c u v trí tu nhân t o. Tuycó th ánh b i ư c Casparov nhưng Deep Blue là m t c máy ch bi t ánh c ! Nó th m chí không có ư c trí thông minh sơ ng c a m t a bé bi t lên ba như nh n di n ư c nh ng ngư i thân, kh năng quan sát nh n bi t th gi i, tình c m thương, ghét, ... Ngành trí tu nhân t o ã có nh ng bư c ti n áng k , nhưng m t trí tu nhân t o th c s v n ch có trong nh ng b phim khoa h c gi tư ng c a Hollywood. V y thì t i sao chúng ta v n nghiên c u v trí tu nhân t o? i u này cũng tương t như ư c mơ ch t o vàng c a các nhà gi kim thu t th i Trung C , tuy chưa thành công nhưng chính quá trình nghiên c u ã làm sáng t nhi u v n . M c dù m c tiêu t i thư ng c a ngành TTNT là xây d ng m t chi c máy có năng l c tư duy tương t như con ngư i nhưng kh năng hi n t i c a t t c các s n ph m TTNT v n còn r t khiêm t n so v i m c tiêu ã ra. Tuy v y, ngành khoa h c m i m này v n ang ti n b m i ngày và ang t ra ngày càng h u d ng trong m t s công vi c òi h i trí thông minh c a con ngư i. Hình nh sau s giúp b n hình dung ư c tình hình c a ngành trí tu nhân t o. Trư c khi bư c vào tìm hi u v trí tu nhân t o, chúng ta hãy nh c l i m t nh nghĩa ư c nhi u nhà khoa h c ch p nh n. M c tiêu c a ngành khoa h c trí tu nhân t o ? T o ra nh ng chi c máy tính có kh năng nh n th c, suy lu n và ph n ng. Nh n th c ư c hi u là kh năng quan sát, h c h i, hi u bi t cũng như nh ng kinh nghi m v th gi i xung quanh. Quá trình nh n th c giúp con ngư i có tri th c. Suy lu n là kh năng v n d ng nh ng tri th c s n có ph n ng v i nh ng tình hu ng 41 Sưu t m b i: www.daihoc.com.vn
hay nh ng v n - bài toán g p ph i trong cu c s ng. Nh n th c và suy lu n t ó ưa ra nh ng ph n ng thích h p là ba hành vi có th nói là c trưng cho trí tu c a con ngư i. (Dĩ nhiên còn m t y u t n a là tình c m. Nhưng chúng ta s không c p n ây!). Do ó, cũng không có gì ng c nhiên khi mu n t o ra m t chi c máy tính thông minh, ta c n ph i trang b cho nó nh ng kh năng này. C ba kh năng này uc n n m t y u t cơ b n là tri th c. Dư i góc nhìn c a t p sách này, xây d ng trí tu nhân t o là tìm cách bi u di n tri th c, tìm cách v n d ng tri th c gi i quy t v n và tìm cách b sung tri th c b ng cách "phát hi n" tri th c t các thông tin s n có (máy h c). 42 Sưu t m b i: www.daihoc.com.vn