Đánh giá quá trình (bài tập về nhà, bài tập dự án) đọc hiểu, biểu diễn ví dụ và cài đặt kỹ thuật biểu diễn suy diễn tri thức
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (109.85 KB, 7 trang )
ÁNH GIÁ I M QUÁ TRÌNH
Gi ng viên: TS. Ph m V n H i, HUST
BÀI T P V NHÀ (SV l p ào t o qu c t ):
Sinh viên cài t b ng ngơn ng l p trình tùy ý mơ t thu t tốn suy di n
ti n và lùi, v cây lu t kèm các các phương th c: t o m i, xem xóa, s a
c a các nút.
BÀI T P D ÁN:
D a vào các cơ ch suy di n ti n và lùi, sinh viên xây d ng bài t p d
án theo nhóm cho mi n ng d ng th c ti n. Yêu c u h th ng bao g m
các ch c n ng qu n tr , c p nh t lu t, thay i và s a i tri th c trong
cơ s tri th c. Mi n ng d ng do sinh viên t
xu t.
N i dung tham kh o:
1. Suy di n ti n:
i t! gi thi t ta s suy di n d"n t i k t qu mong mu n. Suy di n ti n là
quá trình suy di n b#t
c như v y cho
u t! t p s ki n ã bi t, rút ra nh ng s ki n m i và
n khi có ư$c s ki n c n ch ng minh ho c khơng có.
Q trình suy di n ti n là quá trình xem xét các lu t, v i m%i lu t ta xét ph n
i u ki n ( v trái) v i ph n k t lu n ( v ph i) và khi mà t t c các i u
ki n c a lu t
l
u th&a mãn thì ta suy ra s ki n trong ph n k t lu n. Chính vì
ó mà có tên là suy di n ti n. Trong m%i bư c c a th t c, ngư'i ta xét
m(t lu t trong t p lu t. So sánh m%i i u ki n ( v trái) c a t p lu t v i các
s ki n trong cơ s s ki n, n u t t c các i u ki n c a lu t ư$c tho mãn
thì s ki n trong ph n k t lu n ư$c xem là s ki n ư$c suy ra. N u s
ki n này là s ki n m i (khơng có trong b( nh làm vi c) thì nó ư$c ưa
vào b( nh làm vi c. Quá trình trên c l p l i cho
1
n khi nào khơng có lu t
nào sinh ra s ki n m i. Quá trình suy di n ti n không
quy t m(t v n
nh hư ng t i gi i
nào c , không hư ng t i tìm ra câu tr l'i cho m(t câu h&i
nào c . Suy di n ti n ch) là quá trình suy ra các s ki n m i t! các s ki n
có trong b( nh làm vi c.
Thêm thông tin vào b(
nh làm vi c
Xét lu t
Xét lu t ti p theo
u tiên
True
False
Gi thi t kh p
v i b( nh
Còn lu t
True
False
K t lu n vào b( nh
làm vi c
D!ng suy di n
S
suy di n ti n t ng qt
u i m:
• Ưu i+m chính c a suy di n ti n là làm vi c t t khi bài toán v b n
ch t i thu th p thông tin r i th y i u mình c n suy di n.
2
• Suy di n ti n cho ra s lư$ng l n các thông tin t! các thông tin ban
u. Nó sinh ra nhi u thơng tin m i.
• Suy di n ti n là ti p c n lý tư ng v i các lo i bài toán c n gi i quy t
các nhi m v như l p k ho ch, i u hành, i u khi+n và di n d ch.
Nh
c i m:
• H th ng suy di n không c m nh n ư$c m(t vài thông tin quan
tr,ng. H th ng h&i các câu h&i có th+ h&i mà khơng bi t r ng ch) c n
n k t lu n ư$c.
m(t ít câu thơi ã có th+ i
• H th ng có th+ h&i c câu h&i khơng liên quan. Có th+ các câu tr l'i
quan tr,ng, nhưng làm ngư'i dùng lúng túng khi ph i tr l'i các câu
khơng dính dáng
n ch
.
Thu t toán suy di n ti n: [5]
Trong gi i thu t sau R = { ,…., }, là các lu t s n xu t.
- Tgian là các t p s ki n úng
- Vet là t p các lu t s n xu t ã s d ng.
- Loc(F, Rule) là th t c cho t p các lu t r ∈ Rule, r:left → q sao cho
left ⊆ F.
Phương pháp:
{
Tgian = GT; Vet = 0; Thoa = Loc(Tgian,R);
While ((Thoa ≠ 0) and (KL ⊄ GT)) do
/*r: left →q*/
{
r ← Get(Thoa)
Vet = Vet ∪ {r}; R=R\{r};
Tgian = Tgian ∪ {q}; Thoa = Loc(Tgian, R)
}
If (KL ⊂ Tgian) Then exit (“Thành công”)
Else exit (“Không thành công”);
}
u tiên h th ng l y các thơng tin v các bài tốn do ngư'i s d ng cung
c p và t chúng vào b( nh làm vi c. Suy lu n quét các lu t theo dãy xác
3
nh trư c; xem ph n gi thi t có trùng kh p v i n(i dung trong b( nh
không. N u phát hi n m(t lu t như mô t trên thì b sung k t lu n c a lu t
này vào b( nh . Lu t này g,i là cháy. Ti p t c quá trình này, có th+ b& qua
các lu t ã cháy. Q trình d!ng l i khi không kh p ư$c lu t nào hay th y
i u c n ch ng minh. Lúc này b( nh có các thơng tin c a ngư'i dùng và
thông tin do h th ng suy lu n.
2. Suy di n lùi:
Ý tư ng c a suy di n lùi là xu t phát t! k t lu n ta s suy di n d"n t i m(t
i u gì ó úng trong gi thi t ã cho. Là quá trình xu t phát t! s ki n c n
ch ng minh và thay vào ó là nh ng s ki n
v trái c a 1 lu t có v ph i là
s ki n c n ch ng minh. Quá trình này ư$c th c hi n cho
n khi ưa v các
s ki n là t p s ki n con c a t p s ki n gi thi t. Ta có bi+u
suy di n lùi
t ng quát như sau:
Thêm thông tin vào
b( nh làm vi c
Ki+m tra b( nh
làm vi c
Tìm ích m i
True
ích kh p
v i gi thi t
False
True
Quay lui
Còn lu t
False
True
False
D!ng suy di n
K t lu n vào ích
S
suy di n lùi t ng quát
4
u i m:
• M(t trong các ưu i+m chính c a suy di n lùi là phù h$p v i bài toán
ưa ra gi thuy t r i xem hi u qu c a gi thuy t ó có úng khơng.
•
Suy di n lùi t p trung vào ích ã cho. Nó t o ra m(t lo t câu h&i ch)
liên quan
nv n
ang xét,
n hoàn c nh thu n ti n
i v i ngư'i
dùng.
• Khi suy di n lùi mu n suy di n cái gì ó t! các thơng tin ã bi t, nó ch)
tìm trên m(t ph n c a cơ sơ tri th c thích áng
Nh
i v i bài tốn ang xét.
c i m:
• Như$c i+m cơ b n c a lo i suy di n này là nó theo u i m(t dịng suy
lu n, thay vì úng ra ph i d!ng
ó mà sang ch% khác. Tuy nhiên,
ngư'i ta có th+ dùng nhân t tin c y + kh#c ph c hi n tư$ng này.
• So v i suy di n lùi, suy di n ti n ơn gi n hơn. Song quá trình suy di n
ti n ph i huy (ng m,i lu t có th+ áp d ng ư$c, mà không lưu ý
n
li u lu t có liên quan
i
n k t lu n mong mu n hay không. Do v y,
v i các cơ s tri th c l n v i s lu t ngày càng t ng, thu t gi i này d"n
t i bùng n t h$p. Ngư$c l i, suy di n lùi ph c t p hơn, nhưng có ưu
i+m là ch) ch,n nh ng lu t hư ng t i ích
suy di n lùi ư$c cài
t
t ta. V th c ch t cơ ch
ây tương ng v i tìm ki m sâu trên
th .
Thu t tốn suy di n lùi: [5]
- Goal là t p s ki n c n ph i ch ng minh (t ch c dư i d ng Stack).
- Vet là t p lu t ã s d ng (t ch c dư i d ng Stack).
- Tìm lu t (f, j, Rule, i) là th t c xác nh , m ≥ j ≥ i+1 sao cho có
d ng :left →f. N u khơng tìm th y thì j = m +1, m là s lu t trong
Rule.
5
{
If (KL ⊆ GT) then exit(“Thành công”)
Else
{
Goal = KL\GT; Vet=0; back =false;
f →get(goal);
repeat {if f ∉GT then
{tìm lu t (f, j, r, 0) //Tìm lu t th j sao cho :
If (j≤m) then
{ Vet= Vet ∪{(f, j)}
goal = goal ∪
\GT;
}
Else // s quay lui theo các lu t
{
back=true;
While ((f ∉ KL) and (back)) do
{
repeat {(g, k) ←get(vet);
goal = goal \
}
;
until f ∉
Tìm lu t (g, l, r, k);
// Tìm phương án khác i v i g
If (l<=m) then
{
goal=goal \
;
goal=goal ∪
\ GT;
Vet = Vet ∪{(g, l)};
Back = false;
}
Else f = g;
}
}
}
If (goal = 0) then break
Else f ←get(goal);
}
Until f ∉ KL;
6
⇒
If ((f ∉ KL) and back) then exit(“Không thành công”)
Else exit (“Vet”);
}
}
7
