Bài giảng Bên trong một hệ cơ sở tri thức

Heä Côsô tri thöùc= Cô sô ûtri thöùc + Ñoäng cô suy dieãn

BEÂN TRONG MOÄT HEÄ CÔ SÔÛ TRI THÖÙC

Caáu truùc chung cuûa moät heäCSTT

Cô sôû tri thöùc

Toång quan quaù trình xaây döïng heä CSTT

Moät soá böôùc cô baûn ñeå xaây döïng heä Cô sôû tri thöùc

• Tieáp caän chuyeân gia • Thu thaäp, toå chöùc tri thöùc • Choïn löïa coâng cuï phaùt trieån heä CSTT • Caøi ñaët heä CSTT

Moät soá tieâu chuaån phaân loaïi caùc heä CSTT

Heä CSTTñoùng • ñöôïc xaây döïng vôùi moät soá “tri thöùc lónh vöïc” ban ñaàu,vaø chæ nhöõng tri thöùc ño ùma øthoâi trong suoát quaùtrình hoaït ñoäng hay suoát thôøi gian soáng cuûa noù.

• Tính ñoùng, môû, keát hôïp • Phöông phaùp bieåu dieãn tri thöùc • Lónh vöïc öùng duïng

Heä CSTT môû

Heä CSTT keát hôïp

• Bao goàm söï keát hôïp giöõa heä ñoùng vaø heä

heä cô sôû tri thöùc tieân tieán hôn, coù khaû naêng boå sung tri thöùc trong quaù trình hoaït ñoäng, khaùm phaù

môû,heä keát hôïp giöõa CSTT va øCSDL,heä keát hôïp giöõa he äCSTT naøy vôùi moät heä CSTT khaùc, …

• Nhöõng heä CSTT keát hôïp thöôøng phaùt trieån

maïnh döïa treân tri thöùc lieân ngaønh.

• Ví duï: nhöõng heä hoã trôï ra quyeát ñònh trong

ñôøi soáng,kinh teá vaø khoa hoïc, nhöõng heä chaån ñoaùn, döï baùo

Moät soá heä CSTT ñieån hình

Ví duï: Maùy ñieàu nhieät

MÙA TRONG NĂM MÁY

• Heä giaûi toaùn • Heä chaån ñoaùn y khoa MYCIN • Heä ñieàu khieån töï ñoäng • Heä döï baùo thôøi tieát

ĐIỀU

NGÀY TRONG TUẦN NHIỆT NHIỆT ĐỘ THÍCH HỢP

GIỜ TRONG NGÀY

CÁC ĐỐI TƯỢNG GIẢI PHÁP ĐIỀU NHIỆT 7 giải pháp điều nhiệt

-Đặt máy điều nhiệt là “14o C”

Đối tượng

Giá trị

Tháng

Tháng 1, …, Tháng 12

- Đặt máy điều nhiệt là “15o C”

Mùa

Xuân, hè, thu, đông

- Đặt máy điều nhiệt là “16o C”

Ngày

Thứ 2, …, Thứ 7, Chủ nhật

- Đặt máy điều nhiệt là “18o C”

Thời gian

Trước 9, Sau 17, Từ 9 -> 17

- Đặt máy điều nhiệt là “20o C”

Sự khởi động

Trong giờ làm việc, ngoài giờ làm việc

- Đặt máy điều nhiệt là “24o C”

- Đặt máy điều nhiệt là “27o C”

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 2: Luật dẫn 1:

Nếu Ngày là Thứ 7 Nếu Ngày Thứ 2 là

Hoặc Ngày Thứ 3 là

Hoặc Ngày Thứ 4 là Hoặc Ngày là Chủ nhật Hoặc Ngày Thứ 5 là

Hoặc Ngày Thứ 6 là

là Thì Hôm nay Ngày làm việc Thì Hôm nay là Cuối tuần

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 4: Luật dẫn 3:

Nếu Hôm nay là Ngày làm việc

Và Thời gian trước 9 giờ sáng Và Thời gian giữa 9 giờ sáng và 5 giờ chiều

Thì Sự khởi động là ‘trong thời gian làm việc’ Thì Sự khởi động là ‘ngoài thời gian làm việc’

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 5: Luật dẫn 6:

Nếu Hôm nay là Ngày làm việc Nếu Hôm nay là Cuối tuần

Và Thời gian là sau 5 giờ chiều Thì Sự khởi động là ‘ngoài thời gian làm việc’

Thì Sự khởi động là ‘ngoài thời gian làm việc’

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 7: Luật dẫn 8:

Nếu Tháng là Tháng 3

Nếu Tháng là Tháng 1

Hoặc Tháng là Tháng 4

Hoặc Tháng là Tháng 2

Hoặc Tháng là Tháng 5

Hoặc Tháng là Tháng 12

Thì Mùa là Mùa Thu

Thì Mùa là Mùa Hè

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 9: Luật dẫn 10:

Nếu Tháng là Tháng 6 Nếu Tháng là Tháng 9

Hoặc Tháng là Tháng 7 Hoặc Tháng là Tháng 10

Hoặc Tháng là Tháng 8 Hoặc Tháng là Tháng 11

Thì Mùa là Mùa Đông Thì Mùa là Mùa Xuân

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 11: Luật dẫn 12:

Nếu Mùa là Mùa Xuân Nếu Mùa là Mùa Xuân

Sự khởi động là ‘trong thời gian làm Và Sự khởi động là ‘ngoài thời gian làm việc’ Và việc’

Thì Cấu hình điều nhiệt là ’15 độ’ Thì Cấu hình điều nhiệt là ’20 độ’

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 13: Luật dẫn 14:

Nếu Mùa là Mùa Hè Nếu Mùa là Mùa Hè

Và Sự khởi động là ‘trong thời gian làm việc’ Và Sự khởi động là ‘ngoài thời gian làm việc’

Thì Cấu hình điều nhiệt là ’24 độ’ Thì Cấu hình điều nhiệt là ’27 độ’

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 16: Luật dẫn 15:

Nếu Mùa là Mùa Thu Nếu Mùa là Mùa Thu

Và Sự khởi động là ‘ngoài thời gian làm việc’ Và Sự khởi động là ‘trong thời gian làm việc’

Thì Cấu hình điều nhiệt là’16 độ’ Thì Cấu hình điều nhiệt là ’20 độ’

CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT) CƠ SỞ TRI THỨC LUẬT DẪN (18 LUẬT)

Luật dẫn 18: Luật dẫn 17:

Nếu Mùa là Mùa Đông Nếu Mùa là Mùa Đông

Và Sự khởi động là ‘ngoài thời gian làm việc’ Và Sự khởi động là ‘trong thời gian làm việc’

Thì Cấu hình điều nhiệt là ’14 độ’ Thì Cấu hình điều nhiệt là ’18 độ’

MINH HỌA

Giờ ? Tháng ? Thứ ?

9 < Giờ < 17 8 Thứ 6

Luật 1 Luật 3 Luật 9

HEÄ GIAÛI TOAÙN DÖÏA TREÂN TRI THÖÙC

Mùa = Hôm nay= Sự hoạt động =

Mùa Đông ngày làm việc trong giờ làm việc

Máy điều nhiệt = 18o C

Yeâu caàu

•

Heä giaûi toaùn=Tieân ñeà,ñònh lyù+Laäp luaänlogic (toaùn hoïc)

•

Cho pheùp kieåm tra quaù trình suy luaän bao goàm vieäc theå hieän cuï theå caùc böôùc giaûi baøi toaùn vaø traû lôøi hay giaûi thích cho quaù trình giaûi. Cho pheùp vieäc hieäu chænh vaø caäp nhaät cô sôû tri thöùc nhö theâm vaø loaïi bôùt kieán thöùc trong cô sôû tri thöùc. Söû duïng caùc heuristic (thöôøng khoâng ñaày ñuû) trong vieäc suy luaän giaûi baøi toaùn nhaèm ñaït ñöôïc caùc lôøi giaûi toát.

Caáu truùc cuûa moät heä giaûi baøi toaùn döïa treân tri thöùc

Baûo ñaûm söï taùch bieät giöõa cô sôû tri thöùc vaø boä suy dieãn • Seõ laøm cho vieäc bieåu dieãn tri thöùc ñöôïc thöïc hieän moät

caùch töï nhieân hôn.

• Caùc nhaø thieát keá heä thoáng giaûi baøi toaùn thoâng minh seõ taäp trung vaøo veäc naém baét vaø toå chöùc cô sôû tri thöùc • Seõ taêng cöôøng tính moâ-ñun hoùa cuûa phaàn cô sôû tri thöùc, boä suy dieãn vaø boä phaän caäp nhaät, hieäu chænh kieán thöùc

• Cho pheùp cuøng moät chieán löôïc ñieàu khieån vaø giao tieáp coù theå ñöôïc söû duïng cho nhieàu heä thoáng khaùc nhau

• Giuùp ta coù theå thöû nghieäm nhieàu chieán löôït ñieàu khieån khaùc nhau treân cuøng moät cô sôû tri thöùc

Cô sôû tri thöùc

Vaán ñeà Suy dieãn Töï ñoäng

• Phöông phaùp hôïp giaûi, luaät “Modus Ponens”,

• raát ña daïng • bao goàm:

luaät “Modus Tollens” vaø luaät “tam ñoaïn luaän” .

– caùc khaùi nieäm töø ñôn giaûn ñeán coù caáu truùc phöùc

taïp

– caùc heä thöùc tính toaùn vôùi nhöõng qui luaät nhaát ñònh – caùc lieân heä ña daïng bao goàm caû ñònh tính laãn

• Phöông phaùp suy dieãn tieán • Phöông phaùp suy dieãn luøi • Keát hôïp suy dieãn tieán vaø suy dieãn luøi

ñònh löôïng

– caùc luaät daãn vaø caùc heuristics

Moät soá phaàn meàm giaûi toaùn

boä phaàn meàm Engineering 2000

Moät soá keát quaû nghieân cöùu xaây döïng heä giaûi toaùn hình hoïc • Chæ xeùt moät soá luaät suy dieãn cuï theå treân caùc quan heä hình hoïc vaø öùng vôùi moãi luaät phaûi vieát rieâng moät thuû tuïc thi haønh luaät

• Chöa coù moät cô sôû tri thöùc coù theå hieäu chænh

• • Chöông trình StudyWorks • Chöông trình Math Express • Phaàn meàm toaùn hoïc MAPLE

ñöôïc vaø boä suy dieãn seõ hoaït ñoäng döïa treân cô sôû tri thöùc

• Chöa xem xeùt ñeán vaán ñeà tính toaùn • Chöa coù moät ngoân ngöõ qui öôùc cho vieäc ñaëc

taû caùc daïng baøi toaùn

Vaán ñeà

• Chuùng ta phaûi thöïc hieän nhöõng tính toaùn hay suy dieãn ra nhöõng yeáu toá caàn thieát naøo ñoù töø moät soá yeáu toá ñaõ ñöôïc bieát tröôùc

MAÏNG SUY DIEÃN-TÍNH TOAÙN

Ví duï 1

• Moät vaät theå coù khoái löôïng m chuyeån ñoäng thaúng vôùi gia toác khoâng thay ñoåi laø a trong moät khoaûng thôøi gian tính töø thôøi ñieåm t1 ñeán thôøi ñieåm t2

• Vaän toáùc ban ñaàu cuûa vaät theå laø v1, vaän toác ôû thôøi

• f = m * a; • Δv = a*Δt; • Δs = v*Δt; • 2*v = v1 + v2; • Δv = v2 - v1; • Δt = t2 - t1;

ñieåm cuoái laø v2, vaø vaän toác trung bình laø v • Khoaûng caùch giöõa ñieåm ñaàu vaø ñieåm cuoái laø Δs • Löïc taùc ñoäng cuûa chuyeån ñoäng laø f • Ñoä bieán thieân vaän toác giöõa 2 thôøi ñieåm laø Δv • Ñoä bieán thieân thôøi gian laø Δt

Ví duï 2

Muïc tieâu

• Xaùc ñònh tính giaûi ñöôïc cuûa moät baøi toaùn treân

maïng tính toaùn

• Trong hoùa hoïc chuùng ta thöôøng phaûi söû duïng caùc phaûn öùng hoùa hoïc ñeå ñieàu cheá caùc chaát naày töø caùc chaát khaùc

• Trong tröôøng hôïp baøi toaùn laø giaûi ñöôïc thì

(cid:206) Cho tröôùc moät soá chaát hoùa hoïc, haõy tìm caùch

haõy cho moät lôøi giaûi

ñieàu cheá ra moät hay moät soá chaát naøo ñoù

• Neáu baøi toaùn khoâng giaûi ñöôïc thì caàn coù theâm

yeáu toá gì ñeå coù theå giaûi ñöôïc

Maïng suy dieãn vaø tính toaùn

Ñònh nghóa

• Moãi maïng tính toaùn laø moät maïng ngöõ nghóa chöùa caùc bieán vaø nhöõng quan heä coù theå caøi ñaët vaø söû duïng ñöôïc cho vieäc tính toaù

Moâ hình maïng suy dieãn vaø tính toaùn laø moät söï khaùi quaùt cho moät daïng tri thöùc duøng cho vieäc bieåu dieãn tri thöùc vaø thieát keá caùc chöông trình giaûi toaùn töï ñoäng,

Quan heä

f : u → v

• Cho M = {x1,x2,...,xm

} laø moät taäp hôïp caùc bieán coù theå laáy giaù trò trong caùc mieàn xaùc ñònh töông öùng D1,D2,...,Dm

ta coù theå tính ñöôïc giaù trò cuûa caùc bieán thuoäc khi bieát ñöôïc giaù trò cuûa caùc bieán thuoäc u

u ∩ v = ∅

• Ñoái vôùi moãi quan heä R ⊆ D1xD2x...xDm treân caùc taäp hôïp D1,D2,...,Dm ta noùi raèng quan heä naày lieân keát caùc bieán x1,x2,...,xm (cid:198)R(x1,x2,...,xm) hay R(x)

fR,u,v : Du

→ Dv

Quan heä khoâng ñoái xöùngcoù haïng k (k>0)

Quan heä ñoái xöùngcoù haïng k (k>0)

• tính ñöôïc k bieán baát kyø töø m-k bieán kia

Ví duï

• quan heä f giöõ a nöûa chu vi p vôùi caùc ñoä daøi

cuûa 3 caïnh a, b, c:

Quan heä f giöõa 3 goùc A, B, C trong tam giaùc ABC cho bôûi heä thöùc: A+B+C = 180 (ñôn vò: ñoä)

quan heä ñoái xöùng coù haïng 1

Maïng tính toaùn

Ví duï

• bao goàm moät taäp hôïp caùc bieán M vaø moät taäp hôïp caùc quan heä (tính toaùn) F treân caùc bieán

• Trong ví duï 1 ôû treân, ta coù M(f) = {A,B,C}. • Trong ví duï 2 ôû treân, ta coù M(f) = {a,b,c,p}.

• Kyù hieäu MTT:

}

– M = {x1,x2,...,xn } – F = {f1,f2,...,fm – ta kyù hieäu M(f) laø taäp caùc bieán coù lieân heä trong

quan heä f

Ví duï

Vi duï (tt)

• Maïng tính toaùn cho moät hình chöõ nhaät

M = {b1, b2, d, s, p}, F = {f1, f2, f3

– b1, b2 : hai caïnh cuûa hình chöõ nhaät; – d : ñöôøng cheùo cuûa hình chöõ nhaät; – s : dieän tích cuûa hình chöõ nhaät; – p : chu vi cuûa hình chöõ nhaät;

• coù caùc quan heä sau ñaây :

– f1 : – f2 : – f3 :

s = b1 * b2; p = 2 * b1 + 2 * b2; 2 + b2 d2 = b1

Vaán ñeà treân maïng tính toaùn

• Cho moät maïng tính toaùn (M,F)

• Coù theå xaùc ñònh ñöôïc taäp B töø taäp A nhôø caùc

quan heä trong F hay khoâng?

– M laø taäp caùc bieán – F laø taäp caùc quan heä

• Giaû söû coù moät taäp bieán A ⊆ M ñaõ ñöôïc xaùc

• Neáu coù theå xaùc ñònh ñöôïc B töø A thì quaù trình tính toaùn giaù trò cuûa caùc bieán thuoäc B nhö theá naøo?

ñònh

• B laø moät taäp bieán baát kyø trong M

• Trong tröôøng hôïp khoâng theå xaùc ñònh ñöôïc B, thì caàn cho theâm ñieàu kieän gì ñeå coù theå xaùc ñònh ñöôïc B.

Ñònh nghóa

Vaán ñeà treân maïng tính toaùn

• Baøi toaùn xaùc ñònh B töø A treân maïng tính toaùn

• Baøi toaùn A → B ñöôïc goïi laø giaûi ñöôïc khi coù theå tính toaùn ñöôïc giaù trò caùc bieán thuoäc B xuaát phaùt töø giaû thieát A

(M,F) ñöôïc vieát döôùi daïng : A(cid:198)B

Hoaëc A(cid:198)b

• Ta noùi raèng moät daõy caùc quan heä {f1, f2, ..., } ⊆ F laø moät lôøi giaûi cuûa baøi toaùn A → B

fk neáu nhö ta laàn löôït aùp duïng caùc quan heä fi (i=1,...,k) xuaát phaùt töø giaû thieát A thì seõ tính ñöôïc caùc bieán thuoäc B.

Ñònh nghóa

• Cho D = {f1, f2, ..., fk} laø moät daõy quan heä

• Lôøi giaûi toát neáu khoâng theå boû bôùt moät soá

cuûa maïng tính toaùn (M,F)

böôùc tính toaùn trong quaù trình giaûi

• Lôøi giaûi toái öu khi noù coù soá böôùc tính toaùn ít

nhaát

• A laø moät taäp con cuûa M • D laø aùp duïng ñöôïc treân taäp A khi vaø chæ khi ta coù theå laàn löôït aùp duïng ñöôïc caùc quan heä f1, f2, ..., fk xuaát phaùt töø giaû thieát A

Thuaät toaùn tính D(A)

Ñònh nghóa

Nhaäp : Maïng tính toaùn (M,F),

∪ M(f1), . . . ,

A ⊆ M, daõy caùc quan heä D = {f1, f2, ..., fm Xuaát : D(A).

• A0 = A, A1 = A0 ∪ M(fk) • Ak = Ak-1 • kyù hieäu Ak laø D(A) (cid:206)A →D(A) : coù D laø lôøi giaûi

Thuaät toaùn : 1. A’ ← A; 2. for i=1 to m do

D(A) laø söï môû roäng cuûa taäp A nhôø aùp duïng

if fi aùp duïng ñöôïc treân A’ then A’ ← A’ ∪ M(fi);

daõy quan heä D

3. D(A) ← A’

Ñònh nghóa

• Bao ñoùng cuûa A laø söï môû roäng toái ña cuûa A treân moâ

• baøi toaùn A → B laø giaûi ñöôïc khi vaø chæ khi B ⊆ A

hình (M,F). Kyù hieäu:

• Baøi toaùn A → B laø giaûi ñöôïc khi vaø chæ khi caùc baøi

toaùn A → b laø giaûi ñöôïc vôùi moïi b ∈ B

• Neáu A → B vaø B → C laø caùc baøi toaùn giaûi ñöôïc thì

baøi toaùn A → C cuõng giaûi ñöôïc

• Neáu baøi toaùn A → B laø giaûi ñöôïc vaø B’ laø moät taäp con cuûa B thì A → B’ cuõng laø moät baøi toaùn giaûi ñöôïc

Tìm moät lôøi giaûi cho baøi toaùn A → B

• Nhaäp :

Tìm bao ñoùng cuûa taäp A ⊆ M Maïng tính toaùn (M,F), A ⊆ M. A

Nhaäp : Maïng tính toaùn (M,F),

• Xuaát : 1. B ← A; 2. Repeat

B1 ← B; for f ∈ F do

taäp giaû thieát A ⊆ M, taäp bieán caàn tính B ⊆ M. Xuaát : lôøi giaûi cho baøi toaùn A → B

if ( f aùp duïng ñöôïc treân B ) then

begin

B ← B ∪ M(f); F ← F \ {f}; end;

Until B = B1; A 3. ← B;

1. Solution ← empty; // Solution laø daõy caùc

quan heä seõ aùp duïng

3. Repeat

Aold ← A; Choïn ra moät f ∈ F chöa xem xeùt; while not Solution_found and (choïn ñöôïc f) do

begin if ( f söû duïng ñöôïc treân A ) then

2. if B ⊆ A then begin

begin

A ← A ∪ M(f); Solution ← Solution ∪ {f};

Solution_found ← true; goto 4;

end;

end

else

Solution_found ← false;

if B ⊆ A then Solution_found ← true; Choïn ra moät f ∈ F chöa xem xeùt; { while } end;

Tìm moät lôøi giaûi toát töø moät lôøi giaûi ñaõ bieát

Nhaäp : Maïng suy dieãn (M,F),

lôøi giaûi D={f1, f2, ..., fm} cuûa baøi toaùn A→ B.

4. if not Solution_found then

Baøi toaùn khoâng coù lôøi giaûi;

Xuaát : lôøi giaûi toát cho baøi toaùn A → B Thuaät toaùn :

Until Solution_found or (A = Aold);

else

Solution laø moät lôøi giaûi

1. D ← {f1, f2, ..., fm}; 2.

for i=m downto 1 do

if D \ {fi} laø moät lôøi giaûi then

D ← D \ {fi};

3. D laø moät lôøi giaûi toát.

Thuaät toaùn kieåm tra lôøi giaûi cho baøi toaùn

1. for i=1 to m do

if (fi aùp duïng ñöôïc treân A) then

A ← A ∪ M(fi);

Nhaäp : Maïng suy dieãn (M,F), baøi toaùn A→ B, daõy caùc quan heä {f1, f2, ..., fm}.

2. if A ⊇ B then

} laø lôøi giaûi

{f1, f2, ..., fm

Xuaát : thoâng tin cho bieát {f1, f2, ..., fm} coù phaûi laø lôøi giaûi cuûa baøi toaùn A→ B hay khoâng.

else

} khoâng laø lôøi giaûi;

{f1, f2, ..., fm

Ví duï

Ví duï Maïng suy dieãn cuûa tam giaùc

• Cho tam giaùc ABC coù caïnh a vaø 2 goùc keà laø

– M = {a, b, c, α, β, γ, ha, hb, hc, S, p, R, r, ...} – Caùc quan heä suy dieãn :

β, γ ñöôïc cho tröôùc.

• Haõy xaùc ñònh (hay suy ra) S cuûa tam giaùc

Ví duï

• A = {a, β, γ} • B = {S}

böôùc 1: böôùc 2: böôùc 3:

Xaùc ñònh α Xaùc ñònh b Xaùc ñònh S

(aùp duïng f1). (aùp duïng f2). (aùp duïng f9).

MAÏNG SUY DIEÃN COÙ TROÏNG SOÁ VAØ LÔØI GIAÛI TOÁI ÖU

(1) a + b + c = 2*p, vaø (2) a2 = b2 + c2 - 2*b*c*cos(A)

MAÏNG SUY DIEÃN COÙ TROÏNG SOÁ VAØ LÔØI GIAÛI TOÁI ÖU

maïng suy dieãn coù troïng soá laø moät moâ hình (A,

• r : u ⇒ v • u: phaàn giaû thieát cuûa luaät r - hypothesis(r). • v : phaàn keát luaän cuûa luaät r - goal(r). • attr(r) = hypothesis(r) ∪ goal(r) : taäp hôïp caùc

D, w) bao goàm: – moät taäp hôïp caùc thuoäc tính A, – moät taäp hôïp caùc luaät suy dieãn D, vaø – moät haøm troïng soá döông w : D → R+

thuoäc tính trong luaät r

• Moãi luaät daãn r thuoäc D coù daïng r : u ⇒ v u vaø v laø caùc taäp hôïp con khaùc roãng vaø rôøi nhau cuûa A

Ví dụ

• A = {A, B, C, a, b, c, p, S, ha, hb, hc, ...}. • D = {

f1: A + B + C = 180; f2: a/sin(A) = b/sin(B); f3: b/sin(B) = c/sin(C); f4: a/sin(A) = c/sin(C); f5: 2*p = a + b + c; f6: S = a*ha/2; f7: S = b * hb / 2; f8: S = c*hc/2; f9: S = sqrt(p*(p-a)*(p-b)*(p-c)); f10: ha =

b*sin(C);

w(f1) = 2; w(f2) = w(f3) = w(f4) = 2*c2 + 2; w(f5) = 3; w(f6) = w(f7) = w(f8) = 2; w(f9) = c1 + 6; w(f10) = w(f11) = w(f12) = c2 + 1;

f11: hb = a*sin(C); f12: hc =

b*sin(A)

(A,D,w) laø moät maïng suy dieãn coù troïng soá

} +, -, * vaø / ñöôïc ñaët cho troïng soá laø 1 caên baäc 2 coù troïng soá laø moät haèng soá döông c1 (c1>>1), haøm löôïng giaùc coù troïng soá laø moät haèng soá döông c2(c2>>1)

Lôøi giaûi toái öu

• Cho moät baøi toaùn A → B. Daõy caùc luaät suy dieãn S ñöôïc goïi laø moät lôøi giaûi toái öu khi: – S laø moät lôøi giaûi cuûa baøi toaùn A → B. – w(S) = min {w(S’) | S’ laø moät lôøi giaûi cuûa baøi

• (A, D, w) laø moät MSDT • S = {f1,...,fk} laø moät daõy caùc luaät suy dieãn • w(S) = w(f1) + w(f2) + ... + w(fk). • Ta goïi w(S) laø troïng soá cuûa S.

toaùn A → B }

Böôùc 1: Tìm moät lôøi giaûi • Khi G ⊄ H ta thöïc hieän quaù trình laëp cho caùc

• Xeùt baøi toaùn H → G treân moät MSDT (A, D, w), vôùi H vaø G laø caùc taäp con cuûa taäp thuoäc tính A.

• Thuaät toaùn

böôùc döôùi ñaây: – Böôùc 1.1: Tìm luaät r ∈ D coù theå aùp duïng ñöôïc ñeå suy ra caùc thuoäc tính môùi: hypothesis(r) bao haøm trong H nhöng goal(r) khoâng baøo haøm trong H. – Böôùc 1.2: Neáu vieäc tìm kieám ôû böôùc 1.1 thaát baïi:

baøi toaùn khoâng coù lôøi giaûi.

– Böôùc 1: Tìm moät lôøi giaûi – Böôùc 2: Ruùt goïn lôøi giaûi

– Böôùc 1.3: Ngöôïc laïi thì boå sung theâm goal(r) vaøo H vaø ghi nhaän r vaøo danh saùch caùc luaät ñaõ ñöôïc aùp duïng.

Tìm lôøi giaûi toái öu

Böôùc 2: Ruùt goïn lôøi giaûi

Böôùc 2.1: G' ← G \ H; Böôùc 2.2: for k:=p downto 1 do

if (goal(rk) ∉ G') then

Loaïi rk ra khoûi danh saùch S

else

G' ← (G' \ goal(rk)) ∪ (hypothesis(rk) \ H)

Khoâng gian traïng thaùi cuûa baøi toaùn

• baøi toaùn H → G treân moät MSDT (A, D, w) • r laø moät caïnh noái töø ñænh H ñeán ñænh H’ :

• Moät daõy S goàm caùc luaät laø moät lôøi giaûi cuûa baøi toaùn H → G khi vaø chæ khi S laø moät loä trình treân ñoà thò Graph(H→G) noái töø H ñeán S(H) vaø S(H) ⊃ G

– r coù theå aùp duïng treân H – H’ = H ∪ goal(r)

• Ñoä daøi cuûa moät loä trình S treân ñoà thò

• troïng soá cuûa caïnh r (töùc laø moät luaät suy dieãn)

laø w(r)

Graph(H→G) laø w(S), troïng soá cuûa danh saùch luaät S treân MSDT (A, D, w) • Ñoái vôùi moãi ñænh N treân ñoà thò:

(cid:206)Graph(H→G)

h(N) = min {w(r) | hypothesis(r) ⊂ N}

Böôùc 2: Thöïc hieän quaù trình laëp ñeå tìm lôøi giaûi toái öu

• Böôùc 1: Khôûi taïo traïng thaùi xuaát phaùt.

– Open ← {H}; // danh saùch ñænh môû ban ñaàu chæ

• While (Open ≠ {}) do • Begin

coù ñænh xuaát phaùt

– Böôùc 2.1: Choïn moät ñænh N trong Open vôùi öôùc tính

ñöôøng ñi f nhoû nhaát.

– Böôùc 2.2: Chuyeån N töø danh saùch Open sang danh

// ñoä daøi loä trình ñeán H laø 0

saùch Close

– Close ← {}; // danh saùch ñænh ñoùng – g(H) ← 0; – f(H) ← h(H); // ñoä daøi loä trình öôùc tính töø H ñeán

– Böôùc 2.3: if (N laø moät muïc tieâu) then

muïc tieâu laø h(H)

Found ← true; Break;

// Keát thuùc quaù trình laëp

– found ← false;

// bieán kieåm tra quaù trình tìm

– Böôùc 2.4 else // N khoâng laø moät muïc tieâu

lôøi giaû

Begin Duyeät qua caùc ñænh keá S cuûa N maø S ∉ Close, öùng vôùi moãi S ta xeùt caùc tröôøng hôïp sau: S ∉ Open:

Böôùc 3: Kieåm tra keát quaû vieäc tìm kieám.

If Found then Keát quaû laø tìm ñöôïc lôøi giaûi

toái öu vaø thieát laäp lôøi giaûi

Tính g(S) = g(N) + w(r); f(S) = g(S) + h(S); Boå sung S vao Open; S ∈ Open:

Else Keát quaû laø baøi toaùn khoâng coù lôøi giaûi

If g(N) + w(r) < g(S) then Begin

End // Keát thuùc voøng laëp while

100

g(S) ← g(N) + w(r); f(S) ← g(S) + h(S); Caäp nhaät thoâng tin veà ñænh keá tröôùc cuûa S treân loä trình; end End

Ví duï

• A = {A, B, C, a, b, c, p, S, ha, hb, hc}

w(f6) = w(f7) = w(f8) = 2;

• w(f1) = 2; • w(f2) = w(f3) = w(f4) = 2*c2 + 2; • w(f5) = 3; • w(f9) = c1 + 6; • w(f10) = w(f11) = w(f12) = c2 + 1.

101

102

Tìm moät söï thu goïn giaû thieát cuûa baøi toaùn

Ví duï

• Nhaäp : Maïng suy dieãn (A, D),

Baøi toaùn H→ G giaûi ñöôïc

• Xeùt baøi toaùn H → G vôùi

H = {a, b, B} vaø G = {S}.

Xuaát : taäp giaû thieát môùi H’ ⊆ H toái tieåu. Repeat

• S = {f2, f1, f3, f5, f9} – w(S) = 4*c2 + c1 + 15

• S’ = {f2, f1, f10, f6} – w(S’) = 3*c2 + 7

H’ ← H; for x ∈ H do if H - {x} → G giaûi ñöôïc then H ← H - {x};

Until H = H’;

103

104

Ví duï:

MAÏNG SUY DIEÃN-TÍNH TOAÙN

• Kieán thöùc veà moät tam giaùc coù theå ñöôïc bieåu dieãn bôûi

moät maïng suy dieãn tính toaùn (A, D, F, R) : – A = {A, B, C, a, b, c, R, S, p, ...} – D = {r1: A, B ⇒ C; r2: A, C ⇒ B; r3: B, C ⇒ A;

• Taäp hôïp A goàm caùc thuoäc tính • Taäp hôïp D goàm caùc luaät suy dieãn (hay caùc

quan heä suy dieãn) treân caùc thuoäc tính

• Taäp hôïp F goàm caùc coâng thöùc tính toaùn hay caùc thuû tuïc tính toaùn töông öùng vôùi caùc luaät suy dieãn (f: D(cid:198)F)

r4: A, a ⇒ R; r5: A, R ⇒ a; r6: R, a ⇒ A; r7: A, b, c ⇒ a; ...}

• Taäp hôïp R goàm moät soá qui taéc hay ñieàu kieän

– F = {f1: C = π-A-B; f2: B = π-A-C; f3: A = π-B-C; f4: R = a/(2.sin(A)); f5: a = 2.R.sin(A); f6: A = arcsin(a/(2.R)); f7: a= b2+c2-2.b.c.cos(A); ...}

raøng buoäc treân caùc thuoäc tính

105

106

– R = {a+b > c; a+c > b; b+c > a; a > b ⇔ A > B; a = b ⇔ A = B; ...}