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.ế ề ộ
Tìm ki m theo chi u r ng (BFS) là m t thu t toán tìm ki m trong đ th trong ế ề ộ ộ ậ ế ồ ị
đó vi c tìm ki m ch bao g m 2 thao tác: (a) cho tr c m t đnh c a đ th ; (b) ệ ế ỉ ồ ướ ộ ỉ ủ ồ ị
thêm các đnh k v i đnh v a cho vào danh sách có th h ng t i ti p theo. Có ỉ ề ớ ỉ ừ ể ướ ớ ế
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 m t đnh g c cho tr c t i m t đnh đích, và tìm ki m đng đi t ườ ừ ộ ỉ ố ướ ớ ộ ỉ ế ườ ừ
đnh g c t i t t c các đnh khác. Trong đ th không có tr ng s , thu t toán tìm ỉ ố ớ ấ ả ỉ ồ ị ọ ố ậ
ki m theo chi u r ng luôn tìm ra đng đi ng n nh t có th . Thu t toán BFS ế ề ộ ườ ắ ấ ể ậ
b t đu t đnh g c và l n l t nhìn các đnh k v i đnh g c. Sau đó, v i m i ắ ầ ừ ỉ ố ầ ượ ỉ ề ớ ỉ ố ớ ỗ
đnh trong s đó, thu t toán l i l n l t nhìn tr c các đnh k v i nó mà ch a ỉ ố ậ ạ ầ ượ ướ ỉ ề ớ ư
đc quan sát tr c đó và l p l i. Xem thêm thu t toán tìm ki m theo chi u sâu,ượ ướ ặ ạ ậ ế ề
trong đó cũng s d ng 2 thao tác trên nh ng có trình t quan sát các đnh khác ử ụ ư ự ỉ
v i thu t toán tìm ki m theo chi u r ng.ớ ậ ế ề ộ
gi i thu t tìm ki m theo chi u r ng duy t t A t i B t i E t i F sau đó t i C,ả ậ ế ề ộ ệ ừ ớ ớ ớ ớ
t i G và cu i cùng t i D. Gi i thu t này tuân theo qui t c:ớ ố ớ ả ậ ắ
Qui t c 1ắ: Duy t ti p t i đnh li n k mà ch a đc duy t. Đánh d uệ ế ớ ỉ ề ề ư ượ ệ ấ
đnh mà đã đ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.ợ
Qui t c 3ắ: L p l i Qui t c 1 và 2 cho t i khi hàng đi là tr ng.ặ ạ ắ ớ ợ ố
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:Ứ ụ
Thu t toán tìm ki m theo chi u r ng đc dùng đ gi i nhi u bài toán trong lý ậ ế ề ộ ượ ể ả ề
thuy t đ th , ch ng h n nh :ế ồ ị ẳ ạ ư
Tìm t t c các đnh trong m t thành ph n liên thôngấ ả ỉ ộ ầ
Tìm đng đi ng n nh t gi a hai đnh u và v (v i chi u dài đng đi tính ườ ắ ấ ữ ỉ ớ ề ườ
b ng s cung)ằ ố
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:Ư ể
Xét duy t t t c các đnh đ tr v k t qu .ệ ấ ả ỉ ể ả ề ế ả
N u s đnh là h u h n, thu t toán ch c ch n tìm ra k t qu .ế ố ỉ ữ ạ ậ ắ ắ ế ả
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
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.ớ
Mang tính ch t mù quáng, duy t t t c đnh, không chú ý đn thông ấ ệ ấ ả ỉ ế
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.ế ề
Gi i thu t tìm ki m theo chi u sâu (Depth First Search – vi t t t là DFS), còn ả ậ ế ề ế ắ
đc g i là gi 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 ượ ọ ả ậ ế ư ề ả ậ ệ ặ
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 ế ộ ặ ộ ồ ị ử ụ ế ể ớ ỉ
li n k đ b t đu vi c tìm ki m khi không g p đc đnh li n k trong b t kề ề ể ắ ầ ệ ế ặ ượ ỉ ề ề ấ ỳ
vòng l p nào. Gi i thu t ti p t c cho t i khi g p đc đnh c n tìm ho c t i ặ ả ậ ế ụ ớ ặ ượ ỉ ầ ặ ớ
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.ướ ướ
Trong hình minh h a trên, gi i thu t tìm ki m theo chi u sâu đu tiên duy t tọ ả ậ ế ề ầ ệ ừ
các đnhỉ A t iớ B t iớ C t iớ D sau đó t iớ E, sau đó t iớ F và cu i cùng t iố ớ G. Gi iả
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
Qui t c 1ắ: Duy t ti p t i đnh li n k mà ch a đc duy t. Đánh d uệ ế ớ ỉ ề ề ư ượ ệ ấ
đnh mà đã đ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ế ấ ỉ ề ề ấ ộ ỉ ừ
ngăn x p (thao tác pop up). (Gi i thu t s l y t t c các đnh t trong ngăn x pế ả ậ ẽ ấ ấ ả ỉ ừ ế
mà không có các đnh li n k nào)ỉ ề ề
Qui t c 3ắ: L p l i các qui t c 1 và qui t c 2 cho t i khi ngăn x p là tr ng.ặ ạ ắ ắ ớ ế ố
u đi m:Ư ể
Xét duy t t t c các đnhđ tr v k t qu .ệ ấ ả ỉ ể ả ề ế ả
N u s đnh là h u h n, thu t toán ch c ch n tìm ra k t qu .ế ố ỉ ữ ạ ậ ắ ắ ế ả
Nh c đi m:ượ ể
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.ấ ạ ụ ế ệ ố ỉ ớ
Mang tính ch t mù quáng, duy t t t c đnh, không chú ý đn thông 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.ế
3. Tìm ki m theo chi u sâu có gi 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 i h n ệ ạ ế ồ ị ậ ế ớ ạ
đ sâu (DLS)ộ hay depth-limited search algorithm là m t thu t toán phát tri n các ộ ậ ể
nút ch a xét các theo chi u sâu nh ng có gi i h n m c đ tránh đi vào nh ng ư ề ư ớ ạ ứ ể ữ
con đng không mang l i k t qu t t nh trong thu t toán tìm ki m sâu d n.ườ ạ ế ả ố ư ậ ế ầ
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
Nó là b nh hi u qu , s d ng không gian tuy n tính O (bxL)ộ ớ ệ ả ử ụ ế
Nh c đi m:ượ ể
Ch a hoàn thành n u gi i pháp n m d i gi i h n L(d <l), vì nó ư ế ả ằ ướ ớ ạ
không th tìm th y ể ấ Solution.
Nó có th không tìm th y t i u n u có nhi u h n ể ấ ố ư ế ề ơ Solution.
Nó không hi u qu v th i gian vì ph i m t O (b ^ L).ệ ả ề ờ ả ấ
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.ế ố ấ
Hàng đi u tiên PQ là c u trúc d li u l u tr các ph n t cùng v i đ u tiên ợ ư ấ ữ ệ ư ữ ầ ử ớ ộ ư
c a nó và khi l y ph n t ra kh i hàng đi s căn c vào đ u tiên nh nh t.ủ ấ ầ ử ỏ ợ ẽ ứ ộ ư ỏ ấ
Cho m t tr ng thái n, ký hi u g(n) là t ng chi phí đng đi ng n nh t (hi n có) ộ ạ ệ ổ ườ ắ ấ ệ
t 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 ừ ạ ầ ế ạ ậ ử ụ ộ ợ
u tiên (Priority Queue – PQ) đ l u tr và duy t các tr ng thái trên đng đi. ư ể ư ữ ệ ạ ườ
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.