chapter10

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 (340.72 KB, 19 trang )

(1)<div class='page_container' data-page=1>

Ch

ươ

ng 10

L

Ậ

P K

Ế

HO

Ạ

CH

GV: Nguyễn Thị Trúc Viên
Email:

N

ộ

i dung

Các thành ph

ầ

n c

ủ

a 1 h

ệ

th

ố

ng l

ậ

p k

ế

ho

ạ

ch

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n

L

ậ

p k

ế

ho

ạ

ch phân c

ấ

p

Các h

ệ

th

ố

ng ph

ả

n

ứ

ng

</div>
(2)<div class='page_container' data-page=2>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 3

V

ớ

i bài toán

đơ

n gi

ả

n ( 8-puzzle):

–

Đề

ngh

ị

m

ộ

t t

ả đầ

y

đủ

cho tr

ạ

ng thái.

–

Gi

ả

i = tìm ki

ế

m trên KGTT nh

ư

A*, Best-First-Search, SA,

DFS, …

(

xem ch

ươ

ng v

ề

problem-solving).

V

ớ

i bài toán ph

ứ

c t

ạ

p:

–

K

ế

t h

ợ

p Problem-Solving + Knowledge Representation.

–

Dùng ph

ươ

ng pháp chia

để

tr

ị

.

Hai cách:

Chỉmô tảnhững phần thay đổi của bài toán.

Chia bài toán thành nhiều bài tốn nhỏ hơn, dễgiải hơn.

Ví d

ụ

m

ẫ

u – The blocks world

Mơ t

ả

:

–

Có m

ộ

t cái bàn ph

ẳ

ng, các kh

ố

i vng có n

ằ

m trên

đ

ó

đượ

c.

–

Có 1 s

ố

kh

ố

i vng, kích th

ướ

c b

ằ

ng nhau.

–

Có m

ộ

t cánh tay robot, có th

ể

làm cách hành

độ

ng:

UNSTACK(A,B)

STACK(A,B)
PICKUP(A,B)
PUTDOWN(A)

1 Sốpredecates khác:

ON(A,b)
ONTABLE(A)
CLEAR(A)
HOLDING(A)

</div>
(3)<div class='page_container' data-page=3>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 5

Ví d

ụ

m

ẫ

u – The blocks world (tt.)

M

ộ

t s

ố

ràng bu

ộ

c: (VD)

∃

X(HOLDING(X))

¬ARMEMTY

∀

X(ONTABLE(X)

¬

∃

Y(ON(X,Y)))

∀

X((¬

∃

Y(ON(Y,X)))

CLEAR(X))

…

Các thành ph

ầ

n c

ủ

a HT LKH

Ch

ọ

n l

ự

a lu

ậ

t

để

dùng:

–

Wildely used:

Tính DIFF = sựkhác nhau giữa CURRENT STATE & GOAL.
Chọn luật làm giảm DIFF trên.

Có thểdùng thêm những heuristic đểgiải quyết đụng độ.

–

Víd

ụ

:

Với : GOAL: have(tường màu trắng)

CUR-State: have(tường màu xanh)

Chọn luật chuyển đổi màu tường.

CUR-State: ¬have(tường)

</div>
(4)<div class='page_container' data-page=4>

Khoa Cơng Nghệ Thơng Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Môn: Trí tuệnhân tạo Side 7

Áp d

ụ

ng lu

ậ

t:

Trạng thái S0:

B
A

ON(A,B,S0) ^
ONTABLE(B,S0) ^
CLEAR(A,S0)

Luật (hành động): UNSTACK(X,Y)
[CLEAR(X,S) ^ ON(X,Y,S)] [

HOLIDING(X, DO(UNSTACK(X,Y) ,S)) ^
CLEAR(Y, DO(UNSTACK(X,Y) ,S))
]

Nghĩa là:

Với DO: Ởtrạng thái S, DO thực hiện hành động sẽcho ra trạng thái mới.
Cụthể:

- Khi X trống và X trên Y đúng trong trạng thái S thì:
- Thực hiện UNSTACK(X,Y) trên S sẽcho ra trạng thái mà:
HOLDING(X) và CLEAR(Y) là đúng.

Các thành ph

ầ

n c

ủ

a HT LKH (tt.)

Áp d

ụ

ng lu

ậ

t:

Trạng thái S0:

B
A

ON(A,B,S0) ^
ONTABLE(B,S0) ^
CLEAR(A,S0)

Thực hiện luật trên, cho ra S1 như sau:

HOLDING(A,S1) ^ CLEAR(B, S1) ^

?

Cần Frame Axioms, cụthể:

ONTABLE(Z,S) ONTABLE(Z, DO(UNSTACK(X,Y), S))
Và:

</div>
(5)<div class='page_container' data-page=5>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 9

Các thành ph

ầ

n c

ủ

a HT LKH (tt.)

Áp d

ụ

ng lu

ậ

t:

–

Frame axioms:

Ưu: cùng cơ chế(phân giải VT) tìm luật dùng, dùng luật.

Nhược: số lượng axioms lớn.
–

Gi

ả

i quy

ế

t:

Dùng STRIPS hay họcon của nó.
Ý tưởng:

Mỗi OPERATOR có:

- PRECODITION: các PRED nào phải true đểdùng được OP này.
- ADD list : các PRED sẽtrue.

- DELETE list: các PRED cũsẽfalse.

Các PRED ko có trong ADD, DELETE Un affected.

C

ầ

n 1

cơ chế

khác h

ơ

n phân gi

ả

i VT

để

làm vi

ệ

c.

Các thành ph

ầ

n c

ủ

a HT LKH (tt.)

Áp d

ụ

ng lu

ậ

t:

–

Ví d

ụ

v

ề

lu

ậ

t trên STRIPS:

–

STACK(X,Y):

P: CLEAR(Y) ^ HOLDING(X)
D: CLEAR(Y) ^ HOLDING(X)
A: ARMEMPTY ^ ON(X,Y)

–

UNSTACK(X,Y):

P: ON(X,Y) ^ CLEAR(X) ^ ARMEMPTY
D: ON(X,Y) ^ ARMEMPTY

</div>
(6)<div class='page_container' data-page=6>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 11

Áp d

ụ

ng lu

ậ

t:

–

Ví d

ụ

v

ề

lu

ậ

t trên STRIPS: (tt.)

–

PICKUP(X):

P: CLEAR(X) ^ ONTABLE(X) ^ ARMEMPTY
D: ONTABLE(X) ^ ARMEMPTY

A: HOLDING(X)

–

PUTDOWN(X):

P: HOLDING(X)
D: HOLDING(X)

A: ANTABLE(X) ^ ARMEMPTY

Các thành ph

ầ

n c

ủ

a HT LKH (tt.)

Áp d

ụ

ng lu

ậ

t:

–

Ví d

ụ

:

Trạng thái:

S0: ON(A,B) ^ ONTABLE(B) ^ CLEAR(A)

Luật: UNSTACK(A,B):

S1: ONTABLE(B) ^ CLEAR(A) ^ CLEAR(B) ^ HOLDING(A

–

Kh

ả năng phụ

c h

ồ

i.

Global Database: Chứa mô tảcho TT hiện tại.

Ghi lại dãy các phép toán đã được áp dụng, cùng thông sốcủa

chúng.

Phục hồi:

– ADD lại phần DELETE của 1 phép tốn.

</div>
(7)<div class='page_container' data-page=7>

Khoa Cơng Nghệ Thơng Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 13

Các thành ph

ầ

n c

ủ

a HT LKH (tt.)

Áp d

ụ

ng lu

ậ

t:

–

Ví d

ụ

quay lui:

1

2

3

Global database:
ONTABLE(B) ^
CLEAR(A) ^
CLEAR(B) ^
ONTABLE(A)

PUTDOWN(A)

UNSTACK(A,B)

Global database:
ONTABLE(B) ^

ON(A,B) ^
CLEAR(A)

BA
CK

TRA
CK

Các thành ph

ầ

n c

ủ

a HT LKH (tt.)

Phát hi

ệ

n l

ờ

i gi

ả

i:

–

Thành công khi:

T

ồ

n t

ạ

i 1 chu

ổ

i phép toán bi

ế

n TT

đầ

u

GOAL

–

B

ằ

ng cách nào?

Phụthuộc vào cách biểu diễn TT
Có thể:

- Matching đơn giản.

- Có thểphải thực 1 một bước chứng minh, như trong FOL.

Phát hi

ệ

n dead ends:

–

Cùng c

ơ

ch

ế như ph

át hi

ệ

n l

ờ

i gi

ả

i trên.

</div>
(8)<div class='page_container' data-page=8>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 15

S

ử

a l

ạ

i l

ờ

i gi

ả

i g

ầ

n

đ

úng:

–

Gi

ả

i t

ừ

ng bài toán nh

ỏ

, k

ế

t h

ợ

p l

ạ

i. B

ỏ

qua l

ờ

i ch

ư

a

đ

úng.

Hơi lãng ph

í.

–

Gi

ả

s

ử

Solution1 tìm th

ấ

y nh

ư

ng Diff(Solution1, GOAL) <> 0.

G

ọ

i l

ạ

i planing

để

lo

ạ

i b

ỏ

s

ự

khác nhau này, tìm ra Solution2.

K

ế

t qu

ả

= k

ế

t h

ợ

p (Solution1, Solution2).

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu

Đượ

c s

ử

d

ụ

ng b

ở

i STRIPS.

S

ử

d

ụ

ng stack ch

ứ

a goal + operators gi

ả

i ra goal.

Ví d

ụ

:

A C D

B

A D

C B

START:
ON(B,A) ^
ONATBLE(A) ^

ONATBLE(C) ^
ONATBLE(D) ^
AMREMPTY.

</div>
(9)<div class='page_container' data-page=9>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Môn: Trí tuệnhân tạo Side 17

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu (tt.)

Gi

ả

i:

–

T

ừ

goal:

ON(C,A) ^ ON(B,D) ^ ONATBLE(A) ^ ONTABLE(D)

–

Chia làm 4 goal:

ON(C,A)
ON(B,D)

ONTABLE(A) : đã giải – xem start.
ONTABLE(D) : đã giải – xem start.
–

Sub-goal m

ớ

i có th

ể

là:

ON(C,A)
ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD
Hay

ON(B,D)

ON(C,A)

ON(C,A) ^ ON(B,D) ^ OTAD

OTAD = ONTABLE(A) ^ 
ONTABLE(D) ^ 
[1]

[2]

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu (tt.)

Gi

ả

i:

–

Tóm t

ắ

t:

Đặt Goal đầu lên stack.
Lặp:

– Giải goal trên cùng của stack.

– Có thểsẽlàm stack dài ra do các goal mới.

– Dừng khi ko cịn goal trên stack.

–

Ví d

ụ

: ch

ọ

n [1]

đi tiế

p,

đượ

c.

STACK(C,A)

ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD.

</div>
(10)<div class='page_container' data-page=10>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 19

– Chồng mục tiêu mới:

CLEAR(A) 
HOLDING(C)

CLEAR(A) ^ HOLDING(C)
STACK(C,A)

ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD.
– Giải quyết CLEAR(A) cho ra chồng

mới:

ON(B,A)
CLEAR(B)

ARMEMPTY.

ON(B,A) ^ CLEAR(B) ^ 
ARMEMPTY

UNSTACK(B,A)
HOLDING(C)

CLEAR(A) ^ HOLDING(C)
STACK(C,A)

ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD.

– CLEAR(B) : được giải.

– ARMEMPTY: được giải.

– Combined goal - UNSTACK(B,A) :

được giải.

– Chồng mới là:

HOLDING(C)

CLEAR(A) ^ HOLDING(C)
STACK(C,A)

ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD.

– HOLDING(C) có thểthực hiện
bằng: PICKUP(C) hay
UNSTACK(C,x), x nào đó. Hai

chồng mới có thểlà:

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu (tt.)

Gi

ả

i:

[1]

ONTABLE(C)
CLEAR(C)
ARMEMPTY
ONTABLE(C) ^ 
CLEAR(C) ^ 
ARMEMPTY
PICKUP(C)

CLEAR(A) ^ HOLDING(C)
STACK(C,A)

ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD.

[2]

ON(C,x)
CLEAR(C)
ARMEMPTY
ON(C,x) ^ 
CLEAR(C) ^ 
ARMEMPTY
UNSTACK(C,x)

CLEAR(A) ^ HOLDING(C)
STACK(C,A)

ON(B,D)

</div>
(11)<div class='page_container' data-page=11>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Môn: Trí tuệnhân tạo Side 21

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu (tt.)

Gi

ả

i:

Ch

ọ

n [1]:

-

ONTABLE

(C):

đã giả

i.

-

CLEAR

(C):

đã giả

i.

-

ARMEMPTY chưa

:

hai h

ướ

ng:

(1): STACK(B,x)

(2): PUTDOWN(B).

Ch

ọ

n

STACK(B,x)

x = D, sinh ra ch

ồ

ng:

CLEAR(D)

HOLDING(B)
CLEAR(B) ^
HOLDING(B)
STACK(B,D)
ONTABLE(C) ^
CLEAR(C) ^
ARMEMPTY
PICKUP(C)

CLEAR(A) ^ HOLDING(C)
STACK(C,A)

ON(B,D)

ON(C,A) ^ ON(B,D) ^ OTAD.

L

ậ

p k

ế

ho

ạ

ch theo ch

ồ

ng m

ụ

c tiêu (tt.)

Gi

ả

i:

– Các goal sau đây đã được giải:

CLEAR(D)
HOLDING(B)

– Dùng được STACK(B,D)

– Sinh ra:

ONTABLE(A) ^

ONATBLE(C) ^
ONATBLE(D) ^

ON(B,D) ^ ARMEMPTY.

– PICKUP(C) và STACK(C,A)
lần lượt được thực hiện.

– ON(B,D) cũng được thực
hiện.

– goal cuối cùng :

ON(C,A) ^ ON(B,D) ^ OTAD

Plan nh

ư

</div>
(12)<div class='page_container' data-page=12>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Môn: Trí tuệnhân tạo Side 23

Ví d

ụ

khác:

A B

C

C
B

START:
ON(C,A) ^
ONATBLE(A) ^
ONATBLE(B) ^
AMREMPTY.

GOAL:
ON(A,B) ^
ON(B,C) ^
ONATBLE(C)

A

YC: Đưa ra chồng các mục tiêu theo thứtựgiải quyết

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n

H

ạ

n ch

ế

c

ủ

a ki

ể

u LKH tr

ướ

c:

–

Ch

ỉ

dùng cho bài tốn mà

ở đ

ó các bài tốn con có th

ể đượ

c gi

ả

i

riêng, khơng

ả

nh h

ưở

ng

đế

n k

ế

t qu

ả

c

ủ

a bài toán con

đ

ã

đượ

c

gi

ả

i tr

ướ

c nó.

–

Vì th

ế

: dùng stack of goals

để

ch

ứ

a và gi

ả

i l

ầ

n l

ượ

t các goal.

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n:

–

Dùng

đượ

c cho tr

ườ

ng h

ợ

p các goal có

ả

nh h

ưở

ng nhau.

–

Dùng Set of goals thay cho Stack of goals.

–

Quá trình gi

ả

i: các toán t

ử đượ

c s

ắ

p th

ứ

t

ự

riêng ph

ầ

n. Khi k

ế

t

</div>
(13)<div class='page_container' data-page=13>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 25

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

Ví d

ụ

:

A B

C

C
B

START:
ON(C,A) ^
ONATBLE(A) ^
ONATBLE(B) ^
AMREMPTY.

GOAL:
ON(A,B) ^
ON(B,C) ^
ONTABLE(C)

A

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

GOAL

Gi

ả

i cho tr

ườ

ng h

ợ

p: ON(A,B) & ON(B,C)

STACK(A,B) STACK(B,C)

CLEAR(B)
*HOLDING(A)

---STACK(A,B)

---ARMEMTY
ON(A,B)
¬CLEAR(B)
¬HOLDING(A)
CLEAR(C)
*HOLDING(B)

---STACK(B,C)

---ARMEMTY
ON(B,C)

Precondition
Operator

Postcondition

ON(A,B),
ON(B,C)

</div>
(14)<div class='page_container' data-page=14>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 27

T

ậ

p goal m

ớ

i:

*CLEAR(A)
ONTABLE(A)
*ARMEMPTY

---PICKUP(A)

---¬ONTABLE(A)
¬ARMEMPTY
HOLDING(A)
HOLDING(A)

HOLDING(B)

*CLEAR(B)
ONTABLE(B)
*ARMEMPTY

---PICKUP(B)

---¬ONTABLE(B)
¬ARMEMPTY
HOLDING(B)

Operators có th

ể

dùng:

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

T

ậ

p goal m

ớ

i:

CLEAR(B)
ARMEMPTY*
ARMEMPTY*
CLEAR(A)

GOAL

STACK(A,B) STACK(B,C)
PICKUP(A) PICKUP(B)

</div>
(15)<div class='page_container' data-page=15>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 29

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

T

ậ

p goal m

ớ

i:

GOAL

STACK(A,B) STACK(B,C)
PICKUP(A) PICKUP(B)

Th

ứ

t

ự

:

STACK(A,B)
Ảnh hưởng
PICKUP(B)

Vì CLEAR(B) khơng đúng nữa
Thêm ràng buộc

CLEAR(B)
ARMEMPTY*
ARMEMPTY*
CLEAR(A)

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

T

ậ

p goal m

ớ

i:

STACK(A,B) STACK(B,C)
PICKUP(A) PICKUP(B)

Th

ứ

t

ự

:

PICKUP(A)
Ảnh hưởng
PICKUP(B)

Vì ARMEMPTY khơng đúng nữa
Thêm ràng buộc

</div>
(16)<div class='page_container' data-page=16>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 31

T

ậ

p goal m

ớ

i:

GOAL

STACK(A,B) STACK(B,C)
PICKUP(A) PICKUP(B)

Th

ứ

t

ự

:

PICKUP(A)

Có thểgiải quyết bởi ràng buộc:

PICKUP(B) STACK(B,C) PICKUP(A)
Nên thứtựlà:

CLEAR(B)
ARMEMPTY*
ARMEMPTY*
CLEAR(A)

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

T

ậ

p goal m

ớ

i:

CLEAR(B)
ARMEMPTY*

ARMEMPTY*
CLEAR(A)

CLEAR(A) có thểgiải bởi
UNSTACK(x,A)

*ON(x,A)
*CLEAR(x)
*ARMEMPTY

---UNSTACK(x,A)

---¬ARMEMPTY
CLEAR(A)
HOLDING(A)
¬ON(x,A)

</div>
(17)<div class='page_container' data-page=17>

Khoa Cơng Nghệ Thơng Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 33

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

T

ậ

p goal m

ớ

i:

CLEAR(A)

CLEAR(A) có thểgiải bởi
UNSTACK(x,A)

*ON(x,A)

*CLEAR(x)
*ARMEMPTY

---UNSTACK(x,A)

---¬ARMEMPTY
CLEAR(A)
HOLDING(A)
¬ON(x,A)

Heuristic: x = C

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

T

ậ

p goal m

ớ

i:

ON(x,A)
CLEAR(x)
ARMEMPTY

CLEAR(C)
ARMEMPTY
Bị ảnh hưởng bởi
STACK(B,C) &
PICKUP(A)
PICKUP(B)

Ràng buộc bổsung:

STACK(A,B) STACK(B,C)
PICKUP(A) PICKUP(B)

Th

ứ

t

ự

:

</div>
(18)<div class='page_container' data-page=18>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 35

AMREMPTY cho
PICKUP(B)

Có thểthực hiện bởi:
PUTDOWN(C), như sau:

UNSTACK(C,A) PUTDOWN(C) PICKUP(B)

HOLDING(C)

---PUTDOWN(C)

---¬HOLDING(C)
ONTABLE(C)
ARMEMPTY

GOAL

STACK(A,B) STACK(B,C)

PICKUP(A) PICKUP(B)

Th

ứ

t

ự

:

UNSTACK(C,A)
PUTDOWN(C)

L

ậ

p k

ế

ho

ạ

ch phi tuy

ế

n (tt.)

GOAL

STACK(A,B) STACK(B,C)
PICKUP(A) PICKUP(B)

UNSTACK(C,A)
PUTDOWN(C)

</div>
(19)<div class='page_container' data-page=19>

Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM

Bài Giảng Mơn: Trí tuệnhân tạo Side 37

</div>

chapter10

<b>Ch</b>

ươ

<b>ng 10</b>

<b>L</b>

Ậ

<b>P K</b>

Ế

<b>HO</b>

Ạ

<b>CH</b>

<b>N</b>

ộ

<b>i dung</b>

<b>Các thành ph</b>

ầ

<b>n c</b>

ủ

<b>a 1 h</b>

ệ

<b>th</b>

ố

<b>ng l</b>

ậ

<b>p k</b>

ế

<b>ho</b>

ạ

<b>ch</b>

<b>L</b>

ậ

<b>p k</b>

ế

<b>ho</b>

ạ

<b>ch theo ch</b>

ồ

<b>ng m</b>

ụ

<b>c tiêu</b>

<b>L</b>

ậ

<b>p k</b>

ế

<b>ho</b>

ạ

<b>ch phi tuy</b>

ế

<b>n</b>

<b>L</b>

ậ

<b>p k</b>

ế

<b>ho</b>

ạ

<b>ch phân c</b>

ấ

<b>p</b>

<b>Các h</b>

ệ

<b>th</b>

ố

<b>ng ph</b>

ả

<b>n </b>

ứ

<b>ng</b>

<b>V</b>

ớ

<b>i bài toán </b>

đơ

<b>n gi</b>

ả

<b>n ( 8-puzzle):</b>

Đề

ngh

ị

m

ộ

t t