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

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

Thêm vào BST

Báo xấu

82
lượt xem 19
download

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

Biểu diễn tri thức bằng Frame Frame là một cấu trúc dữ liệu chứa đựng tất cả các tri thức liên quan đến một đối tượng nào đó. Frame liên hệ chặc chẽ đến khái niệm hướng đối tượng ( thực ra frame có nuồn gốc lập trình hướng đối tượng)

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 11

c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Kh i u: nh , a c a th ư c kích ho t. (1) (2) (3) (4) (5)  1 0 0 1 0  1 1 0 1 0  0 -1 0 -1 0 a 1 0 1 1 0 b -1 -1 -1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên c t (1), hi u (1+1+1 – (-1)) = 4 nên dòng b s ư c kích ho t. (1) (2) (3) (4) (5)  1 0 0 1 0  1 1 0 1 0  0 -1 0 -1 0 a 1 0 1 1 0 b 1 1 1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên c t (4), hi u (1+1+1 – (-1)) = 4 nên dòng  s ư c kích ho t. (1) (2) (3) (4) (5) 71 Sưu t m b i: www.daihoc.com.vn
 1 0 0 1 0  1 1 0 1 0  0 1 0 1 0 a 1 0 1 1 0 b 1 1 1 0 0 c 0 -1 -1 0 -1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên c t (2), hi u (1+1+1 – (1)) = 4 nên dòng c ư c kích ho t. (1) (2) (3) (4) (5)  1 0 0 1 0  1 1 0 1 0  0 1 0 1 0 A 1 0 1 1 0 B 1 1 1 0 0 C 0 1 1 0 1 S 0 0 -1 0 -1 hC 0 0 0 0 -1 Trên c t (3), hi u (1+1+1 – (-1)) = 4 nên dòng S ư c kích ho t. (1) (2) (3) (4) (5)  1 0 0 1 0  1 1 0 1 0  0 1 0 1 0 a 1 0 1 1 0 b 1 1 1 0 0 c 0 1 1 0 1 72 Sưu t m b i: www.daihoc.com.vn
S 0 0 1 0 1 hC 0 0 0 0 -1 Trên c t (5), hi u (1+1 – (1)) = 3 nên dòng hC ư c kích ho t. Kh năng c a h th ng này không ch d ng l i vi c tính ra giá tr các y u t c n thi t, v i m t chút s a i, chương trình này còn có th ưa ra cách gi i hình th c c a bài toán và th m chí còn có th ch n ư c cách gi i hình th c t i ưu (t i ưu hi u theo nghĩa là cách gi i s d ng nh ng công th c ơn gi n nh t). S dĩ có th nói như v y vì cách suy lu n c a ta trong bài toán này là tìm ki m theo chi u r ng. Do ó, khi t n k t qu , ta có th có r t nhi u cách khác nhau. có th ch n ư c gi i pháp t i ưu, b n c n ph i nh nghĩa ư c "ph c t p" c a m t công th c. M t trong nh ng tiêu chu n thư ng ư c dùng là s lư ng phép nhân, chia, c ng, tr , rút căn, tính sin, cos, ... ư c áp d ng trong công th c. Các phép tính sin, cos và rút căn có ph c t p cao nh t, k n là nhân chia và cu i cùng là c ng tr . Cu i cùng b n có th c i ti n l i phương pháp suy lu n b ng cách v n d ng thu t toán A v i ư c lư ng h=0 có th ch n ra ư c " ư ng i" t i ưu. Ta ch n ư c lư ng h=0 vì hai lý do sau (1) không gian bài toán nh nên ta không c n ph i gi i h n r ng tìm ki m (2) xây d ng m t ư c lư ng như v y là tương i khó khăn, c bi t là làm sao h th ng không ánh giá quá cao h. XI. BI U DI N TRI TH C B NG FRAME XI.1. Khái ni m Frame là m t c u trúc d li u ch a ng t t c nh ng tri th c liên quan nm t i tư ng c th nào ó. Frames có liên h ch t ch n khái ni m hư ng i tư ng (th c ra frame là ngu n g c c a l p trình hư ng i tư ng). Ngư c l i v i các phương pháp bi u di n tri th c ã ư c c p n, frame " óng gói" toàn b m t i tư ng, tình hu ng ho c c m t v n ph c t p thành m t th c th duy nh t có c u trúc. M t frame bao hàm trong nó m t kh i lư ng tương i l n tri th c v m t i tư ng, s ki n, v trí, tình hu ng ho c nh ng y u t khác. Do ó, frame có th giúp ta mô t khá chi ti t m t i tư ng. Dư i m t khía c nh nào ó, ngư i ta có th xem phương pháp bi u di n tri th c b ng frame chính là ngu n g c c a ngôn ng l p trình hư ng i tư ng. Ý tư ng c a phương pháp này là "thay vì b t ngư i dùng s d ng các công c ph như dao m h p, ngày nay các hãng s n xu t h p thư ng g n kèm các n p m h p ngay bên trên v lon. Như v y, ngư i dùng s không bao gi ph i lo l ng n vi c tìm m t thi t b m h p n a!". Cũng v y, ý tư ng chính c a frame (hay c a phương pháp l p trình hư ng i tư ng) là khi bi u di n m t tri th c, ta s "g n kèm" nh ng thao tác thư ng g p trên tri th c này. Ch ng h n như khi mô t khái ni m v hình ch nh t, ta s g n kèm cách tính chu vi, di n tích. Frame thư ng ư c dùng bi u di n nh ng tri th c "chu n" ho c nh ng tri th c ư c xây d ng d a trên nh ng kinh nghi m ho c các c i m ã ư c hi u bi t c n k . B não c a con ngư i chúng ta v n luôn "lưu tr " r t nhi u các tri th c chung mà khi c n, chúng ta có th "l y ra" v n d ng nó trong nh ng v n c n ph i gi i quy t. Frame là m t công c thích h p bi u di n nh ng ki u tri th c này. 73 Sưu t m b i: www.daihoc.com.vn
XI.2. C u trúc c a frame M i m t frame mô t m t i tư ng (object). M t frame bao g m 2 thành ph n cơ b n là slot và facet. M t slot là m t thu c tính ct i tư ng ư c bi u di n b i frame. Ví d : trong frame mô t xe hơi, có hai slot là tr ng lư ng và lo i máy. M i slot có th ch a m t ho c nhi u facet. Các facet ( ôi lúc ư c g i là slot "con") c t m t s thông tin ho c th t c liên quan n thu c tính ư c mô t b i slot. Facet có nhi u lo i khác nhau, sau ây là m t s facet thư ng g p. Value (giá tr ) : cho bi t giá tr c a thu c tính ó (như xanh, , tím vàng n u slot là màu xe). Default (giá tr m c nh) : h th ng s t ng s d ng giá tr trong facet này n u slot là r ng (nghĩa là ch ng có c t nào!). Ch ng h n trong frame v xe, xét slot v s lư ng bánh. Slot này s có giá tr 4. Nghĩa là, m c nh m t chi c xe hơi s có 4 bánh! Range (mi n giá tr ) : (tương t như ki u bi n), cho bi t giá tr slot có th nh n nh ng lo i giá tr gì (như s nguyên, s th c, ch cái, ...) If added : mô t m t hành ng s ư c thi hành khi m t giá tr trong slot ư c thêm vào (ho c ư c hi u ch nh). Th t c thư ng ư c vi t dư i d ng m t script. If needed : ư c s d ng khi slot không có giá tr nào. Facet mô t m t hàm tính ra giá tr c a slot. Frame : XE HƠI Thu c l p : phương ti n v n chuy n. Tên nhà s n xu t : Audi Qu c gia c a nhà s n xu t : c Frame MÁY Model : 5000 Turbo Xy-lanh : 3.19 inch Lo i xe : Sedan T l nén : 3.4 inche Tr ng lư ng : 3300lb Xăng : TurboCharger S lư ng c a : 4 (default) Mã l c : 140 hp H ps :3s t ng S lư ng bánh : 4 (default) Máy (tham chi u n frame Máy) 74 Sưu t m b i: www.daihoc.com.vn
Ki u : In-line, overhead cam S xy-lanh : 5 Kh năng tăng t c 0-60 : 10.4 giây ¼ d m : 17.1 giây, 85 mph. XI.3. Tính k th a Trong th c t , m t h th ng trí tu nhân t o thư ng s d ng nhi u frame ư c liên k t v i nhau theo m t cách nào ó. M t trong nh ng i m thú v c a frame là tính phân c p. c tính này cho phép k th a các tính ch t gi a các frame. Hình sau ây cho th y c u trúc phân c p c a các lo i hình hình h c cơ b n. G c c a cây trên cùng tương ng v i m c tr u tư ng cao nh t. Các frame n m dư i cùng (không có frame con nào) g i là lá. Nh ng frame n m m c th p hơn có th th a k t t c nh ng tính ch t c a nh ng frame cao hơn. Các frame cha s cung c p nh ng mô t t ng quát v th c th . Frame có c p càng cao thì m c t ng quát càng cao. Thông thư ng, frame cha s bao g m các nh nghĩa c a các thu c tính. Còn các frame con s ch a ng giá tr th c s c a các thu c tính này. 75 Sưu t m b i: www.daihoc.com.vn
M t ví d bi u di n các i tư ng hình h c b ng frame Các ki u d li u cơ b n : Area : numeric; // di n tích Height : numeric; //chi u cao Perimeter : numberic; //chu vi Side : numeric; //c nh Diagonal : numeric; // ư ng chéo Radius : numeric; //bán kính Angle : numeric; //góc Diameter : numeric; // ư ng kính pi : (val:numeric = 3.14159) Frame : CIRCLE (hình tròn) r : radius; s : area; p : perimeter; d : diameter; d = 2  r; s = pi  r2; p = 2  pi  r; Frame RECTANGLE (hình ch nh t) b1 : side; b2 : side; s : area; p : perimeter; s = b1  b2; 76 Sưu t m b i: www.daihoc.com.vn
p = 2  (b1+b2); d2 = b12 + b22; Frame SQUARE (hình vuông) Là : RECTANGLE b1 = b2; Frame RHOMBUS (hình thoi) b : side; d1 : diagonal; d2 : diagonal; s : area; p : perimeter; alpha1 : angle; alpha2 : angle; h : height; cos (alpha2/2)  d1 = h; s = d1  d2 / 2; p = 4  b; s = b  h; cos (alpha2/2)/(2 b) = d2; Chúng ta có th d dàng khai báo các i tư ng hình h c khác theo cách này. Sau khi ã bi u di n các tri th c v các hình hình h c cơ b n xong, ta có th v n d ng nó gi i các bài toán hình h c, ch ng h n bài toán tính di n tích. Ví d , cho hình vuông k và vòng tròn n i ti p c, bi t c nh hình vuông có chi u dài là x, hãy vi t chương trình tính di n tích ph n tô en. 77 Sưu t m b i: www.daihoc.com.vn