Bài giảng Trí tuệ nhân tạo - ThS. Nguyễn Thị Thúy Loan

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:65

Thêm vào BST

Báo xấu

188
lượt xem 34
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Trí tuệ nhân tạo - ThS. Nguyễn Thị Thúy Loan trình bày các nội dung về các thuật giải tô màu đồ thị, các thuật giải tìm kiếm trên đồ thị, biểu diễn và xử lý tri thức, phân lớp. Mời bạn đọc tham khảo tài liệu để hiểu rõ hơn về các nội dung trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Trí tuệ nhân tạo - ThS. Nguyễn Thị Thúy Loan

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