Bài toán ghép tranh sử dụng giải thuật A và tìm kiếm Heuristics
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 (836.37 KB, 25 trang )
LỜI NÓI ĐẦU
!"#$%&'()*+,-./*(0
12!##)3-#456744&
89()*+,-:;:(<:9=>-6 -./#
45:(<*+,9()6 ?4#45
(@/1:A@9()6B5"*+,
-4".#-4"&4=>-
C#4.C5D-:;.(D6
+,-:(<-9*C&88:
E6B/D()*+,-:(</.
*+,-C5.F&:886 *+.
4=*4).(<9()*+,--
8:+24*6
G=.@.@)$:HI'7#JKB9&HB%
B4 "&(@L%!I'7# ' 2" K4I':1*#.PGS.TS
Đỗ Văn Nhơn:;%4&M:N:+(@+5+
.46
B1?:;>O.C&PQ(-R%5*'+
*2D-:;!&:"S4+.4.:+0#
8*6
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z
7^7_` IaTbc7TUbd7
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] e
MỤC LỤC
fgb7hbLij666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666Z
BkIfkI666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666e
Ph n 1. TRI TH C VÀ CÁC PH NG PHÁP BI U DI N TRI TH Cầ Ứ ƯƠ Ể Ễ Ứ 4
1.1 Khái ni m tri th cệ ứ 4
1.2 Khái ni m v bi u di n tri th cệ ề ể ễ ứ 4
1.3 M t s ph ng pháp bi u di n tri th cộ ố ươ ể ễ ứ 5
1.3.1 Bi u di n tri th c s d ng h lu t d nể ễ ứ ử ụ ệ ậ ẫ 5
1.3.1.1 C ch suy lu n trên các lu t sinhơ ế ậ ậ 6
1.3.1.2 u và nh c đi m c a bi u di n tri th c b ng lu tƯ ượ ể ủ ể ễ ứ ằ ậ 6
1.3.2 Bi u di n tri th c s d ng m ng ng ngh aể ễ ứ ử ụ ạ ữ ĩ 7
1.3.3 Bi u di n tri th c b ng Frameể ễ ứ ằ 8
1.3.4 Bi u di n tri th c b ng Scriptể ễ ứ ằ 8
Ph n 2. CHI N L C TÌM KI M HEURISTICSầ Ế ƯỢ Ế 10
2.1 Khái ni m Heuristicsệ 10
2.2 Heuristics dùng đ làm gì?ể 10
2.3 c tính thu t gi i HeuristicsĐặ ậ ả 11
2.4 Nguyên lý thu t gi i Heuristicsậ ả 11
2.4.1 Nguyên lý vét c n thông minh:ạ 11
2.4.2 Nguyên lý tham lam (Greedy) 11
2.4.3 Nguyên lý th tứ ự 12
2.4.4 Hàm Heuristic 13
2.5 Các ph ng pháp tìm ki m Heuristicsươ ế 13
2.5.1 C u trúc chung c a bài toán tìm ki mấ ủ ế 13
2.5.2 Các ph ng pháp tìm ki m Heuristicsươ ế 14
Ph n 3. GI I THU T A* VÀ BÀI TOÁN GHÉP TRANHầ Ả Ậ 15
3.1 Hàm đánh giá và ph ng pháp đánh giá trong chi n l c tìm ki m Heuristicsươ ế ượ ế 15
3.1.1 Hàm đánh giá 15
3.1.2 Các ph ng pháp đánh giá trong chi n l c tìm ki m Heuristicsươ ế ượ ế 18
3.2 Gi i thi u thu t gi i A*ớ ệ ậ ả 18
3.3 Bài toán ghép tranh 19
3.4 Cài đ t thu t toánặ ậ 21
3.4.1 Giao di n ch ng trìnhệ ươ 21
3.4.2 Xây d ng hàm đánh giáự 22
3.4.3 Xây d ng gi i thu t A*ự ả ậ 23
23
lbfbmj BHcn66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666eo
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] [
Phần 1. TRI THỨC VÀ CÁC PHƯƠNG PHÁP BIỂU DIỄN TRI
THỨC
1.1 Khái niệm tri thức
-'8:pq"=*3-./#r(<6 4
5<=.s:(<t-u*v4"5PQ:(:p
q9--P6
H#W -.C+*9/.qCS>:96
fqCWB9S:9:(<M!6
-W (@*A#&.%C#&.6
Ví dụW
o H-94!Ew:*#.-6
o /84P?0'-.52D
4P.-6
o %>MD.#(@?.?0
=.s)*5>M.-6
I%-W
• -'W#&:P(<)*6
• ->MW#>M&2#&:P(<-<&666
• -SW.F&S=.s&.(<&x
• -W-9%-M6
1.2 Khái niệm về biểu diễn tri thức
+,-yHz.{|.C,:%+#S-
(0D%"<:+8+}-/#)3-S#P6
!*++-./();8-4"
8+=.":(<M6I~(D.#89:+*+,-
4"6 45!/()?<:+:(.54
"6
I'#*+,-:)(W
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] o
+ I>MD.#)*WV;4&<&Fx
+ I>MD.#r(<WE=&:<6
+ I'!W:Ap&$4x
+ I':P(<6
+ I'D:1-6
Ví dụWH-9/DK#*8+:(<*+
,AW
+ B/<*C&O*:%#/4PSD
(9&9/6
+ B/<'-.52:"54PSD
6
1.3 Một số phương pháp biểu diễn tri thức
1.3.1 Biểu diễn tri thức sử dụng hệ luật dẫn
J()*+,-*v.:(<*3Newell Simon
.M':PQ=$4C/#*}26L$4./+
*+,-8>M6•(3)*.-8+:(<>M*v/1
điều kiện – hành độngW€7•jđiều kiện=4 ‚hành động ƒ:(<€6I„
%W7•j:…'.:† ‚*%':(<:„&7•j4":;3
'3:/:(< ‚+A:#&x
744&.:;35}*:(</;9#
P"#$%6f8+./'':+24
>:9C4+$">:949P6 (@<4&
.:(<?(.D‡Fy48+'‡|(>D":+
<M24:p2&r:8.'6
B/"..8+:(<?:+*Q(0SD456
4&.'‡:)K./+*+,-4"
./+*,,S(@6
L+*,,/.&(@(@‡ˆK"W
yZ| C#‰y‰|
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Š
‰‹Œ•
Z
&•
e
&666•
Ž
ye| 24Q{y{.|5C#%(W
•
Z
∧•
e
∧666∧•→2
:8&•&2:9/‰6
1.3.1.1 Cơ chế suy luận trên các luật sinh
1.3.1.1.1 Suy diễn tiến
f24.=>r/PC#*:K&=:pC#8
+:(<€€rC#46
1.3.1.1.2 Suy diễn lùi
f24.(<=>r/PC#*:K&C
#:;€€C#46B/"(@1C.=>r
%S4"&w:=4":;*p†83:$6
Ví dụ:
C#W
• •-.€†€4€%:/*(@€
• †6
• f†6
• %:…}-.€Q€1€€
• I8$:!}-6
• %:…€=€1€0:†€
• H':(<4"6
L#4"€8€4€'€
1.3.1.2 Ưu và nhược điểm của biểu diễn tri thức bằng luật
1.3.1.2.1 Ưu điểm:
+,-*v.:1*#D#DP#PK
:(D:/CDC#8+2:(<6788D(
:+"4:$4W
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] •
• I.>,+58+,?:+:}0(@?
y8./D%C5S'D|6
• I8+,=$4C:(<)4."r.6
• U##‡*#P.():P,6
• I8+,:+"<.@6
• I.(@"/6
1.3.1.2.2 Nhược điểm:
I--%:'.M:R†29y|.6L94ƒ
.49>:9.52:P:/.F2p#P6
P5>4&(@=$4C#P"#$%".
)>()y,+&,:1|5!(@!:+*+,
-*v.?8()"<)‘L$4.(<:+
"S2S(@6
I)3-..0ƒ.0%ES()
:9+679#P18E#:#C5.
~(18E4.5.6
1.3.2 Biểu diễn tri thức sử dụng mạng ngữ nghĩa
B%Dq./()*+,-:K5~.()
,+>:P0M6J()4ƒ*+,-(0%/
:Ap&:8:‡.:P(<y#|R*P2#D
:P(<y#|46
B%Dqyz|8%:ApAM&
:8W
• IM+##&:P(<6
• I,#2#D:P(<6
VC5%Dq*-/C2M
=.s(W5’*0#4:P(<&'6
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] “
7=WB'r(<2&+'
-+)6
1.3.3 Biểu diễn tri thức bằng Frame
Frame ./>MD.#-:C>D-.52:/
:P(<+:86‰8.5#1ƒ:#(0:P(<yC
•.APS.”(0:P(<|67(<.%0()*+
,-:;:(<:9:&•€:88€*//:P(<&P1
/>:9-%/C+4>8>M6B/•*
8/P.(<():P.0-9/:P(<&C#&p"&P1
D4P6V:8&•8+M'/:P(<6
V(0/"%:8&(@8+=()*+,-
*v•".APS'D.(0:P(<6•(3S
()4.€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!€6I~4&s(3"S•y4S().
(0:P(<|.*+,/-&ƒ€Q…€D(@1
5-46I„%('#9D&ƒQ…cách
tính &#"6
1.3.4 Biểu diễn tri thức bằng Script
X./*+,-()C(•(4:1/
:P(<&8'/OC#6L+'OC#&/;4
.-'9(@&:P(<:/.52:C#:86
4>MS.>?4*&(
/(@*AKW
• L9#y4|W'DP1:9#K
:(<†;(0C#8+,6
• {.y:8|W.D(@8.526
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] ]
• JyP|W.>D:P(<:(<OC#
ƒ,6
• Xy P|W.OC#CC,6
• {.yH2|W%S{.:;=6
• y5*|W'/*+y1(@<:1*#|8+=4
:%6
X>D#C::9ƒ=4:DP=
:p6 "DP(,&R4"C
::(<#ƒ=4=4:P0@:+674""
%/&(@?8+:1$†#P8+4:(<D$
.@"='K(@?>59'y/P
(@<8+'K5'|6V:8&~P(•&./
%*+,-():PD8'"=D
P€w€(@FC#O41:;Q*Q"=6
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] •
Phần 2. CHIẾN LƯỢC TÌM KIẾM HEURISTICS
2.1 Khái niệm Heuristics
TJ.4:pq.tC5-9()
2Q#uyJ.4Z•oŠ|67q48+=>rP
4f%S:/rq.t'#u6H4†*A
Q/.>4~#*v&':;..5tG‘u8qt ':;
>48‘u6 '%&..?:+!D
89E>F:/>:(<6
D:(<‰*‰.:pq(Wt.2
Q&()&.(<&–4():8v.P
.(<.@'*C.0u6
B/P.%Dtu:+‡-24
*('+:py7z &Xz&XEZ••[|6
‡./†:-'9*(0ƒ:(<!
?#24/>:9678(@C#1C6U
D'%5M"8E:(0
"==S'%3D:%=)68
+F:/‡:%:(<KP(1
':(<*>—6
2.2 Heuristics dùng để làm gì?
f/(0.(<9EF:.@6
fD-:(<M‡rD#&tCuS(@6I8
+.D-t:Mu4tu6
fDz.t(@:Mu6
D*5'%&8e(@<K:
W
• U>:98+'8#"=#:9'*+
1ƒ4D.#:+„:p26
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z\
• U>:98#"=("}":+#.2
.0y#2S#*?O}<|6
2.3 Đặc tính thuật giải Heuristics
• .@P6
• @>:(<6
• C5K~04q:/S(@6
2.4 Nguyên lý thuật giải Heuristics
2.4.1 Nguyên lý vét cạn thông minh:
/*:8&'.0&(@0
%.%'1C#/+R:1*#C:1?S
*:+856
2.4.2 Nguyên lý tham lam (Greedy)
f>45wP(y5%|S*:+.5w!.C
:/%*/Sr*(0y4r:%|2.@
6
Bài toánW
˜ ;4//(@:2:+6
˜ BO:+:2/.K39:+=>6
˜ X}9:%:(@K:.Q>6
˜ Tv8:(@PCD:+*>—
LApS*W
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] ZZ
f@T4W
:(<WZo
P(WZ\yZ™še™šŠ™šo™š[™šZ|
2.4.3 Nguyên lý thứ tự
C#:/C5/>M-C<.sS'v
8:%:(</.@P6
Bài toánW
˜ B/'48[4WB
Z
&B
e
&B
[
•'#0@C#()-
.W
Z
‹e&
e
‹Š&
[
‹]&
o
‹Z&
Š
‹Š&
•
‹Z6
;4:(/()$'•'#50>6
B/.@'PW
IP(W
˜ XQ='#-CK9@6
˜ fK.(<Q=#-C:84R9@>
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Ze
2.4.4 Hàm Heuristic
#=$4C& (@(@?
6L8.:'&pS/%#%S
*%O*(067@p4&8+!:(<:/():P
<.sr*(0S6
2.5 Các phương pháp tìm kiếm Heuristics
2.5.1 Cấu trúc chung của bài toán tìm kiếm
L+#.<#*4&;4M@:+.ˆ)€:P(<€
2$SM46B/>&9>:9™*-
%:98%€:(@::Ap€48/-).€=>
r/:‡S/:Ap&:(@:#2>:/:‡:8€6B/
*+(@1S%*4.W
I(0% \ T;4=$4CO% \& Z& e&666& ™
Z& ‹ TW
†;/:9#(0y(@.†>|6
:8W
• /<Xy!.'%Y|*A>
%8+8S*6
• Iy
™Z
&
|.":+*:}r%
™Z
%
6Vq5&r
/%
89:+*:}%
›Z
6H8:/
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z[
*:}+r
™Z
ƒ?D(0:y0s89C.C
!|6
2.5.2 Các phương pháp tìm kiếm Heuristics
• 9$9/
• .:A
• (5P(
•
• H
•
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Zo
Phần 3. GIẢI THUẬT A* VÀ BÀI TOÁN GHÉP TRANH
3.1 Hàm đánh giá và phương pháp đánh giá trong chiến lược tìm kiếm Heuristics
3.1.1 Hàm đánh giá
.(<p.(0.(<"}:+:r%#%:
%.6I)3:+=:p.(<p.C-’#
:(<6.(<p2:MyKC|4y=pC|ƒF
:2:(<P4=>6
I'‡:/:.(<&R(3
24:p0.(<:9+y(0'*=
.s%|6LP0D*"#-%&PE8+.00-
'+8/4"K#:%:>4:-}6V4&S4#
+'+>:(<6 K.0*-:p.s
.&PEK=3.5'%6U#.C!/(0:P>
R):R†Z\
o\
E&":P
0)@&PENZ\
Ze\
6B/=.sPD(@<4.
M!(06
U>:92!.3O&M*.'%O%
:+-C(5:w426 '(@Q0O
%S*0/P:y/:|:8:+:-:/K
:"S86
B/œ:(<.<.s8:
E:+.ˆEP)ER.%67D":+9
:.(0.(<:(@*4r/:‡0:‡:"
*=:p:(@:Q>&4:(0.(<-:/2
!S2$@O@C5}<!PSMx
9>:9&8+#&-SM 9>:9
:8:+:%S>:96U0O%&ƒ=:p/pP
y|&P4:tCK:"uS%6y|:(<!.:6
IMƒ::+(0FC6 2&
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] ZŠ
%O*(0ƒ!%:++.%8p:†
>&%4:(<=.%89-–>:0:"6
J()#.()8:
:6 2&%O*(0ƒ!%.%
89-–F0:"9>6
I:%)*:+24>:9*v#(W
™+,"<%4+%6
™_$4C:6
™ .(<!%:++3O*(06
T20'5'*8
19%=>#8?&(@<4&%.
KPS$4>.%P>6L+::K4:S'
(@<(4&/::(<.AK:8.W
•y|‹y|›y|
U0W y|.%O%
y|.":r%P:%
U4&2&%:88•y|.†>:8.%P
>:(<!:+,6
#&::8RC—2!6IM
8=$4C:(<:C::M%0
#267:'"=&88+F:.#(0F:
#26
H8eM?8p—!:%:5*vM8r
M*Q:K:M:8Q)ƒ:(<!(0(4M48p
P)648.(<pMK).P)
—!:..*v6
H'8wC#:/.(<p6fsW
• H'8>M.(<p6
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z•
• ":M’4:}.5r>:9+6
• ":M’4:}rP+/>:9
I8+?9.(<PK.(<
p9.(<p6
U#!.C.8E8sq24:p:P0P:/S
6
_*]™••.0T.(W
1 2 3
8 4
7 6 5
8[:*5.W
˜ Heuristic 1W }Pp"6
˜ Heuristic 2W }p"Sr6
˜ Heuristic 3WXP1:}p"$e
2 8 3
1 6 4
7 5
5 6 0
2 8 3
1 4
7 6 5
3 4 0
2 8 3
1 6 4
7 5
5 6 0
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z“
3.1.2 Các phương pháp đánh giá trong chiến lược tìm kiếm Heuristics
V%}2S:W•y|‹•y
Z
&x&
|&3:$4-0OE
&:•/p•y
Z
&x&
|&."/pS
P
Z
&x&
:1(E6
(@<:)>W•y
Z
&x&
|‹žŸ
6
&Ÿ
.#P:1(
!PSP
6)D&•y
Z
&x&
|8+.:-*S*6H‹e&
8W•y
Z
&x&
|‹
Z
=
α
∑
›
Z
=
β
∑
e›
Z
=
γ
∑
B-:/#2S:?4/=:pP
Ÿ
&¡
&¢
6IP4.2:p.(<S459P
P:1(S86
£œA[>:92!W
™_:p>#:1
S*6
™U0OE&>#:1
:(<.(<8*3p
6_:p
•y|‹•y
Z
&x&
|C5*/PŸ&¡&¢x
™_:p+pS*/PŸ&¡&¢r*+6
3.2 Giới thiệu thuật giải A*
$.8"5'%C
:•&:(<:pq(W
•‹y|›y|6
Ty|W"CC:r:K:6
y|W"(0.(<:r:%:"6
H=:/%7*5%#.(D[p)*&&•:+:/
PS%:8&R.(D5'PW
• %S%7ys#.Iy7|W*%F:
%76 (@<89%F:7!Iy7|
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z]
":r%3:K:7.>>&q.Wy7|‹y7|
›y7&7|.>>6
• V%S7W4.(D%
7S7":7'27r%*:K.>>6
C>48+:(<"r/"IS%
:(<.(D6 :(<'(W
(0ZWL1nJG7‡-7
\
6L1y7
\
|‹y7
\
|‹•y7
\
|‹\6
L1IfnXG.<O6
(0eWf1.%*(0:1:9#r6
e6W7nJG7OW*'#&6
e6*W7(<.%&!7
nJG7•y7
|6
e6*6ZWf>47
†nJG7:(7
IfnXG6
e6*6eW77
".:"7
.
'*.@.7
6
e6*6[W77
'.7
.
6 %>%
S7
6T!/%4.7
6U0O7
&.*(0W
e6*6[6ZW "y7
|‹y7
|›y7
&7
|¤y7
|&•y7
|‹y7
|›y7
|6
e6*6[6eWL1Iy7
|‹7
6
f49C4:}p&•>%S
7
y3>>|:;:(<.(DIfnXGnJG76
e6*6[6oW77
(=>#nJG7.FIfnXGW
57
nJG7
3.3 Bài toán ghép tranh
CR)]P6B/:+A
e\*(0&#Pƒ[6
LP0'PS*&84+?4p"S8W
• H'P3D&8oE4+6
• H838&8eE4+&
• H835%&8[E4+6
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] Z•
L+*4&K/P6 8+e(0.(<W
• Z‹P.(<Pp"6
• e‹}PSP0p"5&.}
99!6
I!(0.(<‹}PSP0p"5&.
}99!6
U"!W
%:KyX| %:"yT.|
3 1 2
6 4 5
7 8
¥0&8W
3 1 2
6 4 5
7 8
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] e\
1 2
3 4 5
6 7 8
3 1 2
4 5
6 7 8
3 1 2
4 5
6 7 8
N4
N3
N1
N2
f=2, g=0, h=2
Open=ŒStartNodeŽ
Close=ŒŽ
Open=ŒN1,N2Ž
Close=ŒX7Ž
StartNode
f=4, g=1, h=3
f=2, g=1, h=1
Open=ŒN1,N3,N4Ž
Close=ŒX7&7eŽ
f=2, g=2, h=0
f=4, g=2, h=2
Goal
3.4 Cài đặt thuật toán
3.4.1 Giao diện chương trình
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] eZ
f>47[†n‹Œ7Z&7oŽ:(I.‹ŒX7&7e&7[Ž67[".T.6
3.4.2 Xây dựng hàm đánh giá
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] ee
3.4.3 Xây dựng giải thuật A*
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] e[
KẾT LUẬN
+.:;*4-
:+*6 '2#+5-:9
4&(@8}2)#-*+,-4
.24>:9C6B1?:;>PQ(R%91
@~(-5+.‡0#*]••.(3/
0(@<.0&JK9‡%45/.ˆ=.s:)y.|&(
#C:(<().5*/=.s:6
Xin chân thành cảm ơn Thầy PGS.TS Đỗ Văn Nhơn, giảng viên chuyên đề Biểu
diễn tri thức và suy luận, đã truyền đạt những kiến thức quý báu về biễu diễn tri thức trên
máy tính, các thuật toán để ứng dụng trong thực tiễn.
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] eo
TÀI LIỆU THAM KHẢO
¦Z§JTX6 XLOUE7)&Bài giảng Biểu diễn tri thức và ứng dụng6
¦e§UEHLOJM&Giáo trình Cơ sở tri thức&LI7 &e\Z\6
¦[§UEH&Giáo trình thuật toán, thuật giải và trí tuệ nhân tạo&LI7 6
¦o§W’’zzz6•6’ ’z’]™••.66
¦Š§Heuristic search W’’zzz66z66’¨.’[’*e©•©e©[6.
TUVWJTX6 XLOUE7) U W74,7!U!YIZ[\ZZZ] eŠ
