Xem mẫu
- Cách đánh giá
TRÍ TUỆ NHÂN TẠO
Thực hành: 30%
Bài tập: 20%
ThS. Nguyễn Thị Thúy Loan Lý thuyết: 50%
6/8/2010 Nguyễn Thị Thúy Loan 2
Tài liệu tham khảo
[1]. Bài giảng của Nguyễn Thị Thúy Loan
NỘI DUNG
[2]. Trí tuệ nhân tạo, Đỗ Trung Tuấn, NXB Giáo
dục, 1998. Các thuật giải tô màu đồ thị.
[3]. Bạch Hưng Khang – Hoàng Kiếm, Trí tuệ nhân Các thuật giải tìm kiếm trên đồ thị.
tạo, NXB KHKT - 1989.
[4]. Lập trình C cho TTNT, 3C soft (dịch), NXB Đại
Biểu diễn và xử lý tri thức.
học và Trung học chuyên nghiệp Hà nội – Phân lớp.
1990.
[5]. Trang web
http://ocw.mit.edu/OcwWeb/Electrical-
Engineering-and-Computer-Science/index.htm
6/8/2010 Nguyễn Thị Thúy Loan 3 6/8/2010 Nguyễn Thị Thúy Loan 4
- Chương I Bài toán
Cho một đồ thị gồm n đỉnh. Quan hệ giữa
CÁC THUẬT GIẢI TÔ đỉnh i và đỉnh j, kí hiệu Qhij, là 1 nếu đỉnh i
MÀU ĐỒ THỊ có nối với đỉnh j và 0 nếu ngược lại.
Bài toán đặt ra là làm thế nào để tô màu đồ
thị sao cho không tồn tại hai đỉnh có quan hệ
ThS. Nguyễn Thị Thúy Loan với nhau được tô chung một màu với số màu
cần tô là ít nhất?
6
6/8/2010 Nguyễn Thị Thúy Loan 6
Ví dụ Thuật giải tô màu “Tối ưu”
Bước 1: [Tô màu] Tô màu i (i bắt đầu xét từ 1) cho đỉnh
a
b c
có bậc lớn nhất.
e Bước 2: [Hạ bậc & cấm tô]
d
h
2.1. Bậc của đỉnh được tô màu i thì bậc:=0.
p 2.2. Bậc của đỉnh có quan hệ với đỉnh được tô màu i thì
bậc:= bâc – 1.
Tô 3 màu Ít nhất chưa? 2.3. Cấm tô màu i cho đỉnh có quan hệ với đỉnh được tô
màu i.
Bước 3: Lặp lại bước 1 cho đến khi tất cả các đỉnh đều
7 8
được tô màu.
6/8/2010 Nguyễn Thị Thúy Loan 7 6/8/2010 Nguyễn Thị Thúy Loan 8
- Minh họa Ví dụ
Một công ty có 8 đài phát thanh A, B, C, D, E, F, G, H có
khoảng cách (km) được cho trong ma trận sau:
A B C D E F G H
A 0 100 50 30 200 150 40 120
B 0 30 80 120 50 200 150
a C 0 120 100 30 80 50
b c D 0 50 120 150 30
E 0 200 120 120
e
d F 0 180 150
h G 0 50
H 0
p
Do yêu cầu kỹ thuật nên các đài có khoảng cách 100km
không được dùng chung một trạm phát sóng. Hãy lắp đặt các
9 10
trạm phát sóng sao cho số trạm cần lắp là nhỏ nhất.
6/8/2010 Nguyễn Thị Thúy Loan 9
Giải quyết Giải quyết
A
A
0
B
100 50
C D E F G
30 200 150 40 120
H
2. Áp dụng thuật giải
B 0 30 80 120 50 200 150
C 0 120 100 30 80 50 để tô màu
1. Xác định đồ thị D 0 50 120 150 30
E 0 200 120 120
a) Đỉnh: F 0 180 150
G 0 50
Kết quả:
b) Cung: H 0
11 12
6/8/2010 Nguyễn Thị Thúy Loan 11 6/8/2010 Nguyễn Thị Thúy Loan 12
- AC AD AF BC BD BE CE DE DF EF
Ví dụ
AC 0 1 1 1 0 0 1 0 0 0
Thuật giải tham lam (Greedy) AD
AF
1
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
1
BC 1 0 0 0 1 1 1 0 0 0
Bước 1: BD 0 1 0 1 0 1 0 1 1 0
Cho ma trận bên BE 0 0 0 1 1 0 1 1 0 1
i := 0 CE 1 0 0 1 0 1 0 1 0 1
Bước 2: DE 0 1 0 0 1 1 1 0 1 1
DF 0 1 1 0 1 0 0 1 0 1
i := i+1 i=1 1
i=1 1
1
EF
0
0
1
0 0
1
1 1 1 1 0
Tô màu i cho tất cả các đỉnh có thể tô được. AC AD AF BC BD BE CE DE DF EF
Bước 3: i=2 2 2
AD AF BC BE CE DE DF
Lặp lại bước 2 cho đến khi tất cả các đỉnh
i=3 3 3
đều được tô màu. AF BE CE DE DF
13 i=4 4 4 4
i=4 i=5 5 14
CE DE DF DE
6/8/2010 Nguyễn Thị Thúy Loan 13
AC AD AF BC BD BE CE DE DF EF Bậc
Thuật giải sắp thứ tự + Ví dụ AC
AD
0
1
1
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
0
4
5
tham lam
AF 1 1 0 0 0 0 0 0 1 1 4
BC 1 0 0 0 1 1 1 0 0 0 4
BD 0 1 0 1 0 1 0 1 1 0 5
Bước 1: Cho ma trận BE 0 0 0 1 1 0 1 1 0 1 5
Sắp xếp các đỉnh theo chiều giảm dần của CE 1 0 0 1 0 1 0 1 0 1 5
bậc. bên DE
DF
0
0
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
1
6
5
i := 0 EF 0 0 1 0 0 1 1 1 1 0 5
Bước 2: i=1 1 1
DE AD BD BE CE DF EF AC AF BC
i := i+1
Tô màu i cho tất cả các đỉnh có thể tô được (xét i=2 2 2
từ trái sang). AD BD BE CE DF EF AF BC
Bước 3: i=3 3 3 3
Lặp lại bước 2 cho đến khi tất cả các đỉnh đều BD CE DF EF AF BC
được tô màu. i=4 4 4 i=5 5
15 16
DF EF BC EF
6/8/2010 Nguyễn Thị Thúy Loan 15
- Ví dụ Ví dụ
Một cuộc hội thảo có 9 chủ đề a, b, c, d, e, f, g, Học kì II năm 2009 -2010, Phòng ĐT muốn tổ
h, i biết rằng các chủ đề sau không được phép chức thi các môn A,B,C,D,E,F,G,H,I biết rằng
diễn ra trong cùng một buổi: ac, bde, adg, cdf, các môn sau không được thi chung một buổi.
dfg, egh, ghi. ABC, AE, BCD, BHI, EFG, EI, GHI.
Hãy sắp xếp các chủ đề vào các buổi sao cho số Hãy sắp xếp lịch thi sao cho số buổi thi cần sắp
buổi diễn ra là ít nhất. là ít nhất.
17 18
6/8/2010 Nguyễn Thị Thúy Loan 17 6/8/2010 Nguyễn Thị Thúy Loan 18
Ví dụ Chương II Phần 1
Cho ngã năm giao thông như sau trong đó BE là
đường 1 chiều: CÁC PHƯƠNG PHÁP
E
A
Yêu cầu:
1. Xác định đồ thị.
TÌM KIẾM LỜI GIẢI
2. Tô màu đồ thị.
D
Sao cho tại mỗi thời điểm,
các tuyến lưu thông
không giao nhau.
ThS. Nguyễn Thị Thúy Loan
B
C
19
Ref: http://www.cs.cmu.edu/~awm/tutorials
6/8/2010 Nguyễn Thị Thúy Loan 19
- Nội dung Bài toán tìm kiếm
a GOAL
G
b c
Bài toán tìm kiếm
e
Tìm kiếm Theo chiều Rộng d
f
Tìm kiếm Theo chiều Sâu START
S h
p r
q
Làm sao đi từ S đến G? Số bước đi ít nhất có thể
là bao nhiêu? Đi qua các đỉnh nào?
6/8/2010 Nguyễn Thị Thúy Loan 21 6/8/2010 Nguyễn Thị Thúy Loan 22
Bài toán tìm kiếm Bài toán tìm kiếm
Một bài toán tìm kiếm gồm năm thành phần: succs: Q P(Q) là một hàm nhận một trạng
thái làm đầu vào và trả về kết quả là một tập
Q , S , G , succs , cost trạng thái. succs(s) nghĩa là “tập các trạng
Q là một tập hữu hạn các trạng thái. thái có thể đến từ s trong một bước”.
cost: Q Q R là một hàm nhận hai trạng
S Q một tập khác rỗng các trạng thái đầu thái s và s’ làm đầu vào. Nó trả về chi phí
(START). một bước của việc di chuyển từ s đến s’.
Hàm chi phí chỉ được xác định khi và chỉ khi
G Q một tập khác rỗng các trạng thái đích s’ là trạng thái con của s, nghĩa là s’
(GOAL). succs(s)
6/8/2010 Nguyễn Thị Thúy Loan 23 6/8/2010 Nguyễn Thị Thúy Loan 24
- Bài toán tìm kiếm Bài toán tìm kiếm
a GOAL
GOAL a GOAL
b c b c
e e
d f d f
START
START
h START
h
p r p r
q q
Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL} à i
?B ?
Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL}
S = { START } S = { START } tâm ậy
G = { GOAL } u an h ư v
G = { GOAL } aq n
succs(b) = { a } succs(b) = { a } a o t giống
is
succs(e) = { h , r } succs(e) = { h , r } Tạ n nào
succs(a) = {}, … succs(a) = {} to á
cost(s,s’) = 1 cho tất cả các biến đổi cost(s,s’) = 1 cho tất cả các biến đổi
Các bài toán tìm kiếm Các bài toán tìm kiếm
Lập lịch
8-Hậu
Gì nữa?
Giải toán
6/8/2010 Nguyễn Thị Thúy Loan 28
- Tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộng
(BFS – Breadth First Search) (BFS – Breadth First Search)
a GOAL Gán nhãn tất cả trạng thái có thể đi đến được
b c từ S trong 1 bước.
e Sau đó gán nhãn tất cả trạng thái có thể đi đến
d
f
được từ S trong 2 bước nhưng không thể đi
START
h
đến được trong ít hơn 2 bước.
p r
q
6/8/2010 Nguyễn Thị Thúy Loan 29 6/8/2010 Nguyễn Thị Thúy Loan 30
Tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộng
(BFS – Breadth First Search) GOAL
a
b c
Sau đó gán nhãn tất cả trạng thái có thể đi đến
được từ S trong 3 bước nhưng không thể đi 0 bước từ
start d
e
f
đến được trong ít hơn 3 bước. START h
v.v… cho đến khi đạt được trạng thái G hoặc
p r
không còn đi tiếp được nữa. q
6/8/2010 Nguyễn Thị Thúy Loan 31 6/8/2010 Nguyễn Thị Thúy Loan 32
- Tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộng
1 bước từ 1 bước từ
start start GOAL
a GOAL a
c b c
b
0 bước từ e 0 bước từ e
start d start d
f f
START START h
h
p r p r
q q
2 bước từ
start
6/8/2010 Nguyễn Thị Thúy Loan 33 6/8/2010 Nguyễn Thị Thúy Loan 34
Tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộng
3 bước từ
1 bước từ 3 bước từ 4 bước từ
start 1 bước từ
start a GOAL start start
start a GOAL
b c
b c
0 bước từ e
d
0 bước từ e
start f d
start f
START h START h
p r
q p r
q
2 bước từ
2 bước từ start
start
6/8/2010 Nguyễn Thị Thúy Loan 35 6/8/2010 Nguyễn Thị Thúy Loan 36
- Ghi nhớ đường đi! Ghi nhớ đường đi!
Khi gán nhãn một trạng thái, ghi nhận trạng thái
a GOAL
b c trước đó. Ghi nhận này được gọi là con trỏ quay
d
e
f
lui. Lịch sử trước đó được dùng để phát sinh con
START
h đường lời giải, khi đã tìm được đích:
p r
q
“Tôi đã đến đích. Tôi thấy mình đã ở f trước đó.
Và tôi đã ở r trước khi tới f. Và…
…. do đó con đường lời giải là S e r f
G”
6/8/2010 Nguyễn Thị Thúy Loan 37 6/8/2010 Nguyễn Thị Thúy Loan 38
Con trỏ quay lui Con trỏ quay lui
4 bước từ 4 bước từ
start start
1 bước từ 3 bước từ 1 bước từ 3 bước từ
start start GOAL start start GOAL
a a
b c b c
0 bước từ e 0 bước từ e
start d start d
f f
START h START h
p r p r
q q
2 bước từ start 2 bước từ start
6/8/2010 Nguyễn Thị Thúy Loan 39 6/8/2010 Nguyễn Thị Thúy Loan 40
- Tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộng
Với bất kỳ trạng thái s nào đã gán nhãn, ghi nhớ: Sau đó, trong suốt vòng lặp, ta sẽ tính Vk+1,
previous(s) là trạng thái trước đó trên đường đi được định nghĩa là tập các trạng thái mà từ
ngắn nhất từ trạng thái START đến s. trạng thái START đi đến có đúng k+1 bước
Trong vòng lặp thứ k của thuật toán ta bắt đầu Chúng ta bắt đầu với k = 0, V0 = {START}
với Vk được định nghĩa là tập các trạng thái mà và định nghĩa, previous(START) = NULL
từ trạng thái START đi đến có đúng k bước Sau đó ta sẽ thêm vào những trạng thái một
bước từ START vào V1. Và tiếp tục.
6/8/2010 Nguyễn Thị Thúy Loan 41 6/8/2010 Nguyễn Thị Thúy Loan 42
BFS BFS
a GOAL a GOAL
b c b c
e e
d d
f f
START h START h
V0 p
q
r V0 p
q
r
V1
6/8/2010 Nguyễn Thị Thúy Loan 43 6/8/2010 Nguyễn Thị Thúy Loan 44
- BFS BFS
a GOAL a GOAL
b c b c
e e
d d
f f V3
START h START h
V0 p
q
r V0 p
q
r
V1 V1
V2 V2
6/8/2010 Nguyễn Thị Thúy Loan 45 6/8/2010 Nguyễn Thị Thúy Loan 46
BFS V4 BFS V4
a GOAL a GOAL
b c b c
e e
d d
f V3 f
ta lấy V3
phép chúng
START START
g gian tì m kiếmhcho tiện
Giả sử khôn
h
ột cách thuận
đượcptrạng thái trước m
S? r
V0 p r V0 qt cách
khác cho BF
q
•Có th ể nghĩ ra mộ ớ c đó
những gì trư
ng cần phải lưu trữ
V1 •Có thể khô
V1
V2 phải lưu? V 2
6/8/2010 Nguyễn Thị Thúy Loan 47 6/8/2010 Nguyễn Thị Thúy Loan 48
- Chi phí chuyển đổi Chi phí chuyển đổi
a GOAL Lưu ý rằng BFS tìm đường đi ngắn nhất theo
2 2
b c
số bước. Nó không tìm thấy đường đi có chi
5
1 8
5
phí thấp nhất.
2 e
3 d
f
Bây giờ chúng ta xem xét một thuật toán tìm
9 1 9
START
h
đường đi với chi phí thấp nhất. Trong vòng
1 4 5
4 3
lặp thứ k, với bất kỳ trạng thái S nào, đặt g(s)
p 15 r
q
là chi phí đường đi có chi phí nhỏ nhất đến S
trong k bước hay ít hơn.
6/8/2010 Nguyễn Thị Thúy Loan 49 6/8/2010 Nguyễn Thị Thúy Loan 50
Tìm kiếm với chi phí đồng nhất Hàng đợi ưu tiên
(UCS – Uniform Cost Search) Một hàng đợi ưu tiên là một cấu trúc dữ liệu trong
đó ta có thể thêm và lấy các cặp (thing, value) với
các thao tác sau:
Một cách tiếp cận BFS đơn giản về mặt khái
Init-PriQueue(PQ) khởi tạo PQ rỗng.
niệm khi có chi phí chuyển đổi Insert-PriQueue(PQ, thing, value) thêm (thing, value) vào hàng đợi.
Dùng hàng đợi ưu tiên Pop-least(PQ) trả về cặp (thing, value) với giá trị
thấp nhất, và loại bỏ nó khỏi hàng đợi.
Hàng đợi ưu tiên có thể được
cài đặt theo một cách sao Rất nhỏ
cho chi phí của các toán tử (dù không tuyệt đối)
thêm vào và lấy ra là:
O(log(số mục trong hàng đợi ưu tiên))
6/8/2010 Nguyễn Thị Thúy Loan 51
- UCS Bắt đầu UCS
a GOAL
Một cách tiếp cận BFS đơn giản về mặt khái 2 2
c
niệm khi có chi phí chuyển đổi b 2
5
1 8
Dùng hàng đợi ưu tiên 2 e
3 d
f
PQ = Tập trạng thái đã được mở 9 1 9
START
h
4 5
Độ ưu tiên của trạng thái s là g(s) = chi phí đến 1
4 3
p r
s sử dụng đường đi được cho bởi con trỏ quay 15
q
lui. PQ = { (s,0, null) }
6/8/2010 Nguyễn Thị Thúy Loan 53 6/8/2010 Nguyễn Thị Thúy Loan 54
Lặp UCS Lặp UCS
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
Lặp: Lặp:
PQ = { (s,0,null) } 1. Lấy trạng thái có chi phí thấp n = (s,0) 1. Lấy trạng thái có chi phí
nhất từ PQ thấp nhất từ PQ
2. Thêm các con vào PQ
PQ = { (p,1,s), (d,3,s), (e,9,s) } 2. Thêm các con vào PQ
- Lặp UCS Lặp UCS
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
Lặp: Lặp:
1. Lấy trạng thái có chi 1. Lấy trạng thái có chi
n = (p,1)
phí thấp nhất từ PQ phí thấp nhất từ PQ
PQ = { (d,3,s), (e,9,s), (q,16,p) } 2. Thêm các con vào PQ n = (d,3)
2. Thêm các con vào PQ
PQ = { (b,4,d), (e,5,d), (c,11,d), (q,16,p) }
Lặp: Lặp:
1. Lấy trạng thái chi phí
Lặp UCS Lặp UCS
1. Lấy trạng thái chi phí
thấp nhất từ PQ thấp nhất từ PQ
2. Thêm các con 2. Thêm các con
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
n = (d,3) n = (b,4)
PQ = { (b,4,d), (e,5,d), (c,11,d), (q,16,p) } PQ = { (e,5,d), (a,6,b), (c,11,d), (q,16,p) }
- Lặp: Lặp:
Lặp UCS Lặp UCS
1. Lấy trạng thái chi phí 1. Lấy trạng thái chi phí
thấp nhất từ PQ thấp nhất từ PQ
2. Thêm các con 2. Thêm các con
a GOAL GOAL
2 2 a
2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
n = (e,5) n = (a,6)
PQ = { (a,6,b),(h,6,e),(c,11,e),(r,14,e),(q,16,p) } PQ = { (h,6,e),(c,11,e),(r,14,e),(q,16,p) }
Lặp UCS Lặp UCS
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
Lặp: Lặp:
1. Lấy trạng thái chi phí 1. Lấy trạng thái chi phí
n = (h,6) thấp nhất từ PQ n = (h,6) thấp nhất từ PQ
2. Thêm các con 2. Thêm các con
PQ = { (q,10,h), (c,11,e),(r,14,e) } PQ = { (q,10,h), (c,11,d),(r,14,e) }
- Lặp UCS Lặp UCS
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
Lặp: Lặp:
n = (q,10) 1. Lấy trạng thái chi phí 1. Lấy trạng thái chi phí thấp
thấp nhất từ PQ n = (c,11) nhất từ PQ
PQ = { (c,11,d),(r,14,e) } 2. Thêm các con PQ = {(r,13,q) } 2. Thêm các con
Lặp UCS Lặp UCS
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
Lặp: Lặp:
n = (r,13) 1. Lấy trạng thái chi phí thấp n =(f,18) 1. Lấy trạng thái chi phí thấp
nhất từ PQ nhất từ PQ
PQ = { (f,18,r) } 2. Thêm các con PQ = { (G,23,f) } 2. Thêm các con
- Lặp UCS Lặp UCS
a GOAL a GOAL
2 2 2 2
b c b c
2 2
5 5
1 8 1 8
2 e 2 e
3 d 3 d
f f
9 1 9 9 1 9
START START
h h
1 4 5 1 4 5
4 3 4 3
p 15 r p 15 r
q q
Lặp: Lặp:
n = (g, 23) 1. Lấy trạng thái chi phí thấp n = (g, 23) 1. Lấy trạng thái chi phí thấp
nhất từ PQ nhất từ PQ
PQ = {} 2. Thêm các con
PQ = { (G,23,f) } 2. Thêm các con
Biểu diễn cây tìm
a GOAL
Kết thúc UCS b c
e
kiếm
d f
START
h
a GOAL
2 p q r
2
b c
2
5
1 8
2 e
3 d
f
9 1 9
START
h
4 5
1 m
k iế
p 15
4 3
r
y tìm o?
q câ ự nà
ệt
uy ứ t
Lặp: ta d e o th
ng th
PQ = { } 1. Lấy trạng thái chi phí thấp hú FS
C iB
nhất từ PQ
2. Thêm các con vớ
- Biểu diễn cây tìm Biểu diễn cây tìm
a GOAL
a GOAL
b c b c
e e
kiếm kiếm
d f d f
START
h START
h
p q r p q r
Biểu diễn cây tìm Biểu diễn cây tìm
a GOAL
a GOAL
b c b c
e e
kiếm kiếm
d f d f
START
h START
h
p q r p q r
Là đích, dừng
- Tìm kiếm theo chiều sâu DFS trên thực tế
START
GOAL
2 a
2
START d a GOAL
b c
5
START d b c
5 b
1 8 START d b a
2 e
d
START d c e
3 f d
9 1 9 START d c a f
START h
1 4 5 START d e START
h
p 4 3 r START d e r
15 q p r
START d e r f q
START d e r f c
Một thay thế cho BFS. Luôn mở từ node vừa mới START d e r f c a
mở nhất, nếu nó có bất kỳ node con nào chưa thử. START d e r f
Ngược lại quay lại node trước đó trên đường đi. GOAL
Duyệt cây tìm kiếm DFS Bài tập
S G
Thứ tự mà trong đó các node của cây tìm kiếm
được viếng? A B C D E F G
A 0 1 0 0 0 0 2
B 0 0 4 0 0 3 0
C 0 0 0 8 0 3 0
D 3 0 0 0 3 0 0
E 0 0 0 0 0 0 12
F 0 0 0 1 3 0 0
G 0 0 1 7 0 5 0
Là đích, dừng 6/8/2010 Nguyễn Thị Thúy Loan 80
nguon tai.lieu . vn
