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

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

Thêm vào BST

Báo xấu

145
lượt xem 25
download

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

Phát sinh tập luật Tối ưu tập luật Loại bỏ mệnh đề thừa Xây dựng mệnh đề mặc định Và một số bài tập về các chươ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 14

Annie Th p T.Bình Không Cháy Kartie Th p Nh Có Không VC.Cao(Cao) = (0/1,1/1) = (0,1) VC.Cao(T.B) = (1/1,0/1) = (1,0) VC.Cao(Th p) = (1/2,1/2) VC.N ng (Nh ) = (1/2,1/2) VC.N ng (T.B) = (1/2,1/2) VC.N ng (N ng) = (0,0) VKem (Có) = (0/2,2/2) = (0,1) VKem (Không) = (2/2,0/2) = (1,0) 2 thu c tính dùmg kem và chi u cao u có 2 vector ơn v . Tuy nhiên, s phân ho ch c a thu c tính dùng kem là ít hơn nên ta ch n phân ho ch theo thu c tính dùng kem. Cây nh danh cu i cùng c a chúng ta s như sau : II.2.2. o h n lo n Thay vì ph i xây d ng các vector c trưng như phương pháp c a Quinlan, ng v i m i thu c tính d n xu t ta ch c n tính ra o h n lo n và l a ch n thu c tính nào có o h n lo i là th p nh t. Công th c tính như sau : 92 Sưu t m b i: www.daihoc.com.vn
TA = trong ó : bt là t ng s ph n t có trong phân ho ch bj là t ng s ph n t có thu c tính d n xu t A có giá tr j. bri : t ng s ph n t có thu c tính d n xu t A có giá tr j và thu c tính m c tiêu có giá tr i. II.3. Phát sinh t p lu t Nguyên t c phát sinh t p lu t t cây nh danh khá ơn gi n. ng v i m i nút lá, ta ch vi c i t nh cho n nút lá ó và phát sinh ra lu t tương ng. C th là t cây nh danh k t qu cu i ph n II.2 ta có các lu t sau (xét các nút lá t trái sang ph i) (Màu tóc vàng) và (có dùng kem)  không cháy n ng (Màu tóc vàng) và (không dùng kem)  cháy n ng (Màu tóc nâu)  không cháy n ng (Màu tóc )  cháy n ng Khá ơn gi n ph i không? Có l không có gì ph i nói gì thêm. Chúng ta hãy th c hi n bư c cu i cùng là t i ưu t p lu t. II.4. T i ưu t p lu t II.4.1. Lo i b m nh th a Khác so v i các phương pháp lo i b m nh th a ã ư c trình bày trong ph n bi u di n tri th c (ch quan tâm n logic hình th c), phương pháp lo i b m nh th a ây d a vào d li u. V i ví d và t p lu t ã có ph n trư c, b n hãy quan sát lu t sau : (Màu tóc vàng) và (có dùng kem)  không cháy n ng Bây gi ta hãy l p m t b ng (g i là b ng Contigency), b ng th ng kê nh ng ngư i có dùng kem tương ng v i tóc màu vàng và b cháy n ng hay không. Trong d li u ã cho, có 3 ngư i không dùng kem. 93 Sưu t m b i: www.daihoc.com.vn
Không cháy Cháy n ng n ng Màu 2 0 vàng Màu 1 0 khác Theo b ng th ng kê này thì rõ ràng là thu c tính tóc vàng (trong lu t trên) không óng góp gì trong vi c ưa ra k t lu n cháy n ng hay không (c 3 ngư i dùng kem u không cháy n ng) nên ta có th lo i b thu c tính tóc vàng ra kh i t p lu t. Sau khi lo i b m nh th a, t p m nh c a chúng ta trong ví d trên s còn : (có dùng kem)  không cháy n ng (Màu tóc vàng) và (không dùng kem)  cháy n ng (Màu tóc nâu)  không cháy n ng (Màu tóc )  cháy n ng Như v y quy t c chung có th lo i b m t m nh là như th nào? R t ơn gi n, gi s lu t c a chúng ta có n m nh : A1 và A2 và … và An  R ki m tra xem có th lo i b m nh Ai hay không, b n hãy l p ra m t t p h p P bao g m các ph n t th a t t c m nh A1 , A2 , … Ai-, Ai+1, …, An (lưu ý : không c n xét là có th a Ai hay không, ch c n th a các m nh còn l i là ư c) Sau ó, b n hãy l p b ng Contigency như sau : R R Ai E F  G H Ai Trong ó E là s ph n t trong P th a c Ai và R. F là s ph n t trong P th a Ai và không th a R 94 Sưu t m b i: www.daihoc.com.vn
G là s ph n t trong P không th a Ai và th a R H là s ph n t trong P không th a Ai và không th a R N u t ng F+H = 0 thì có th lo i b m nh Ai ra kh i lu t. II.4.2. Xây d ng m nh m c nh Có m t v n t ra là khi g p ph i m t trư ng h p mà t t c các lu t u không th a thì ph i làm như th nào? M t cách hành ng là t ra m t lu t m c nh i lo i như : N u không có lu t nào th a  cháy n ng (1) Ho c N u không có lu t nào th a  không cháy n ng. (2) (ch có hai lu t vì thu c tính m c tiêu ch có th nh n m t trong hai giá tr là cháy n ng hay không cháy n ng) Gi s ta ã ch n lu t m c nh là (2) thì t p lu t c a chúng ta s tr thành : (Màu tóc vàng) và (không dùng kem)  cháy n ng (Màu tóc )  cháy n ng N u không có lu t nào th a  không cháy n ng. (2) Lưu ý r ng là chúng ta ã lo i b i t t c các lu t d n n k t lu n không cháy n ng và thay nó b ng lu t m c nh. T i sao v y? B i vì các lu t này có cùng k t lu n v i lu t m c nh. Rõ ràng là ch có th có m t trong hai kh năng là cháy n ng hay không. V n là ch n lu t nào? Sau ây là m t s quy t c. 1) Ch n lu t m c nh sao cho nó có th thay th cho nhi u lu t nh t. (trong ví d c a ta thì nguyên t c này không áp d ng ư c vì có 2 lu t d n n cháy n ng và 2 lu t d n n không cháy n ng) 2) Ch n lu t m c nh có k t lu n ph bi n nh t. Trong ví d c a chúng ta thì nên ch n lu t (2) vì s trư ng h p không cháy n ng là 5 còn không cháy n ng là 3. 3) Ch n lu t m c nh sao cho t ng s m nh c a các lu t mà nó thay th là nhi u nh t. Trong ví d c a chúng ta thì lu t ư c ch n s là lu t (1) vì t ng s m nh c a lu t d n n cháy n ng là 3 trong khi t ng s m nh c a lu t d n n không cháy n ng ch là 2. 95 Sưu t m b i: www.daihoc.com.vn
BÀI T P CHƯƠNG 1 1) Vi t chương trình gi i bài toán hành trình ngư i bán hàng rong b ng hai thu t gi i GTS1 và GTS2 trong trư ng h p có n a i m khác nhau. 2) Vi t chương trình gi i bài toán phân công công vi c b ng cách ng d ng nguyên lý th t . 3) ng d ng nguyên lý th t , hãy gi i bài toán chia v t sau. Có n v t v i kh i lư ng l n lư t là M1, M2, … Mn. Hãy tìm cách chia n v t này thành hai nhóm sao cho chênh l ch kh i lư ng gi a hai nhóm này là nh nh t. 4) Vi t chương trình gi i bài toán mã i tu n. 5) Vi t chương trình gi i bài toán 8 h u. 6) Vi t chương trình gi i bài toán Ta-canh b ng thu t gi i A*. 7) Vi t chương trình gi i bài toán tháp Hà N i b ng thu t gi i A*. 8)* Vi t chương trình tìm ki m ư ng i ng n nh t trong m t b n t ng quát. B n ư c bi u di n b ng m t m ng hai chi u A, trong ó A[x,y]=0 là có th i ư c và A[x,y]= 1 là v t c n. Cho phép ngư i dùng click chu t trên màn hình t ob n và xác nh i m xu t phát và k t thúc. Chi phí i t m t ô b t kỳ sang ô k c n nó là 1. M r ng bài toán trong trư ng h p chi phí di chuy n t ô (x,y) sang m t b t kỳ k (x,y) là A[x,y]. CHƯƠNG 2 1. Vi t chương trình minh h a các bư c gi i bài toán ong nư c (s d ng h a càng t t). 2. Vi t chương trình cài t hai thu t toán Vương H o và Robinson trong ó li t kê các bư c ch ng minh m t bi u th c logic. 3. Vi t chương trình gi i bài toán tam giác t ng quát b ng m ng ng nghĩa (lưu ý s d ng thu t toán ký pháp ngh ch o Ba Lan) 4. Hãy th xây d ng m t b lu t ph c t p hơn trong ví d ã ư c trình bày dùng chu n oán h ng hóc c a máy tính. Vi t chương trình ng d ng b lu t này trong vi c chu n oán h ng hóc c a máy tính (s dùng thu t toán suy di n lùi). 5. Hãy cài t các frame c t các i tư ng hình h c b ng k thu t hư ng i tư ng trong ngôn ng l p trình mà b n quen dùng. Hãy xây d ng m t ngôn ng script ơn gi n cho phép ngư i dùng có th s d ng các frame này trong vi c gi i m t s bài toán hình h c ơn gi n. CHƯƠNG 3 1) Cho b ng s li u sau 96 Sưu t m b i: www.daihoc.com.vn
Hãy xây d ng cây nh danh và tìm lu t xác nh m t ngư i là Châu Âu hay Châu Á b ng hai phương pháp vector c trưng c a Quinlan và oh n lo n. STT Dáng Cao Gi i Châu 1 To TB Nam Á 2 Nh Cao Nam Á 3 Nh TB Nam Âu 4 To Cao Nam Âu 5 Nh TB N Âu 6 Nh Cao Nam Âu 7 Nh Cao N Âu 8 To TB N Âu 2)* Vi t chương trình cài t t ng quát thu t toán h c d a trên vi c xây d ng cây nh danh. Chương trình yêu c u ngư i dùng ưa vào danh sách các thu c tính d n xu t, thu c tính m c tiêu cùng v i t t c các giá tr c a m i thu c tính; yêu c u ngư i dùng cung c p b ng s li u quan sát. Chương trình s li t kê lên màn hình các lu t mà nó tìm ư c t b ng s li u. Sau ó, yêu c u ngư i dùng nh p vào các trư ng h p c n xác nh, h th ng s ưa ra k t lu n c a trư ng h p này. Lưu ý : Nên s d ng m t h qu n tr CSDL cài t chương trình này. GS.TSKH. Hoàng Ki m Ths. inh Nguy n Anh Dũng 97 Sưu t m b i: www.daihoc.com.vn