Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ộ Ố Ả
Ậ
Ể
TÌM HI U M T S GI I THU T
MÔN H C Ọ
Ạ
Ệ
TRÍ TU NHÂN T O
ồ
GVHD: Th.S Ngô H Anh Khôi
ự
ễ
ậ
ươ
Sinh viên th c hi n:
ệ Nguy n L p An Kh
ng
ề ộ
ế
1. Tìm ki m theo chi u r ng.
ậ ế
ệ ế ướ
ỉ ng t
ế ề ộ ỉ ề ớ ỉ ậ
i m t đ nh đích, và tìm ki m đ ướ ớ c t
ườ ậ ế ố ố ỉ ừ t c các đ nh khác. Trong đ th không có tr ng s , thu t toán tìm
ề ộ ộ ỉ ồ ị ắ ườ ậ
ầ ượ ớ
ậ ỉ t nhìn tr
ấ ề ớ ỉ ướ ậ ặ ạ ề ọ ể ng đi ng n nh t có th . Thu t toán BFS ỗ ố t nhìn các đ nh k v i đ nh g c. Sau đó, v i m i ư ề ớ ỉ ạ ầ ượ c các đ nh k v i nó mà ch a i l n l ế i. Xem thêm thu t toán tìm ki m theo chi u sâu, c đó và l p l c quan sát tr
ướ ử ụ ự ỉ quan sát các đ nh khác
ề ộ ậ ồ ị ế ộ Tìm ki m theo chi u r ng (BFS) là m t thu t toán tìm ki m trong đ th trong ồ ủ ồ ị ộ ỉ c m t đ nh c a đ th ; (b) đó vi c tìm ki m ch bao g m 2 thao tác: (a) cho tr ể ướ ớ ế ừ i ti p theo. Có thêm các đ nh k v i đ nh v a cho vào danh sách có th h ế ụ ể ử ụ th s d ng thu t toán tìm ki m theo chi u r ng cho hai m c đích: tìm ki m ườ ừ ộ ỉ đ ng đi t ng đi t m t đ nh g c cho tr ỉ ố ớ ấ ả đ nh g c t i t ề ộ ế ki m theo chi u r ng luôn tìm ra đ ố ắ ầ ừ ỉ đ nh g c và l n l b t đ u t ố ỉ đ nh trong s đó, thu t toán l ượ đ ư trong đó cũng s d ng 2 thao tác trên nh ng có trình t ế ớ v i thu t toán tìm ki m theo chi u r ng.
ậ ớ ớ ớ i F sau đó t i E t A t i C,
ớ gi ớ t ả ế ố i G và cu i cùng t (cid:0) i B t ắ ư ề ệ
ượ ộ ượ ể ỉ đ nh mà đã đ (cid:0) ề ộ ớ ệ ừ i thu t tìm ki m theo chi u r ng duy t t ả ậ i thu t này tuân theo qui t c: i D. Gi ệ ế ớ ỉ ề Qui t c 1ắ : Duy t ti p t i đ nh li n k mà ch a đ ẩ ỉ ị ề ệ ế ề ấ ầ ỉ ỉ ấ c duy t. Đánh d u ợ c duy t. Hi n th đ nh đó và đ y vào trong m t hàng đ i (queue).. Qui t c 2ắ : N u không tìm th y đ nh li n k , thì xóa đ nh đ u tiên trong
hàng đ i.ợ (cid:0) ặ ạ ắ ớ ố i Qui t c 1 và 2 cho t ợ i khi hàng đ i là tr ng. Qui t c 3ắ : L p l
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ứ ụ ng d ng:
ượ ể ả ề c dùng đ gi i nhi u bài toán trong lý
ậ ế ồ ị ế ẳ ạ ề ộ Thu t toán tìm ki m theo chi u r ng đ ư thuy t đ th , ch ng h n nh :
(cid:0) ầ
(cid:0) ề ớ ườ ỉ ắ ấ ỉ ng đi ng n nh t gi a hai đ nh u và v (v i chi u dài đ ng đi tính
ộ ấ ả t c các đ nh trong m t thành ph n liên thông Tìm t ườ ữ Tìm đ ằ ố b ng s cung) ể ồ ị
(cid:0) ộ ồ ị (cid:0) Ki m tra xem m t đ th có là đ th hai phía ầ Tìm các thành ph n liên thông
Ư ể u đi m: (cid:0) ệ ấ ả ể ả ề ế
ỉ ữ ạ ế ắ
ả t c các đ nh đ tr v k t qu . ả ắ ậ (cid:0) N u s đ nh là h u h n, thu t toán ch c ch n tìm ra k t qu . ượ Xét duy t t ế ố ỉ ể c đi m: Nh
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
ệ ố ỉ
ụ
ế
ấ
GVHD: Th.S Ngô Hồ Anh Khôi ạ (cid:0) Mang tính ch t vét c n, không nên áp d ng n u duy t s đ nh quá
l n.ớ
ế
ệ ấ ả ỉ t c đ nh, không chú ý đ n thông ệ ả ẫ ệ
ệ
ế
ể
ỉ
ấ (cid:0) Mang tính ch t mù quáng, duy t t ỉ ế
ầ
tin trong các đ nh đ duy t hi u qu , d n đ n duy t qua các đ nh không c n thi
t.
ế
ề
2. Tìm ki m theo chi u sâu.
t là DFS), còn
ả ậ ả ặ ế i thu t tìm ki m u tiên chi u sâu, là gi ệ i thu t duy t ho c tìm
ế ắ t t ậ ế ề ử ụ ớ ỉ
ề ầ
ặ ượ ỉ ặ ượ ỉ ề ỉ ừ ả
ướ ề ậ ả i thu t tìm ki m theo chi u sâu (Depth First Search – vi Gi ế ư ượ ọ c g i là gi đ ể ộ ồ ị ộ ế ặ ki m trên m t cây ho c m t đ th và s d ng stack (ngăn x p) đ ghi nh đ nh ề ề ể ắ ầ ấ ỳ ế ề ệ c đ nh li n k trong b t k li n k đ b t đ u vi c tìm ki m khi không g p đ ặ ớ ớ ậ ế ụ ả ặ c đ nh c n tìm ho c t i i khi g p đ i thu t ti p t c cho t vòng l p nào. Gi ế ở ớ ậ ộ m t nút không có con. Khi đó gi i thu t quay lui v đ nh v a m i tìm ki m ướ b c tr c.
ề ầ
ệ ừ iả i ọ iớ C t A t i thu t tìm ki m theo chi u sâu đ u tiên duy t t ớ G. Gi ế iớ E, sau đó t ố iớ F và cu i cùng t
ả ậ iớ D sau đó t ắ Trong hình minh h a trên, gi các đ nhỉ iớ B t ậ thu t này tuân theo qui t c sau:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi ề
(cid:0) ư ệ Qui t c 1ắ : Duy t ti p t
ượ ệ ế ớ ỉ ỉ ề i đ nh li n k mà ch a đ ẩ ị ượ ộ ể ỉ đ nh mà đã đ (cid:0) ệ ế ỉ
ấ ề ậ ẽ ấ ấ ả ấ ỉ ả ấ c duy t. Đánh d u ế c duy t. Hi n th đ nh đó và đ y vào trong m t ngăn x p (stack). ộ ỉ Qui t c 2ắ : N u không tìm th y đ nh li n k , thì l y m t đ nh t ừ ề trong ế ừ ế trong ngăn x p i thu t s l y t t c các đ nh t
ề ỉ
(cid:0) ngăn x p (thao tác pop up). (Gi mà không có các đ nh li n k nào) ắ ắ ớ ố ề ặ ạ i các qui t c 1 và qui t c 2 cho t ế i khi ngăn x p là tr ng. Qui t c 3ắ : L p l
Ư ể u đi m: (cid:0) ệ ấ ả ể ả ề ế
ỉ ữ ạ ế ắ ắ
Nh Xét duy t t ế ố ỉ ể c đi m:
ế ạ ớ
ấ ấ
ả t c các đ nhđ tr v k t qu . ả ậ (cid:0) N u s đ nh là h u h n, thu t toán ch c ch n tìm ra k t qu . ượ (cid:0) Mang tính ch t vét c n, không nên áp d ng n u duy t s đ nh quá l n. t c đ nh, không chú ý đ n thông tin (cid:0) Mang tính ch t mù quáng, duy t t ầ ụ ệ ấ ả ỉ ế ả ẫ ệ ố ỉ ế ỉ ệ ệ ể ệ ỉ
trong các đ nh đ duy t hi u qu , d n đ n duy t qua các đ nh không c n thi t.ế
ế
ề
ớ ạ
3. Tìm ki m theo chi u sâu có gi
i h n.
ạ ế ồ ị ế ậ
ậ
hay depthlimited search algorithm là m t thu t toán phát tri n các ớ ạ ớ ạ i h n ể ữ
ộ ứ ể ậ ế ầ ệ Trong trí tu nhân t o hay các lý thuy t đ th , thu t toán tìm ki m có gi ộ đ sâu (DLS) ư nút ch a xét các theo chi u sâu nh ng có gi ư ườ con đ i h n m c đ tránh đi vào nh ng t nh trong thu t toán tìm ki m sâu d n. ề ạ ế ng không mang l ư ả ố i k t qu t
Ư ể u đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
ớ ệ
ế
ộ
GVHD: Th.S Ngô Hồ Anh Khôi ả ử ụ
(cid:0) Nó là b nh hi u qu , s d ng không gian tuy n tính O (bxL)
ượ Nh ể c đi m:
ư
ế
ả
ằ
ướ
ớ ạ
i pháp n m d
i gi
i h n L(d
ấ Solution.
(cid:0) Ch a hoàn thành n u gi
ể
không th tìm th y
ấ ố ư ế
ề
ể
ơ Solution.
(cid:0) Nó có th không tìm th y t
i u n u có nhi u h n
ả ề ờ
ệ
ả
ấ
(cid:0) Nó không hi u qu v th i gian vì ph i m t O (b ^ L).
ế
ế
ể
ặ
ượ ử ụ
(cid:0) Nó có th gây ra các vòng l p n u tìm ki m cây đ
c s d ng trên
ể
ồ
bi u đ .
ố
ế
ấ
4. Tìm ki m theo giá thành th ng nh t.
ữ ợ ư ữ ệ ư ầ ử
ỏ ấ ấ
ầ ử ợ ẽ ấ
ộ ạ ứ
ra kh i hàng đ i s căn c vào đ u tiên nh nh t.
ườ
ệ ệ ổ
ớ ộ ư
cùng v i đ u tiên
ộ ư
ỏ
ắ
ử ụ ạ ầ ậ
ể ư ườ ữ
ệ
ể ư ạ
ữ ậ ạ ộ
Hàng đ i u tiên PQ là c u trúc d li u l u tr các ph n t
ủ
c a nó và khi l y ph n t
ấ
ng đi ng n nh t (hi n có)
Cho m t tr ng thái n, ký hi u g(n) là t ng chi phí đ
ợ
ộ
ế
ừ ạ
tr ng thái ban đ u S đ n tr ng thái n. Thu t toán UCS s d ng m t hàng đ i
t
ư
ng đi.
u tiên (Priority Queue – PQ) đ l u tr và duy t các tr ng thái trên đ
ượ
Thu t toán dùng thêm m t danh sách CLOSE đ l u tr các tr ng thái đã đ
c
xét.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0)
ấ
ố
ố ư
ườ
i u vì con đ
ng có chi phí
ấ ượ
ấ
ế
Tìm ki m theo giá thành th ng nh t là t
ọ
c ch n.
th p nh t đ
ượ Nh ể
c đi m:
ầ
ướ
ế ố ượ
ườ
ả
ậ
ế
ế
c liên quan đ n tìm ki m
ể
thu t này có th
ạ
(cid:0) Không c n quan tâm đ n s l
ng các b
ế
ẫ
ỉ
và ch quan tâm đ n chi phí đ
ng d n. Do đó gi
ặ
ộ
ị ắ ẹ
b m t k t trong m t vòng l p vô h n.
ầ
ế
5. Tìm ki m sâu d n.
ế ồ ị ế ế ệ ạ ậ ầ
ệ ế ặ ậ Trong trí tu nhân t o hay lý thuy t đ th , thu t toán tìm ki m ki m sâu d n là
ặ ồ ị
1 thu t toán duy t ho c tìm ki m trên cây ho c đ th .
ượ ư ể
ả ằ ở ộ ế
ơ ủ
i n m DLS
ả ậ
Thu t toán đ
ộ
ạ
h n đ sâu
ộ
ạ
h n đ sâu l thì gi ớ
ậ
ắ
i
c đ a ra đ kh c ph c đi m yêu c a thu t toán tìm ki m gi
ớ
ớ
. Đó là khi mà t
đ sâu l n h n gi
i
i gi
i thu t ụ
ể
ờ
ấ ả
t c các l
ẽ ấ ạ
ậ DLS s th t b i.
ả ậ Gi i thu t tìm ki m sâu d n ầ s :ẽ (cid:0) ố ớ ườ i thu t (cid:0) ế
ả
ấ ạ ậ DLS
ế ụ ộ
ng đi có đ dài <= 1
ố ớ ườ ế ả ậ ộ ụ
đ i v i đ
áp d ng gi
ụ
N u th t b i, ti p t c áp d ng gi i thu t dfs đ i v i đ ng đi có đ dài
ả ặ ộ ượ ượ ờ
c l i gi i ho c khi toàn b cây đã đ c
ả <= 2
ứ ư ậ
(cid:0) …..c nh v y đ n khi tìm đ
xét mà không tìm đ ế
ượ ờ
c l i gi i.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
ủ ớ ễ ệ ệ ọ
GVHD: Th.S Ngô Hồ Anh Khôi
ế
Luôn tìm ra nghi m (n u bài toán có nghi m), mi n là ch n max đ l n
ề ộ
ế
(gi ng nh tìm ki m theo chi u r ng)
ư ố
ộ ứ ạ ế ờ ố ộ Có đ ph c t p th i gian là O(kd) (gi ng tìm ki m r ng)
ộ ứ ạ ế ố Có đ ph c t p không gian là O(k*d) (gi ng tìm ki m sâu)
ả ụ ầ
ế
i thu t tìm ki m sâu d n th
ộ ươ
ệ ậ
ớ ủ Gi
ạ
gian tr ng thái l n và đ sâu c a nghi m không bi ng áp d ng cho các bài toán có không
c. ế ướ
t tr
Ư ể u đi m:
(cid:0) Nó t
ả
ổ ứ ề ặ ủ ệ ế ợ
i ích c a thu t toán tìm ki m BFS và DFS v m t hi u
ộ ch c các l
ế ớ ậ
qu tìm ki m và b nh nhanh.
ủ
ế
ạ
ạ
ướ
(cid:0) H n ch chính c a IDS là nó l p l
ặ ạ ấ ả
i t
ệ ủ
t c các công vi c c a giai đo n tr
c.
ượ Nh ể
c đi m:
ồ
ế
6. Tìm ki m leo đ i.
ồ ế ế ở ộ
ướ ế ớ
ẫ
ng d n b i hàm đánh giá.
ộ ỉ
ề ượ ướ
c h
ể
ứ ẹ c ti p theo
ể ộ
ủ ố ỉ
ượ ở ị Tìm ki m leo đ i là tìm ki m theo đ sâu đ
ế
Song khác v i tìm ki m theo đ sâu, khi phát tri n m t đ nh u thì b
ấ ể
ỉ
ọ
ta ch n trong s các đ nh con c a u, đ nh có h a h n nhi u nh t đ phát tri n,
ỉ
đ nh này đ c xác đ nh b i hàm đánh giá.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ọ ế ế ươ ướ ng pháp tìm ki m leo đ i chú tr ng tìm h
ằ
ế
ạ
ớ ế
ỗ ướ
i m i b
ấ ể ứ ẹ
ế ướ ấ
ọ
c. V n đ quan tr ng là bi
ẩ ả ị
ạ
ế
ậ
ề
ộ ạ
c ta s u tiên ch n m t tr ng thái có h a h n
ề
ướ
ỗ ạ ọ
ế
ủ ườ ế ớ t khai
ng đi ti p và đ y nhanh
ng ta gán m i tr ng thái c a bài toán v i
ứ ộ ầ
ạ ộ ố
ề ờ
ạ
ề ớ ế
ế ủ ể ế ạ
ặ ồ
ễ ẫ
ng đi d d n đ n tr ng
Ph
ứ
ả
ượ ư
ấ
thái đích nh t. Cách đó đ
c đ a ra nh m làm gi m công s c tìm ki m.
ự
ấ
ồ
ậ
Thu t toán tìm ki m leo đ i th c ch t là thu t toán tìm ki m theo chi u
ẽ ư
sâu, song t
ể
i đich nh t đ phát tri n tr
nhanh t
ồ ể
thác kheo léo thông tin ph n h i đ xác đ nh h
quá trình tìm ki m. Thông th
ủ
ằ
m t s đo (hàm đánh giá) nào đó nh m đánh giá m c đ g n đích c a nó.
ẽ ượ
ệ
Đi u đó có nghĩa là n u tr ng thái hi n th i là u thì tr ng thái v s đ
c
ị
phát tri n ti p theo n u v k v i u và hàm đanh giá c a v đ t giá tr max
(ho c min).
ượ Nh ể
c đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ị ố ơ
ư
ả ể ươ
ng án t
(cid:0) C c tr đ a ph
ự
ị
ươ
ả
ph i là ph
ướ ể
nút tr
ườ
ng đi.
đ
ớ ạ ả ỏ ng: nút đang xét t
ấ
ng khác. Gi ậ
t h n các nút lân c n, nh ng đó không
ề
ể
ậ
t nh t trong toàn th , ví v y có th ph i quay lui v
ề
ướ
i nhi u i pháp này đòi h i ghi nh l ố
c đ đi theo h
(cid:0) Cao nguyên: Các giá tr c a các ph
ươ ư ị ng án nh nhau, không xác đ nh
7. Simulated annealing search.
ượ ướ ố ơ ậ đ c ngay h t h n trong vùng lân c n. ị ủ
ng nào là t
ự ứ ạ ạ ộ ạ (annealing process): Kim lo i ngu i đi và l nh c ng l i
ế ấ ủ
D a trên quá trình tôi
thành c u trúc k t tinh
ể ượ ể ố ư ng pháp tìm ki m Simulated Annealing có th tránh đ c các đi m t i u
ế
ươ
Ph
ụ ộ
c c b (local optima)
ươ ử ụ ế ng pháp tìm ki m Simulated Annealing s d ng chi n l
ế
c tìm ki m ng u
ầ ự ấ ậ ổ ị
ế ượ
ụ
ả ấ ậ ạ ổ ẫ
Ph
nhiên, trong đó ch p nh n các thay đ i làm tăng giá tr hàm m c tiêu (c n c c
ế
ạ
đ i hóa) và cũng ch p nh n (có h n ch ) các thay đ i làm gi m
ố ề ử ụ ể ộ ng pháp tìm ki m Simulated Annealing s d ng m t tham s đi u khi n T
ế
ệ ố ươ
ư Ph
(nh trong các h th ng nhi ệ ộ
t đ )
ắ ầ ề ậ ả ầ ị ❑ B t đ u thì T nh n giá tr cao, và gi m d n v 0
ượ
ỏ
ồ ừ ạ ố ư ụ ộ ằ
t qua) các đi m t
ờ ể
ệ ấ ủ ư ả ả
i u c c b b ng cách cho phép c
ầ ầ
tr ng thái hi n th i, nh ng gi m d n t n xu t c a các
ưở
ng: Thoát kh i (v
Ý t
ể
ị
i” t
các d ch chuy n “t
ể ồ
i này
di chuy n t
ứ ộ ả ượ ị
ể ứ
ấ ố ớ
ấ ấ ẽ ố
ị ủ
ế
ầ
c) N u giá tr c a tham s T (xác đ nh m c đ gi m t n
(Có th ch ng minh đ
ế
ươ
ả
ậ
ể ồ
xu t đ i v i các di chuy n t
ng pháp tìm ki m Simulated
i) gi m ch m, thì ph
ỉ
ụ ớ
ả ố ư
i u toàn c c v i xác su t x p x 1
i t
i gi
Annealing s tìm đ ượ ờ
c l
ươ ế ấ ượ ử ụ ng pháp tìm ki m Simulated Annealing Search r t hay đ c s d ng trong
ự ế ế ơ ồ ả ậ ị ạ Ph
các lĩnh v c: thi t k s đ b ng m ch VLSI, l p l ch bay, …
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ế ớ
ộ ỹ ạ ậ ỗ ộ
ữ ệ
ẽ ạ ể ố
Simulated annealing search có th đ i phó v i các mô hình phi tuy n tính
ề
ồ
cao, d li u h n lo n và n ào và nhi u ràng bu c. Đó là m t k thu t
m nh m và chung chung.
(cid:0) ươ ủ ớ ị ươ ng khác
u đi m chính c a nó so v i các ph
ế ậ ạ ả Ư ể
là tính linh ho t và kh năng ti p c n toàn c u s t ế
ng pháp tìm ki m đ a ph
ầ ự ố ư
i u.
(cid:0) ậ ấ ỳ ự ạ ạ ộ
ế Thu t toán này khá linh ho t vì nó không d a trên b t k thu c tính h n
ủ
ch nào c a mô hình.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
(cid:0) M t b t l
ượ Nh ể
c đi m:
i
ỏ ủ ộ ấ ợ Simulated annealing search là chuyên sâu tính toán. Có t n ồ
i các bi n th c b n nhanh h n mô ph ng
ể ơ ả
ễ , nh ng rõ ràng chúng
ượ ử ụ ế
ượ ậ ộ ư
ơ
c mã hóa d dàng và vì v y chúng không đ c s d ng r ng
ạ
t
không đ
rãi.
ế
8. Tìm ki m Beam
ề ộ ể ố
ậ
i thu t tìm ki m beam gi ng nh tìm ki m theo chi u r ng, nó phát tri n các
ở ộ ế
ở ứ ế ế
ứ ồ ư
ỉ ể ả
Gi
ỉ
đ nh m t m c r i phát tri n các đ nh m c ti p theo.
ể ấ ả m t
ề ộ
ạ ế ỉ ể
ượ ế ị
ỉ
ứ
ố ỉ ề ộ ỉ
ở ộ
t c các đ nh
ấ
ố
ỉ
t nh t(các đ nh
ở ấ
b t kì m c
c xác đ nh b i hàm đánh giá). Do đó trong tìm ki m beam,
ế
c phát tri n, trong khi tìm ki m theo chi u r ng, s đ nh
ố ế
Tuy nhiên trong tìm ki m theo chi u r ng, ta phát tri n t
ế
ứ
m c, còn trong tìm ki m beam, ta h n ch ch phát tri n đ nh K t
ở
này đ
ỉ
ượ
nào cũng có K đ nh đ
ể ở ứ
ầ
m c d là b
c n phát tri n ể
d (b là nhân t t nhánh).
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ế ả ả ợ i th là có kh năng làm gi m tính toán, và do đó,
ớ ủ ờ ồ
ụ ộ
ơ ả ủ ứ
ế ủ
ề ộ
ớ ươ ơ ế
Tìm ki m beam có l
ế
ờ
ế
th i gian c a m t tìm ki m. Đ ng th i, m c tiêu th b nh c a tìm ki m
ít h n nhi u so v i các ph ng pháp tìm ki m c b n c a nó.
ượ Nh ể
c đi m:
ế ể ẫ
ụ ể ế
i u và th m chí có th không đ t đ
ủ
ậ
ế ạ ượ ậ ợ ế
c đi m chính c a tìm ki m beam là tìm ki m có th không d n đ n
ự
c m c tiêu. Trong th c
ườ
c nút ng h p: đ t đ
ứ
ấ
ạ ượ ặ ắ c nút m c tiêu và không còn nút
(cid:0) Nh
ể
ượ
ụ
ạ ượ
ố ư
m c tiêu t
ế
, thu t toán tìm ki m chùm ch m d t cho hai tr
t
ụ
ộ
ụ
m c tiêu b t bu c ho c không đ t đ
nào đ khám phá.
ể
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ế
ậ
9. Tìm ki m nhánh c n.
ươ ố ư ổ ợ ệ i các bài toán t ng pháp ch y u đ gi i u t
ừ ủ ế
ướ ể ả
ế ế ả
ế
ẽ ố ầ ệ ậ
ủ
ị ệ ờ ủ ậ ạ ệ
ự
Là ph
h p. Ta th c hi n vi c
ẽ
ả ố ơ
ấ
t h n thì r
c, n u không có kh năng tìm th y k t qu t
đánh giá theo t ng b
ể
ệ
ự
ỉ
nhánh nó, không th c hi n tìm ti p mà chuy n ngay sang nhánh khác. Khi đó, ch
ầ
ả ố ơ
ế
ầ
t d n
c n ghi nh n các k t qu t
ả ố ơ
ế
i giá tr hi n th i c a bài toán.
lên do khi tìm ra k t qu t t h n lúc ban đ u. Nghi m c a bài toán s t
ẽ ậ
t h n ta s c p nh t l
ả ế ủ ộ ạ ươ ng pháp quay lui dùng
ế ươ
Ph
ể ả
đ gi ậ
ng pháp Nhánh c n là m t d ng c i ti n c a ph
i quy t bài toán t ố ư .
i u
Ư ể u đi m:
(cid:0) ươ ệ ể ậ ộ ng pháp nhánh c n không quét qua toàn b các nghi m có th có
Ph
ủ
c a bài toán .
ượ Nh ể
c đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
(cid:0) Khó khăn c a ph
ượ ế ậ
ề ế ệ c các
ầ
t s b nhi u nghi m không c n
ế ả ươ
ủ
ng pháp nhánh c n là làm th nào đánh giá đ
ệ
ố ẽ ỏ
ậ
ở ộ
nghi m m r ng (c n). N u đánh giá t
t ph i xét (nhánh)
thi .
ả
ậ
10. Gi
i thu t Minimax.
ậ ệ ọ ướ ậ
i thu t Minimax là m t thu t toán đ quy l a ch n b
ườ ườ
ờ ộ
ư ờ ơ ố
ờ ướ c đi c a mình nh c vua, c t
ủ ế ờ
ư ộ
ế ế
ự
c đi k ti p trong
i thay
i. Xét m t trò ch i đ i kháng trong đó hai ng
ơ
ng, c caro, c vây… Khi ch i
ạ
ượ ủ ố ế
ả ứ
ả ử ố ư ế
ế ủ
ể
c ph n ng và n
ạ
ố ả ế ụ ứ ề
ể ướ
ủ ủ ạ
ậ thuy t này đ tìm ủ
ử ụ
s đ i th c a b n cũng s d ng ki n th c v không
i thu t Minimax áp d ng gi
ấ ậ ượ ướ
c b
ằ ế ế ế ố
c đi k ti p t
ế
ể
ị ạ ố t nh t ế
c ti p
ế ạ
ơ ị
ể
ơ ượ ọ ố
ế
ư ườ ạ ợ i quy t dành th ng l
ố
ố ắ
i và c g ng t
ạ ố ắ ườ i ng
ả ố ể
thi
ế
i đa hóa u th
ố
ả
i c g ng gi m đi m s
ế
t
t. Gi
ơ ế ề ạ
ố
ứ ơ
ủ ế
ể ệ ậ ơ ị ị
ị
ơ ẽ ự ướ ườ ế ợ ị ả
Gi
ơ
ộ
m t trò ch i có hai ng
ướ
phiên đi n
ạ
ể
ạ
b n có th khai tri n h t không gian tr ng thái nh ng khó khăn ch y u là b n
ả
c đi c a đ i th mình nh th nào? Cách
ph i tính toán đ
ơ
ả
ử
x lý đ n gi n là b n gi
ả
ạ
ạ
gian tr ng thái gi ng b n. Gi
ơ
ủ
ạ
ế
ki m không gian tr ng thái c a trò ch i.
ả
t nh t trong các
Gi
i thu t Minimax giúp chúng ta tìm đ
ạ
không gian tr ng thái ti p theo b ng cách phát tri n h t không gian tr ng thái
ấ ở ướ
b
cây trò ch i đ nh giá tr cho các Node tìm Node có tr ng thái t
theo phát tri n ti p.
ủ
c g i là MIN và MAX luân phiên thay th nhau đi.
Hai đ i th trong trò ch i đ
ắ
ế
ệ
MAX đ i di n cho ng
ệ
ơ ạ
ượ ạ
ủ
i ch i đ i di n cho MIN l
c l
c a mình, ng
ố ủ
ể
ố ắ
ủ
c a MAX và c g ng làm cho đi m s c a mình càng âm càng t
ư
ứ
ư
đ a ra MIN và MAX có ki n th c nh nhau v không gian tr ng thái trò ch i và
ư
ủ ề ố ắ
ả
c hai đ i th đ u c g ng nh nhau.
ộ ạ
ễ
ể
ỗ
M i Node bi u di n cho m t tr ng thái trên cây trò ch i. Node lá là Node ch a
ạ
ơ
tr ng thái k t thúc c a trò ch i.
ằ
ả
i thu t Minimax th hi n b ng cách đ nh tr các Node trên cây trò ch i:
Gi
ị ớ
(cid:0) Node thu c l p MAX thì gán cho nó giá tr l n nh t c a con Node đó.
ỏ
(cid:0) Node thu c l p MIN thì gán cho nó giá tr nh nh t c a con Node đó.
ọ
i ch i s l a ch n cho mình n ấ ủ
ấ ủ
c đi ti p theo h p lý
ộ ớ
ộ ớ
ừ
T các giá tr này ng
nh t.ấ
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m: (cid:0) ế ượ ự ố c đi ti p theo sau đó l a ch n n c đi t ấ
t nh t, vì
ả ọ ướ
c m i n
ấ ạ ỏ
Nh
ạ ớ ư
ọ ướ
ế
Tìm ki m đ
ậ
ạ
gi
i thu t có tính ch t vét c n nên không b soát tr ng thái.
ể
c đi m:
ố ớ
ệ ẽ ệ ậ ờ ướ
ả ữ ng…
ự
không còn hi u qu n a do s
ượ
(cid:0) Đ i v i các trò ch i có không gian tr ng thái l n nh caro, c t
i thu t Minimax có l
ớ h p quá l n.
ậ ụ ượ i thu t áp d ng nguyên lý vét c n không t n d ng đ
ạ
ọ ướ c thông tin c a
ạ ệ ế ệ ạ ể ự ủ
c đi, vì duy t h t các tr ng thái nên i đ l a ch n n
ơ
ả
ụ
ỉ
vi c ch áp d ng gi
ổ ổ ợ
bùng n t
(cid:0) Gi
ả
ụ
ậ
ạ
tr ng thái hi n t
ờ
ố
t n th i gian.
ả
ớ ắ ỉ
ậ
11. Gi
i thu t Minimax v i c t t a AlphaBeta.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ượ ậ ắ ỉ
ọ
ề
ế
c c i ti n cho đ n ngày nay. Gi ề
i thu t này th
ừ
i thu t c t t a Alphabeta t ng đ
ượ ả ế
ừ
ng và không ng ng đ
ậ ậ
ỗ ợ ả ế ằ ớ
ậ
ớ
ể
ắ ơ ơ i thu t c t t a Alphabeta có nguyên t c đ n gi n
ườ ế ả ầ ợ ấ
ả
c nhi u nhà khoa h c máy tính đ xu t ý
Gi
ưở
ườ
ả
t
ng
ử ụ
s d ng chung v i thu t toán tìm ki m Minimax nh m h tr gi m b t các
ơ
ạ
không gian tr ng thái trong cây trò ch i, giúp thu t toán Minimax có th tìm
ế
ả
ậ ắ ỉ
ả
ki m sâu và nhanh h n. Gi
ấ
ế
"N u bi ng h p x u thì không c n ph i xét thêm". t là tr
ộ ặ ằ ơ
ị ộ ị
ỏ ơ ả
ớ
ặ ằ
ị ể
ư
ượ ượ ề Nút Max có m t giá tr alpha (l n h n ho c b ng alpha – luôn tăng), nút min có
m t giá tr beta (nh h n ho c b ng beta – luôn gi m).
ế
ự
ệ
Khi ch a có alpha và beta xác đ nh thì th c hi n tìm ki m sâu (depthfirst) đ xác
ị
đ nh đ
c lên các nút cha. c alpha, beta, và truy n ng
ộ ố ệ ắ ỉ ắ ỉ ệ ớ
ơ ọ
ể ắ ỉ ộ
ề ậ
M t s sách và tài li u có đ c p v i vi c c t t a alpha và c t t a beta, dùng m t
ướ
ả
i
cách khác đó là dùng các kho ng trong toán h c. Hãy nhìn cây trò ch i phía d
ể
đ hình dung cách đ c t t a.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ả ừ ế ượ ư c đ a ra trái sang ph i ta s th y S là Max, theo chi n l
ị ạ ẽ ấ
i S.
ứ
ơ
đây là nút Min (tr ng thái trò ch i dành cho Max) t c là s l y
ư ậ ế ị ạ
ở ướ
d ẽ ấ
ả
i. N u nh v y thì giá tr chúng ta ph i
ể ễ ị
ượ
Ở ị
ệ ả ệ
c alpha và beta, chúng ta có th d dàng xác đ nh vi c có
ư ở
C
nút S (Max), giá tr alpha luôn ≥ 10 (luôn tăng) nh ng
ạ ở
i C là
ầ
ạ ỉ i nút g c ố S,
ả
ậ ầ ả ầ
Đ u tiên là xét cây t
ậ
ẽ
v y chúng ta s có giá tr alpha ≥ 10 t
ế
ở ở
C
Ti p theo,
ấ ủ
ỏ
ị
giá tr nh nh t c a các nút con
ấ
l y là beta ≤ 3.
ị
Sau khi xác đ nh đ
ắ ỉ
c t t a hay không.
ị
(Min) thì giá tr luôn luôn ≤ 3 (luôn gi m), nên vi c xét các con còn l
ế
không c n thi
t.
ế
N u nói theo kho ng thì hi n t
ậ
v y thì đâu c n b n tâm đ n vi c kho ng ≤ 3 t ả
ậ
ệ ạ
i chúng ta ch nh n kho ng ≥ 10 t
ạ
ệ
ế
i nút C.
ụ ớ ộ ơ Ví d v i m t cây trò ch i trung bình
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ố ả ắ ầ ừ nút g c và nút con bên trái
ừ
ệ ướ trái qua ph i b t đ u t
c.
ị ố ầ ư ề ồ ạ đây chúng ta cũng xét t
c u tiên duy t tr
ệ ừ
ệ ẽ ặ ố
ầ
trên g c xu ng sâu (vì ban đ u ch a h t n t
ị
ẽ ắ ầ ế ệ
ể
ẽ ọ ị
ể
đây ta s ch n cho alpha = 3 (Max).
ả ầ ượ ừ ệ ừ ả
trái sang ph i và ph i l n l
ế ế ậ
ị
ủ ệ ả ầ ị t t ng nhánh
ẽ ư
c duy t,
Khi duy t con đ u tiên mang giá tr 5 v y alpha c a
ạ ạ ầ
i F – alpha ≥ 5. Nh v y chúng ta không c n xem xét các
ả ư ậ
ỉ ạ ủ ầ ở ắ ộ đây ch là kho ng ≤ 3 nên ta c t toàn b các i c a F vì cái ta c n
ủ ệ ạ ạ Ở
ẽ ượ ư
s đ
Xét duy t t
i giá tr alpha hay
ở
ủ
beta c a các nút). Nút đ u tiên ta duy t là E s g p giá tr 2 (alpha ≥ 2), khi đó
ư
trên ch a có giá tr beta đ ta có th so sánh nên s b t đ u duy t con ti p theo
ủ
ở
c a nút E đó và
ư
L u ý là chúng ta luôn luôn duy t t
ố
ộ
m t, sau đó sang nhánh ti p theo cùng g c. V y nên ti p theo chúng ta s đ a
ệ
ẽ ượ
giá tr alpha này lên nút B (Min) và nút B – beta ≤ 3, sau đó nút F s đ
ủ
ậ
và ta ph i tìm alpha c a F.
F – alpha ≥ 5.
T i B – beta ≤ 3 và t
nút con còn l
i.ạ
con còn l
ộ
Sau khi duy t toàn b các con c a B thì t i nút A – alpha ≥ 3. i B – beta = 3, và t
Ư ể
(cid:0) ắ ỉ ể ố ư ậ i u thu t toán Minimax.
ượ u đi m:
ậ
Thu t toán c t t a Alpha Beta sinh ra đ t
ể
c đi m: Nh
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ỗ ạ ể ả ả ượ c đi m c a thu t toán minimax là m i tr ng thái b ng ph i
(cid:0) M t nh
ộ
ượ
đ
ị
giá giá tr heuristic.
ủ ứ ể ể ầ ậ
ộ ầ ậ ủ
ầ c truy c p hai l n: m t l n đ tìm con c a nó và l n th hai đ đánh
ả
ế
ậ
ố
12. Gi
i thu t tìm ki m t
ấ ầ
t nh t đ u tiên.
ậ ả ự Có 3 thu t gi i con d a vào nó:
(cid:0) ả ậ
Thu t gi i AT
(cid:0) ả ậ
Thu t gi i AKT
(cid:0) ả ậ
Thu t gi i A*
ế ủ ế ự ở ộ
ề
ủ Ư ể ị
ế ắ ụ
ố ư ẽ ế ợ
ộ
ấ ạ ng duy nh t t
ư ồ
ướ
ườ ẻ ằ ọ i u s k t h p 2
ờ
i m t th i
ế
ng khác. N u con đ
ng ta đang "quan sát" ta s ườ
ng
ẽ
ể ộ ố Ư ể
ả
u đi m c a tìm ki m theo chi u sâu là không ph i quan tâm đ n s m r ng
ế
ủ ấ ả
ề ộ
c a t
t c các nhánh. u đi m c a tìm ki m chi u r ng là không b sa vào các
ế ư
ẫ
ườ
đ
ng d n b t c (các nhánh c t). Tìm ki m u tiên t
ườ
ộ
ươ
ph
ng pháp trên cho phép ta đi theo m t con đ
ờ ẫ
ữ
ượ
ể
c nh ng h
đi m, nh ng đ ng th i v n "quan sát" đ
ữ
ể
đang đi "có v " không tri n v ng b ng nh ng con đ
ườ
ng này.
chuy n sang đi theo m t trong s các con đ
ọ ạ ế ụ ể ạ c c a tìm ki m BFS, ta ch n đi theo tr ng thái có
ờ ế ượ ộ
ả c xét cho đ n th i đi m đó.
ớ
ạ ỗ ướ ủ
ạ
ỉ ọ
ể ế ượ ừ ạ
ả
ạ
ệ ạ
tr ng thái hi n t
ả ẽ ư ữ ố
ồ ố ứ ẽ ẩ
ằ
ệ ế ế
ị ẩ
ệ
ng mà ta ch a đi, thì ta s không đi
ộ ướ ấ ố ướ
ng mà ta phát hi n ra r ng h
ư
ướ
t nh t trong s nh ng ơ ả ữ
ọ
i n a mà ch n đi theo m t h
ủ ạ ủ i m i b
M t cách c th , t
ể
ố
ấ
kh năng cao nh t trong s các tr ng thái đã đ
ồ ố ứ
ố
ấ
(khác v i leo đ i d c đ ng là ch ch n tr ng thái có kh năng cao nh t trong s
ớ ế
ư ậ
ế ế
i). Nh v y, v i ti p
c t
các tr ng thái k ti p có th đ n đ
ậ
ấ
c n này, ta s u tiên đi vào nh ng nhánh tìm ki m có kh năng nh t (gi ng tìm
ế
ki m leo đ i d c đ ng), nh ng ta s không b l n qu n trong các nhánh này vì
ế
ng này càng đi thì
n u càng đi sâu vào m t h
ẽ
càng t
ố ữ
ế ướ
ti p h
ướ
h ư
ộ ướ
ứ
ấ
, đ n m c nó x u h n c nh ng h
ệ ạ ữ
ng hi n t
ư
ng ch a đi. Đó là t ng t
ế
ng ch đ o c a tìm ki m Best First Search. ư ưở
t
Ư ể u đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
(cid:0) ậ ữ ổ
GVHD: Th.S Ngô Hồ Anh Khôi
ố
t nh t đ u tiên có th chuy n đ i gi a BFS và DFS
ữ
c nh ng l
ế
ạ ượ ấ ầ
ợ ế ủ ả ể
ậ Thu t toán tìm ki m t
ằ
b ng cách đ t đ ể
i th c a c hai thu t toán.
(cid:0) Nó hi u qu h n BFS và DFS.
ả ơ
ệ
(cid:0) Đ ph c t p th i gian c a tìm ki m đ u tiên t
ủ ế ầ ố ề ấ ơ ớ t nh t ít h n nhi u so v i
ộ ứ ạ
ầ
ế ủ ờ
tìm ki m đ u tiên c a Breadth.
(cid:0) ẫ ệ ố ọ ườ ấ ạ ờ t nh t t
ậ ề
ữ
ử ụ ứ ế
ể
i th i đi m đó. Nó
ế
ế
ậ t nh t cho phép chúng tôi t n d ng l
ầ ố ợ
t nh t,
ậ
ự ế ợ
ề ộ
ố
ấ
ớ ự ợ
ể ọ ủ
ứ ẹ ấ
ng d n xu t hi n t
thu t toán luôn ch n đ
ế
là s k t h p gi a thu t toán tìm ki m theo chi u sâu và tìm ki m theo
ầ
chi u r ng. Nó s d ng ch c năng heuristic và tìm ki m. Tìm ki m đ u
ế ủ ả
ậ ụ
i th c a c hai thu t toán.
tiên t
ế
ấ ở ỗ ướ
V i s tr giúp c a tìm ki m đ u tiên t
c, chúng ta có
m i b
ấ
th ch n nút h a h n nh t.
ượ Nh ể
c đi m:
(cid:0) Nó có th ho t đ ng nh m t tìm ki m sâu đ u tiên không có đi u ki n
ạ ộ ệ ề ầ
ể
ườ ợ ấ ế
ể ị ẹ ư ặ ộ ng h p x u nh t. Nó có th b k t trong m t vòng l p nh DFS.
trong tr
ậ
Thu t toán này không t ư ộ
ấ
ố ư
i u.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ả
ậ
13. Gi
i thu t tham lam.
ọ ể ố i thu t tham lam l a ch n gi c cho là t
th i đi m
ự ấ ở ờ
ọ ự
ậ
i và sau đó gi
ậ ự ệ c đó. Vi c
t nh t
ệ ự
vi c th c hi n l a ch n đó. L a
ướ
ệ ờ
ế ị ậ
ả ế ậ ượ
ả
ự
i pháp nào đ
ả
ừ ệ
ả
i bài toán con n y sinh t
ể ụ
ả
ộ
i thu t tham lam có th ph thu c vào l a ch n tr
ả
ủ
ớ
ng đi c a gi
i thu t cùng v i vi c không bao gi
ố ư ể
ả
ế
i u đ ọ
ớ
i thu t này không t
ổ ướ
ẽ ẫ
i các quy t đ nh cũ s d n đ n k t qu là gi
ả ụ ả
Gi
ệ ạ
hi n t
ọ ủ
ch n c a gi
ế ị
quy t đ nh s m và thay đ i h
ạ
xét l
tìm gi i pháp toàn c c.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ờ ạ
ề ư ớ ỹ
ậ
ơ
ố ớ ỹ
ậ ở ỗ ấ ỏ ơ ỹ
ụ
ướ
ộ ệ
m i c p đ đ quy kích th ậ
ố
c nh h n và s
ề ụ ẽ ễ
ậ
Phân tích th i gian ch y cho các thu t toán tham lam nói chung s d
ụ
ậ
dàng h n nhi u so v i các k thu t khác (nh Phân chia và chinh ph c).
Đ i v i k thu t Phân chia và chinh ph c, không rõ k thu t này nhanh
ề
hay ch m. Đi u này là do
ấ
ượ
l ng các v n đ ph tăng lên.
ượ Nh ể
c đi m:
ề ố ớ ạ
(cid:0) Đi u khó khăn là đ i v i các thu t toán tham lam, b n ph i làm vi c
ệ
ậ
ậ
ỉ ơ ả
ả ớ ề
ể ể
ể ứ ậ ằ
ậ ơ ệ ậ ọ ộ
ề ự ế ấ ấ
ề
chăm ch h n nhi u đ hi u các v n đ chính xác. Ngay c v i thu t toán
ộ
ứ
ạ
i sao nó đúng. Ch ng minh r ng m t
chính xác, th t khó đ ch ng minh t
ộ
thu t toán tham lam là chính xác là m t ngh thu t h n là m t khoa h c.
ạ
Nó liên quan đ n r t nhi u s sáng t o.
ả
14. Gi
ậ
i thu t A*.
ầ ượ
ể ượ ứ ọ
ư
ư ộ c xem nh là
ồ
ng đ ng nh ng có
ố ầ
Đ c công b l n đ u tiên vào năm 1968 do Peter Hart, Nils Nilsson và Bertram
ệ
ủ
Raphael c a Vi n nghiên c u khoa h c Stanford. Đây có th đ
ủ
ớ
ặ ươ
ậ
ở ộ
m t m r ng c a thu t toán Dijkstra v i các b
ở ỗ ướ
ượ
m i b
thêm thông tin l ướ
c cài đ t t
ế
c tìm ki m. ng giá (heuristic)
ả ậ ườ ệ ạ i thu t tìm ki m trong đ th , tìm đ m t t i
ế
ử ụ ỉ ng đi t
ả ồ ị
ể ướ ượ
c l ừ ộ ừ ộ ỉ
m t đ nh hi n t
ọ
ng kho ng cách hay còn g i là hàm
A* là gi
ế
đ n đ nh đích có s d ng hàm đ
Heuristic.
ệ ạ ự ể
ấ ả
i A* xây d ng t
ể ườ
ườ ể ố ừ ạ
T tr ng thái hi n t
ả
ượ
l t c các đ
c kho ng cách ( hàm Heuristic) đ đánh giá đ ng đi có th đi dùng hàm
ấ
ng đi t ướ
c
t nh t có th đi.Tùy
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ỗ ạ ẽ ượ c đánh giá khác nhau. A*
ắ theo m i d ng bài khác nhau mà hàm Heuristic s đ
ấ ế ồ ạ ườ
luôn tìm đ ng đi ng n nh t n u t n t ượ ườ
c đ i đ ư ế
ng đi nh th .
Ư ể u đi m:
ộ ả ậ ứ ả ế ổ
ữ
ướ ng c a hàm Heuristic. Chính vì th mà
(cid:0) M t thu t gi
ế
ế ờ
i gi
ườ
i ta th
ể ả ề
i linh đ ng, t ng quát, trong đó hàm ch a c tìm ki m chi u
sâu, tìm ki m chi u r ng và nh ng nguyên lý Heuristic khác.Nhanh chóng
ủ
tìm đ n l
ậ
ườ
ng ộ
ề ộ
ả ớ ự ị
i v i s đ nh h
ng nói, A* chính là thu t gi ế
i tiêu bi u cho Heuristic.
ượ Nh ể
c đi m:
(cid:0) ộ ấ ư ế ể ặ ố
ơ ả
ộ
ề ẫ
ề ộ ế ố i
ư
ộ
A* r t linh đ ng nh ng v n g p m t khuy t đi m c b n – gi ng nh
ế ượ
ớ ể ư ạ
chi n l
c tìm ki m chi u r ng – đó là t n khá nhi u b nh đ l u l
ạ
ữ
nh ng tr ng thái đã đi qua.
ấ Solution.
(cid:0) Ch a hoàn thành n u gi ể không th tìm th y
ấ ố ư ế
ề
ể
ơ Solution.
(cid:0) Nó có th không tìm th y t
i u n u có nhi u h n
ả ề ờ
ệ
ả
ấ
(cid:0) Nó không hi u qu v th i gian vì ph i m t O (b ^ L).
ế
ế
ể
ặ
ượ ử ụ
(cid:0) Nó có th gây ra các vòng l p n u tìm ki m cây đ
c s d ng trên
ể
ồ bi u đ .
ố
ế
ấ
4. Tìm ki m theo giá thành th ng nh t.
ữ ợ ư ữ ệ ư ầ ử
ỏ ấ ấ ầ ử ợ ẽ ấ
ộ ạ ứ ra kh i hàng đ i s căn c vào đ u tiên nh nh t. ườ ệ ệ ổ
ớ ộ ư cùng v i đ u tiên ộ ư ỏ ắ ử ụ ạ ầ ậ
ể ư ườ ữ
ệ ể ư ạ ữ ậ ạ ộ
Hàng đ i u tiên PQ là c u trúc d li u l u tr các ph n t ủ c a nó và khi l y ph n t ấ ng đi ng n nh t (hi n có) Cho m t tr ng thái n, ký hi u g(n) là t ng chi phí đ ợ ộ ế ừ ạ tr ng thái ban đ u S đ n tr ng thái n. Thu t toán UCS s d ng m t hàng đ i t ư ng đi. u tiên (Priority Queue – PQ) đ l u tr và duy t các tr ng thái trên đ ượ Thu t toán dùng thêm m t danh sách CLOSE đ l u tr các tr ng thái đã đ c xét.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0)
ấ
ố
ố ư
ườ
i u vì con đ
ng có chi phí
ấ ượ
ấ
ế Tìm ki m theo giá thành th ng nh t là t ọ c ch n. th p nh t đ
ượ Nh ể c đi m:
ầ
ướ
ế ố ượ ườ
ả
ậ
ế ế c liên quan đ n tìm ki m ể thu t này có th
ạ
(cid:0) Không c n quan tâm đ n s l ng các b ế ẫ ỉ và ch quan tâm đ n chi phí đ ng d n. Do đó gi ặ ộ ị ắ ẹ b m t k t trong m t vòng l p vô h n.
ầ
ế 5. Tìm ki m sâu d n.
ế ồ ị ế ế ệ ạ ậ ầ
ệ ế ặ ậ Trong trí tu nhân t o hay lý thuy t đ th , thu t toán tìm ki m ki m sâu d n là ặ ồ ị 1 thu t toán duy t ho c tìm ki m trên cây ho c đ th .
ượ ư ể
ả ằ ở ộ ế ơ ủ i n m DLS
ả ậ Thu t toán đ ộ ạ h n đ sâu ộ ạ h n đ sâu l thì gi ớ ậ ắ i c đ a ra đ kh c ph c đi m yêu c a thu t toán tìm ki m gi ớ ớ . Đó là khi mà t đ sâu l n h n gi i i gi i thu t ụ ể ờ ấ ả t c các l ẽ ấ ạ ậ DLS s th t b i.
ả ậ Gi i thu t tìm ki m sâu d n ầ s :ẽ (cid:0) ố ớ ườ i thu t (cid:0) ế ả ấ ạ ậ DLS ế ụ ộ ng đi có đ dài <= 1 ố ớ ườ ế ả ậ ộ ụ đ i v i đ áp d ng gi ụ N u th t b i, ti p t c áp d ng gi i thu t dfs đ i v i đ ng đi có đ dài
ả ặ ộ ượ ượ ờ c l i gi i ho c khi toàn b cây đã đ c
ả <= 2 ứ ư ậ (cid:0) …..c nh v y đ n khi tìm đ xét mà không tìm đ ế ượ ờ c l i gi i.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
ủ ớ ễ ệ ệ ọ
GVHD: Th.S Ngô Hồ Anh Khôi ế Luôn tìm ra nghi m (n u bài toán có nghi m), mi n là ch n max đ l n ề ộ ế (gi ng nh tìm ki m theo chi u r ng)
ư ố
ộ ứ ạ ế ờ ố ộ Có đ ph c t p th i gian là O(kd) (gi ng tìm ki m r ng)
ộ ứ ạ ế ố Có đ ph c t p không gian là O(k*d) (gi ng tìm ki m sâu)
ả ụ ầ
ế i thu t tìm ki m sâu d n th ộ ươ ệ ậ ớ ủ Gi ạ gian tr ng thái l n và đ sâu c a nghi m không bi ng áp d ng cho các bài toán có không c. ế ướ t tr
Ư ể u đi m:
(cid:0) Nó t ả
ổ ứ ề ặ ủ ệ ế ợ
i ích c a thu t toán tìm ki m BFS và DFS v m t hi u ộ ch c các l ế ớ ậ qu tìm ki m và b nh nhanh.
ủ
ế
ạ
ạ
ướ
(cid:0) H n ch chính c a IDS là nó l p l
ặ ạ ấ ả i t
ệ ủ t c các công vi c c a giai đo n tr
c.
ượ Nh ể c đi m:
ồ
ế 6. Tìm ki m leo đ i.
ồ ế ế ở ộ
ướ ế ớ
ẫ ng d n b i hàm đánh giá. ộ ỉ ề ượ ướ c h ể ứ ẹ c ti p theo ể ộ ủ ố ỉ
ượ ở ị Tìm ki m leo đ i là tìm ki m theo đ sâu đ ế Song khác v i tìm ki m theo đ sâu, khi phát tri n m t đ nh u thì b ấ ể ỉ ọ ta ch n trong s các đ nh con c a u, đ nh có h a h n nhi u nh t đ phát tri n, ỉ đ nh này đ c xác đ nh b i hàm đánh giá.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ọ ế ế ươ ướ ng pháp tìm ki m leo đ i chú tr ng tìm h
ằ
ế
ạ
ớ ế ỗ ướ i m i b ấ ể ứ ẹ ế ướ ấ
ọ c. V n đ quan tr ng là bi ẩ ả ị
ạ ế ậ ề ộ ạ c ta s u tiên ch n m t tr ng thái có h a h n ề ướ ỗ ạ ọ ế ủ ườ ế ớ t khai ng đi ti p và đ y nhanh ng ta gán m i tr ng thái c a bài toán v i
ứ ộ ầ ạ ộ ố ề ờ
ạ ề ớ ế ế ủ ể ế ạ
ặ ồ ễ ẫ ng đi d d n đ n tr ng Ph ứ ả ượ ư ấ thái đích nh t. Cách đó đ c đ a ra nh m làm gi m công s c tìm ki m. ự ấ ồ ậ Thu t toán tìm ki m leo đ i th c ch t là thu t toán tìm ki m theo chi u ẽ ư sâu, song t ể i đich nh t đ phát tri n tr nhanh t ồ ể thác kheo léo thông tin ph n h i đ xác đ nh h quá trình tìm ki m. Thông th ủ ằ m t s đo (hàm đánh giá) nào đó nh m đánh giá m c đ g n đích c a nó. ẽ ượ ệ Đi u đó có nghĩa là n u tr ng thái hi n th i là u thì tr ng thái v s đ c ị phát tri n ti p theo n u v k v i u và hàm đanh giá c a v đ t giá tr max (ho c min).
ượ Nh ể c đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ị ố ơ
ư ả ể ươ ng án t
(cid:0) C c tr đ a ph ự ị ươ ả ph i là ph ướ ể nút tr ườ ng đi. đ
ớ ạ ả ỏ ng: nút đang xét t ấ ng khác. Gi ậ t h n các nút lân c n, nh ng đó không ề ể ậ t nh t trong toàn th , ví v y có th ph i quay lui v ề ướ i nhi u i pháp này đòi h i ghi nh l ố c đ đi theo h
(cid:0) Cao nguyên: Các giá tr c a các ph
ươ ư ị ng án nh nhau, không xác đ nh
7. Simulated annealing search.
ượ ướ ố ơ ậ đ c ngay h t h n trong vùng lân c n. ị ủ ng nào là t
ự ứ ạ ạ ộ ạ (annealing process): Kim lo i ngu i đi và l nh c ng l i
ế ấ ủ D a trên quá trình tôi thành c u trúc k t tinh
ể ượ ể ố ư ng pháp tìm ki m Simulated Annealing có th tránh đ c các đi m t i u
ế ươ Ph ụ ộ c c b (local optima)
ươ ử ụ ế ng pháp tìm ki m Simulated Annealing s d ng chi n l
ế c tìm ki m ng u ầ ự ấ ậ ổ ị
ế ượ ụ ả ấ ậ ạ ổ ẫ Ph nhiên, trong đó ch p nh n các thay đ i làm tăng giá tr hàm m c tiêu (c n c c ế ạ đ i hóa) và cũng ch p nh n (có h n ch ) các thay đ i làm gi m
ố ề ử ụ ể ộ ng pháp tìm ki m Simulated Annealing s d ng m t tham s đi u khi n T
ế ệ ố ươ ư Ph (nh trong các h th ng nhi ệ ộ t đ )
ắ ầ ề ậ ả ầ ị ❑ B t đ u thì T nh n giá tr cao, và gi m d n v 0
ượ
ỏ ồ ừ ạ ố ư ụ ộ ằ t qua) các đi m t ờ ể ệ ấ ủ ư ả ả i u c c b b ng cách cho phép c ầ ầ tr ng thái hi n th i, nh ng gi m d n t n xu t c a các
ưở ng: Thoát kh i (v Ý t ể ị i” t các d ch chuy n “t ể ồ i này di chuy n t
ứ ộ ả ượ ị
ể ứ ấ ố ớ
ấ ấ ẽ ố ị ủ ế ầ c) N u giá tr c a tham s T (xác đ nh m c đ gi m t n (Có th ch ng minh đ ế ươ ả ậ ể ồ xu t đ i v i các di chuy n t ng pháp tìm ki m Simulated i) gi m ch m, thì ph ỉ ụ ớ ả ố ư i u toàn c c v i xác su t x p x 1 i t i gi Annealing s tìm đ ượ ờ c l
ươ ế ấ ượ ử ụ ng pháp tìm ki m Simulated Annealing Search r t hay đ c s d ng trong
ự ế ế ơ ồ ả ậ ị ạ Ph các lĩnh v c: thi t k s đ b ng m ch VLSI, l p l ch bay, …
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ế ớ
ộ ỹ ạ ậ ỗ ộ
ữ ệ ẽ ạ ể ố Simulated annealing search có th đ i phó v i các mô hình phi tuy n tính ề ồ cao, d li u h n lo n và n ào và nhi u ràng bu c. Đó là m t k thu t m nh m và chung chung.
(cid:0) ươ ủ ớ ị ươ ng khác
u đi m chính c a nó so v i các ph ế ậ ạ ả Ư ể là tính linh ho t và kh năng ti p c n toàn c u s t ế ng pháp tìm ki m đ a ph ầ ự ố ư i u.
(cid:0) ậ ấ ỳ ự ạ ạ ộ
ế Thu t toán này khá linh ho t vì nó không d a trên b t k thu c tính h n ủ ch nào c a mô hình.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
(cid:0) M t b t l
ượ Nh ể c đi m:
i
ỏ ủ ộ ấ ợ Simulated annealing search là chuyên sâu tính toán. Có t n ồ i các bi n th c b n nhanh h n mô ph ng
ể ơ ả ễ , nh ng rõ ràng chúng ượ ử ụ ế ượ ậ ộ ư ơ c mã hóa d dàng và vì v y chúng không đ c s d ng r ng
ạ t không đ rãi.
ế 8. Tìm ki m Beam
ề ộ ể ố
ậ i thu t tìm ki m beam gi ng nh tìm ki m theo chi u r ng, nó phát tri n các ở ộ ế ở ứ ế ế ứ ồ ư ỉ ể ả Gi ỉ đ nh m t m c r i phát tri n các đ nh m c ti p theo.
ể ấ ả m t
ề ộ ạ ế ỉ ể
ượ ế ị
ỉ ứ ố ỉ ề ộ ỉ ở ộ t c các đ nh ấ ố ỉ t nh t(các đ nh ở ấ b t kì m c c xác đ nh b i hàm đánh giá). Do đó trong tìm ki m beam, ế c phát tri n, trong khi tìm ki m theo chi u r ng, s đ nh
ố ế Tuy nhiên trong tìm ki m theo chi u r ng, ta phát tri n t ế ứ m c, còn trong tìm ki m beam, ta h n ch ch phát tri n đ nh K t ở này đ ỉ ượ nào cũng có K đ nh đ ể ở ứ ầ m c d là b c n phát tri n ể d (b là nhân t t nhánh).
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ế ả ả ợ i th là có kh năng làm gi m tính toán, và do đó,
ớ ủ ờ ồ
ụ ộ ơ ả ủ ứ ế ủ ề ộ ớ ươ ơ ế Tìm ki m beam có l ế ờ ế th i gian c a m t tìm ki m. Đ ng th i, m c tiêu th b nh c a tìm ki m ít h n nhi u so v i các ph ng pháp tìm ki m c b n c a nó.
ượ Nh ể c đi m:
ế ể ẫ
ụ ể ế i u và th m chí có th không đ t đ
ủ ậ ế ạ ượ ậ ợ ế c đi m chính c a tìm ki m beam là tìm ki m có th không d n đ n ự c m c tiêu. Trong th c ườ c nút ng h p: đ t đ
ứ ấ ạ ượ ặ ắ c nút m c tiêu và không còn nút
(cid:0) Nh ể ượ ụ ạ ượ ố ư m c tiêu t ế , thu t toán tìm ki m chùm ch m d t cho hai tr t ụ ộ ụ m c tiêu b t bu c ho c không đ t đ nào đ khám phá.
ể
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ế
ậ
9. Tìm ki m nhánh c n.
ươ ố ư ổ ợ ệ i các bài toán t ng pháp ch y u đ gi i u t
ừ ủ ế ướ ể ả ế ế ả
ế
ẽ ố ầ ệ ậ
ủ ị ệ ờ ủ ậ ạ ệ ự Là ph h p. Ta th c hi n vi c ẽ ả ố ơ ấ t h n thì r c, n u không có kh năng tìm th y k t qu t đánh giá theo t ng b ể ệ ự ỉ nhánh nó, không th c hi n tìm ti p mà chuy n ngay sang nhánh khác. Khi đó, ch ầ ả ố ơ ế ầ t d n c n ghi nh n các k t qu t ả ố ơ ế i giá tr hi n th i c a bài toán. lên do khi tìm ra k t qu t t h n lúc ban đ u. Nghi m c a bài toán s t ẽ ậ t h n ta s c p nh t l
ả ế ủ ộ ạ ươ ng pháp quay lui dùng
ế ươ Ph ể ả đ gi ậ ng pháp Nhánh c n là m t d ng c i ti n c a ph i quy t bài toán t ố ư . i u
Ư ể u đi m:
(cid:0) ươ ệ ể ậ ộ ng pháp nhánh c n không quét qua toàn b các nghi m có th có
Ph ủ c a bài toán .
ượ Nh ể c đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
(cid:0) Khó khăn c a ph
ượ ế ậ
ề ế ệ c các ầ t s b nhi u nghi m không c n
ế ả ươ ủ ng pháp nhánh c n là làm th nào đánh giá đ ệ ố ẽ ỏ ậ ở ộ nghi m m r ng (c n). N u đánh giá t t ph i xét (nhánh) thi .
ả
ậ
10. Gi
i thu t Minimax.
ậ ệ ọ ướ ậ i thu t Minimax là m t thu t toán đ quy l a ch n b
ườ ườ
ờ ộ ư ờ ơ ố ờ ướ c đi c a mình nh c vua, c t
ủ ế ờ ư ộ ế ế ự c đi k ti p trong i thay i. Xét m t trò ch i đ i kháng trong đó hai ng ơ ng, c caro, c vây… Khi ch i ạ
ượ ủ ố ế ả ứ
ả ử ố ư ế ế ủ ể c ph n ng và n ạ
ố ả ế ụ ứ ề ể ướ ủ ủ ạ ậ thuy t này đ tìm ủ ử ụ s đ i th c a b n cũng s d ng ki n th c v không i thu t Minimax áp d ng gi
ấ ậ ượ ướ c b
ằ ế ế ế ố c đi k ti p t ế ể
ị ạ ố t nh t ế c ti p
ế ạ ơ ị ể
ơ ượ ọ ố
ế ư ườ ạ ợ i quy t dành th ng l
ố ố ắ i và c g ng t ạ ố ắ ườ i ng
ả ố ể thi
ế i đa hóa u th ố ả i c g ng gi m đi m s ế t t. Gi ơ ế ề ạ
ố
ứ ơ
ủ ế
ể ệ ậ ơ ị ị
ị
ơ ẽ ự ướ ườ ế ợ ị ả Gi ơ ộ m t trò ch i có hai ng ướ phiên đi n ạ ể ạ b n có th khai tri n h t không gian tr ng thái nh ng khó khăn ch y u là b n ả c đi c a đ i th mình nh th nào? Cách ph i tính toán đ ơ ả ử x lý đ n gi n là b n gi ả ạ ạ gian tr ng thái gi ng b n. Gi ơ ủ ạ ế ki m không gian tr ng thái c a trò ch i. ả t nh t trong các Gi i thu t Minimax giúp chúng ta tìm đ ạ không gian tr ng thái ti p theo b ng cách phát tri n h t không gian tr ng thái ấ ở ướ b cây trò ch i đ nh giá tr cho các Node tìm Node có tr ng thái t theo phát tri n ti p. ủ c g i là MIN và MAX luân phiên thay th nhau đi. Hai đ i th trong trò ch i đ ắ ế ệ MAX đ i di n cho ng ệ ơ ạ ượ ạ ủ i ch i đ i di n cho MIN l c l c a mình, ng ố ủ ể ố ắ ủ c a MAX và c g ng làm cho đi m s c a mình càng âm càng t ư ứ ư đ a ra MIN và MAX có ki n th c nh nhau v không gian tr ng thái trò ch i và ư ủ ề ố ắ ả c hai đ i th đ u c g ng nh nhau. ộ ạ ễ ể ỗ M i Node bi u di n cho m t tr ng thái trên cây trò ch i. Node lá là Node ch a ạ ơ tr ng thái k t thúc c a trò ch i. ằ ả i thu t Minimax th hi n b ng cách đ nh tr các Node trên cây trò ch i: Gi ị ớ (cid:0) Node thu c l p MAX thì gán cho nó giá tr l n nh t c a con Node đó. ỏ (cid:0) Node thu c l p MIN thì gán cho nó giá tr nh nh t c a con Node đó. ọ i ch i s l a ch n cho mình n ấ ủ ấ ủ c đi ti p theo h p lý
ộ ớ ộ ớ ừ T các giá tr này ng nh t.ấ
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m: (cid:0) ế ượ ự ố c đi ti p theo sau đó l a ch n n c đi t ấ t nh t, vì
ả ọ ướ c m i n ấ ạ ỏ
Nh
ạ ớ ư
ọ ướ ế Tìm ki m đ ậ ạ gi i thu t có tính ch t vét c n nên không b soát tr ng thái. ể c đi m: ố ớ ệ ẽ ệ ậ ờ ướ ả ữ ng… ự không còn hi u qu n a do s
ượ (cid:0) Đ i v i các trò ch i có không gian tr ng thái l n nh caro, c t i thu t Minimax có l ớ h p quá l n.
ậ ụ ượ i thu t áp d ng nguyên lý vét c n không t n d ng đ
ạ ọ ướ c thông tin c a ạ ệ ế ệ ạ ể ự ủ c đi, vì duy t h t các tr ng thái nên i đ l a ch n n
ơ ả ụ ỉ vi c ch áp d ng gi ổ ổ ợ bùng n t (cid:0) Gi ả ụ ậ ạ tr ng thái hi n t ờ ố t n th i gian.
ả
ớ ắ ỉ
ậ
11. Gi
i thu t Minimax v i c t t a AlphaBeta.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ượ ậ ắ ỉ
ọ ề ế c c i ti n cho đ n ngày nay. Gi ề i thu t này th
ừ i thu t c t t a Alphabeta t ng đ ượ ả ế ừ ng và không ng ng đ ậ ậ ỗ ợ ả ế ằ ớ
ậ
ớ ể ắ ơ ơ i thu t c t t a Alphabeta có nguyên t c đ n gi n
ườ ế ả ầ ợ ấ ả c nhi u nhà khoa h c máy tính đ xu t ý Gi ưở ườ ả t ng ử ụ s d ng chung v i thu t toán tìm ki m Minimax nh m h tr gi m b t các ơ ạ không gian tr ng thái trong cây trò ch i, giúp thu t toán Minimax có th tìm ế ả ậ ắ ỉ ả ki m sâu và nhanh h n. Gi ấ ế "N u bi ng h p x u thì không c n ph i xét thêm". t là tr
ộ ặ ằ ơ
ị ộ ị ỏ ơ ả
ớ ặ ằ ị ể
ư ượ ượ ề Nút Max có m t giá tr alpha (l n h n ho c b ng alpha – luôn tăng), nút min có m t giá tr beta (nh h n ho c b ng beta – luôn gi m). ế ự ệ Khi ch a có alpha và beta xác đ nh thì th c hi n tìm ki m sâu (depthfirst) đ xác ị đ nh đ c lên các nút cha. c alpha, beta, và truy n ng
ộ ố ệ ắ ỉ ắ ỉ ệ ớ
ơ ọ
ể ắ ỉ ộ ề ậ M t s sách và tài li u có đ c p v i vi c c t t a alpha và c t t a beta, dùng m t ướ ả i cách khác đó là dùng các kho ng trong toán h c. Hãy nhìn cây trò ch i phía d ể đ hình dung cách đ c t t a.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ả ừ ế ượ ư c đ a ra trái sang ph i ta s th y S là Max, theo chi n l
ị ạ ẽ ấ i S.
ứ
ơ đây là nút Min (tr ng thái trò ch i dành cho Max) t c là s l y ư ậ ế ị ạ ở ướ d ẽ ấ ả i. N u nh v y thì giá tr chúng ta ph i
ể ễ ị
ượ Ở ị
ệ ả ệ c alpha và beta, chúng ta có th d dàng xác đ nh vi c có ư ở C nút S (Max), giá tr alpha luôn ≥ 10 (luôn tăng) nh ng ạ ở i C là
ầ
ạ ỉ i nút g c ố S,
ả ậ ầ ả ầ Đ u tiên là xét cây t ậ ẽ v y chúng ta s có giá tr alpha ≥ 10 t ế ở ở C Ti p theo, ấ ủ ỏ ị giá tr nh nh t c a các nút con ấ l y là beta ≤ 3. ị Sau khi xác đ nh đ ắ ỉ c t t a hay không. ị (Min) thì giá tr luôn luôn ≤ 3 (luôn gi m), nên vi c xét các con còn l ế không c n thi t. ế N u nói theo kho ng thì hi n t ậ v y thì đâu c n b n tâm đ n vi c kho ng ≤ 3 t ả ậ ệ ạ i chúng ta ch nh n kho ng ≥ 10 t ạ ệ ế i nút C.
ụ ớ ộ ơ Ví d v i m t cây trò ch i trung bình
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ố ả ắ ầ ừ nút g c và nút con bên trái
ừ ệ ướ trái qua ph i b t đ u t c.
ị ố ầ ư ề ồ ạ đây chúng ta cũng xét t c u tiên duy t tr ệ ừ
ệ ẽ ặ ố ầ
trên g c xu ng sâu (vì ban đ u ch a h t n t ị ẽ ắ ầ ế ệ
ể ẽ ọ ị ể đây ta s ch n cho alpha = 3 (Max).
ả ầ ượ ừ ệ ừ ả trái sang ph i và ph i l n l
ế ế ậ
ị
ủ ệ ả ầ ị t t ng nhánh ẽ ư c duy t, Khi duy t con đ u tiên mang giá tr 5 v y alpha c a
ạ ạ ầ
i F – alpha ≥ 5. Nh v y chúng ta không c n xem xét các ả ư ậ ỉ ạ ủ ầ ở ắ ộ đây ch là kho ng ≤ 3 nên ta c t toàn b các i c a F vì cái ta c n
ủ ệ ạ ạ Ở ẽ ượ ư s đ Xét duy t t i giá tr alpha hay ở ủ beta c a các nút). Nút đ u tiên ta duy t là E s g p giá tr 2 (alpha ≥ 2), khi đó ư trên ch a có giá tr beta đ ta có th so sánh nên s b t đ u duy t con ti p theo ủ ở c a nút E đó và ư L u ý là chúng ta luôn luôn duy t t ố ộ m t, sau đó sang nhánh ti p theo cùng g c. V y nên ti p theo chúng ta s đ a ệ ẽ ượ giá tr alpha này lên nút B (Min) và nút B – beta ≤ 3, sau đó nút F s đ ủ ậ và ta ph i tìm alpha c a F. F – alpha ≥ 5. T i B – beta ≤ 3 và t nút con còn l i.ạ con còn l ộ Sau khi duy t toàn b các con c a B thì t i nút A – alpha ≥ 3. i B – beta = 3, và t
Ư ể
(cid:0) ắ ỉ ể ố ư ậ i u thu t toán Minimax.
ượ u đi m: ậ Thu t toán c t t a Alpha Beta sinh ra đ t ể c đi m: Nh
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ỗ ạ ể ả ả ượ c đi m c a thu t toán minimax là m i tr ng thái b ng ph i
(cid:0) M t nh ộ ượ đ ị giá giá tr heuristic.
ủ ứ ể ể ầ ậ ộ ầ ậ ủ ầ c truy c p hai l n: m t l n đ tìm con c a nó và l n th hai đ đánh
ả
ế
ậ
ố
12. Gi
i thu t tìm ki m t
ấ ầ t nh t đ u tiên.
ậ ả ự Có 3 thu t gi i con d a vào nó:
(cid:0) ả ậ Thu t gi i AT
(cid:0) ả ậ Thu t gi i AKT
(cid:0) ả ậ Thu t gi i A*
ế ủ ế ự ở ộ
ề ủ Ư ể ị
ế ắ ụ
ố ư ẽ ế ợ ộ ấ ạ ng duy nh t t
ư ồ
ướ ườ ẻ ằ ọ i u s k t h p 2 ờ i m t th i ế ng khác. N u con đ ng ta đang "quan sát" ta s ườ ng ẽ
ể ộ ố Ư ể ả u đi m c a tìm ki m theo chi u sâu là không ph i quan tâm đ n s m r ng ế ủ ấ ả ề ộ c a t t c các nhánh. u đi m c a tìm ki m chi u r ng là không b sa vào các ế ư ẫ ườ đ ng d n b t c (các nhánh c t). Tìm ki m u tiên t ườ ộ ươ ph ng pháp trên cho phép ta đi theo m t con đ ờ ẫ ữ ượ ể c nh ng h đi m, nh ng đ ng th i v n "quan sát" đ ữ ể đang đi "có v " không tri n v ng b ng nh ng con đ ườ ng này. chuy n sang đi theo m t trong s các con đ
ọ ạ ế ụ ể ạ c c a tìm ki m BFS, ta ch n đi theo tr ng thái có
ờ ế ượ ộ ả c xét cho đ n th i đi m đó.
ớ
ạ ỗ ướ ủ ạ ỉ ọ ể ế ượ ừ ạ
ả ạ ệ ạ tr ng thái hi n t ả ẽ ư ữ ố
ồ ố ứ ẽ ẩ
ằ
ệ ế ế ị ẩ ệ ng mà ta ch a đi, thì ta s không đi
ộ ướ ấ ố ướ ng mà ta phát hi n ra r ng h ư ướ t nh t trong s nh ng ơ ả ữ ọ i n a mà ch n đi theo m t h
ủ ạ ủ i m i b M t cách c th , t ể ố ấ kh năng cao nh t trong s các tr ng thái đã đ ồ ố ứ ố ấ (khác v i leo đ i d c đ ng là ch ch n tr ng thái có kh năng cao nh t trong s ớ ế ư ậ ế ế i). Nh v y, v i ti p c t các tr ng thái k ti p có th đ n đ ậ ấ c n này, ta s u tiên đi vào nh ng nhánh tìm ki m có kh năng nh t (gi ng tìm ế ki m leo đ i d c đ ng), nh ng ta s không b l n qu n trong các nhánh này vì ế ng này càng đi thì n u càng đi sâu vào m t h ẽ càng t ố ữ ế ướ ti p h ướ h ư ộ ướ ứ ấ , đ n m c nó x u h n c nh ng h ệ ạ ữ ng hi n t ư ng ch a đi. Đó là t ng t ế ng ch đ o c a tìm ki m Best First Search. ư ưở t
Ư ể u đi m:
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
(cid:0) ậ ữ ổ
GVHD: Th.S Ngô Hồ Anh Khôi ố t nh t đ u tiên có th chuy n đ i gi a BFS và DFS ữ c nh ng l
ế ạ ượ ấ ầ ợ ế ủ ả ể ậ Thu t toán tìm ki m t ằ b ng cách đ t đ ể i th c a c hai thu t toán.
(cid:0) Nó hi u qu h n BFS và DFS. ả ơ
ệ
(cid:0) Đ ph c t p th i gian c a tìm ki m đ u tiên t
ủ ế ầ ố ề ấ ơ ớ t nh t ít h n nhi u so v i
ộ ứ ạ ầ ế ủ ờ tìm ki m đ u tiên c a Breadth.
(cid:0) ẫ ệ ố ọ ườ ấ ạ ờ t nh t t
ậ ề
ữ ử ụ ứ ế
ể i th i đi m đó. Nó ế ế ậ t nh t cho phép chúng tôi t n d ng l
ầ ố ợ t nh t,
ậ ự ế ợ ề ộ ố ấ ớ ự ợ ể ọ ủ ứ ẹ ấ ng d n xu t hi n t thu t toán luôn ch n đ ế là s k t h p gi a thu t toán tìm ki m theo chi u sâu và tìm ki m theo ầ chi u r ng. Nó s d ng ch c năng heuristic và tìm ki m. Tìm ki m đ u ế ủ ả ậ ụ i th c a c hai thu t toán. tiên t ế ấ ở ỗ ướ V i s tr giúp c a tìm ki m đ u tiên t c, chúng ta có m i b ấ th ch n nút h a h n nh t.
ượ Nh ể c đi m:
(cid:0) Nó có th ho t đ ng nh m t tìm ki m sâu đ u tiên không có đi u ki n
ạ ộ ệ ề ầ
ể ườ ợ ấ ế ể ị ẹ ư ặ ộ ng h p x u nh t. Nó có th b k t trong m t vòng l p nh DFS.
trong tr ậ Thu t toán này không t ư ộ ấ ố ư i u.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ả
ậ
13. Gi
i thu t tham lam.
ọ ể ố i thu t tham lam l a ch n gi c cho là t
th i đi m ự ấ ở ờ ọ ự
ậ i và sau đó gi ậ ự ệ c đó. Vi c
t nh t ệ ự vi c th c hi n l a ch n đó. L a ướ ệ ờ
ế ị ậ ả ế ậ ượ ả ự i pháp nào đ ả ừ ệ ả i bài toán con n y sinh t ể ụ ả ộ i thu t tham lam có th ph thu c vào l a ch n tr ả ủ ớ ng đi c a gi i thu t cùng v i vi c không bao gi ố ư ể ả ế i u đ ọ ớ i thu t này không t
ổ ướ ẽ ẫ i các quy t đ nh cũ s d n đ n k t qu là gi ả ụ ả Gi ệ ạ hi n t ọ ủ ch n c a gi ế ị quy t đ nh s m và thay đ i h ạ xét l tìm gi i pháp toàn c c.
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
Ư ể u đi m:
(cid:0) ờ ạ
ề ư ớ ỹ
ậ
ơ ố ớ ỹ ậ ở ỗ ấ ỏ ơ ỹ ụ ướ ộ ệ m i c p đ đ quy kích th ậ ố c nh h n và s
ề ụ ẽ ễ ậ Phân tích th i gian ch y cho các thu t toán tham lam nói chung s d ụ ậ dàng h n nhi u so v i các k thu t khác (nh Phân chia và chinh ph c). Đ i v i k thu t Phân chia và chinh ph c, không rõ k thu t này nhanh ề hay ch m. Đi u này là do ấ ượ l ng các v n đ ph tăng lên.
ượ Nh ể c đi m:
ề ố ớ ạ
(cid:0) Đi u khó khăn là đ i v i các thu t toán tham lam, b n ph i làm vi c ệ ậ ậ
ỉ ơ ả ả ớ ề
ể ể ể ứ ậ ằ
ậ ơ ệ ậ ọ ộ
ề ự ế ấ ấ ề chăm ch h n nhi u đ hi u các v n đ chính xác. Ngay c v i thu t toán ộ ứ ạ i sao nó đúng. Ch ng minh r ng m t chính xác, th t khó đ ch ng minh t ộ thu t toán tham lam là chính xác là m t ngh thu t h n là m t khoa h c. ạ Nó liên quan đ n r t nhi u s sáng t o.
ả
14. Gi
ậ i thu t A*.
ầ ượ
ể ượ ứ ọ
ư ư ộ c xem nh là ồ ng đ ng nh ng có
ố ầ Đ c công b l n đ u tiên vào năm 1968 do Peter Hart, Nils Nilsson và Bertram ệ ủ Raphael c a Vi n nghiên c u khoa h c Stanford. Đây có th đ ủ ớ ặ ươ ậ ở ộ m t m r ng c a thu t toán Dijkstra v i các b ở ỗ ướ ượ m i b thêm thông tin l ướ c cài đ t t ế c tìm ki m. ng giá (heuristic)
ả ậ ườ ệ ạ i thu t tìm ki m trong đ th , tìm đ m t t i
ế ử ụ ỉ ng đi t ả ồ ị ể ướ ượ c l ừ ộ ừ ộ ỉ m t đ nh hi n t ọ ng kho ng cách hay còn g i là hàm
A* là gi ế đ n đ nh đích có s d ng hàm đ Heuristic.
ệ ạ ự ể
ấ ả i A* xây d ng t ể ườ ườ ể ố ừ ạ T tr ng thái hi n t ả ượ l t c các đ c kho ng cách ( hàm Heuristic) đ đánh giá đ ng đi có th đi dùng hàm ấ ng đi t ướ c t nh t có th đi.Tùy
Tìm hiểu một số giải thuật môn học Trí Tuệ Nhân Tạo
GVHD: Th.S Ngô Hồ Anh Khôi
ỗ ạ ẽ ượ c đánh giá khác nhau. A*
ắ theo m i d ng bài khác nhau mà hàm Heuristic s đ ấ ế ồ ạ ườ luôn tìm đ ng đi ng n nh t n u t n t ượ ườ c đ i đ ư ế ng đi nh th .
Ư ể u đi m:
ộ ả ậ ứ ả ế ổ
ữ ướ ng c a hàm Heuristic. Chính vì th mà
(cid:0) M t thu t gi ế ế ờ i gi ườ i ta th
ể ả ề i linh đ ng, t ng quát, trong đó hàm ch a c tìm ki m chi u sâu, tìm ki m chi u r ng và nh ng nguyên lý Heuristic khác.Nhanh chóng ủ tìm đ n l ậ ườ ng ộ ề ộ ả ớ ự ị i v i s đ nh h ng nói, A* chính là thu t gi ế i tiêu bi u cho Heuristic.
ượ Nh ể c đi m:
(cid:0) ộ ấ ư ế ể ặ ố
ơ ả ộ ề ẫ ề ộ ế ố i
ư ộ A* r t linh đ ng nh ng v n g p m t khuy t đi m c b n – gi ng nh ế ượ ớ ể ư ạ chi n l c tìm ki m chi u r ng – đó là t n khá nhi u b nh đ l u l ạ ữ nh ng tr ng thái đã đi qua.
