Bài giảng Trí tuệ nhân tạo - Tìm kiếm

Nội dung text: Bài giảng Trí tuệ nhân tạo - Tìm kiếm

1. TRÍ TU NHÂN TO Tìm kim Ref:
2. Ni dung trình bày 2
   Bài tốn tìm kim
   Tìm kim Theo chiu Rng
   Tính ti ưu, Tính đy đ, ð phc tp thi gian và khơng gian
   Cây Tìm kim
   Tìm kim Theo chiu Sâu
3. Mt bài tốn Tìm kim 3 a GOAL b c e d f START h p r q Làm sao đ đi t S đn G? Và s bin đi cĩ th ít nht là gì?
4. Hình thc hố mt bài tốn tìm kim 4 Mt bài tốn tìm kim cĩ năm thành phn: Q , S , G , succs , cost
   Q là mt tp hu hn các trng thái.
   S ⊆ Q mt tp khác rng các trng thái ban đu.
   G ⊆ Q mt tp khác rng các trng thái đích.
   succs : Q  P(Q) là mt hàm nhn mt trng thái làm đu vào và tr v kt qu là mt tp trng thái. succs (s) nghĩa là “tp các trng thái cĩ th đn t s trong mt bưc”.
   cost : Q , Q  S Dương là mt hàm nhn hai trng thái, s và s’, làm đu vào. Nĩ tr v chi phí mt bưc ca vic di chuyn t s đn s’. Hàm chi phí ch đưc đnh nghĩa khi s’ là trng thái con ca s.
5. Bài tốn Tìm kim 5 a GOAL b c e d f START h p r q Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL} S = { START } G = { GOAL } succs (b) = { a } succs (e) = { h , r } succs (a) = NULL etc. cost (s,s’ ) = 1 cho tt c các bin đi
6. Bài tốn Tìm kim 6 a GOAL b c e d f START h p r q Q = {START, a , b , c , d , e , f , h , p , q , r , GOAL} S = { START } G = { GOAL } succs (b) = { a } succs (e) = { h , r } succs (a) = NULL etc. cost (s,s’ ) = 1 cho tt c các bin đi
7. Các Bài tốn Tìm kim 7
8. Các Bài tốn Tìm kim 8 Lp lch 8Hu Gì na? Gii tốn
9. Tìm kim Theo Chiu Rng 9 a GOAL b c e d f START h p r q Gán nhãn tt c trng thái cĩ th đi đn đưc t S trong 1 bưc nhưng khơng th đi đn đưc trong ít hơn 1 bưc. Sau đĩ gán nhãn tt c trng thái cĩ th đi đn đưc t S trong 2 bưc nhưng khơng th đi đn đưc trong ít hơn 2 bưc. Sau đĩ gán nhãn tt c trng thái cĩ th đi đn đưc t S trong 3 bưc nhưng khơng th đi đn đưc trong ít hơn 3 bưc. V.v đn khi trng thái Goal đưc đi đn.
10. Tìm kim Theo Chiu Rng 10 a GOAL b c 0 bưc t e d start f START h p r q
11. Tìm kim Theo Chiu Rng 11 1 bưc t start a GOAL b c 0 bưc t e d start f START h p r q
12. Tìm kim Theo Chiu Rng 12 1 bưc t start a GOAL b c 0 bưc t e d start f START h p r q 2 bưc t start
13. Tìm kim Theo Chiu Rng 13 1 bưc t start a GOAL b c 0 bưc t e d start f START h 3 bưc t start p r q 2 bưc t start
14. Tìm kim Theo Chiu Rng 14 1 bưc t 4 bưc t start start a GOAL b c 0 bưc t e d start f START h 3 bưc t start p r q 2 bưc t start
15. Ghi nh đưng đi! 15 a GOAL b c e d f START h p r q Ngồi ra, khi gán nhãn mt trng thái, ghi nhn trng thái trưc đĩ. Ghi nhn này đưc gi là con tr quay lui . Lch s trưc đĩ đưc dùng đ phát sinh con đưng li gii, khi đã tìm đưc đích: “Tơi đã đn đích. Tơi thy mình đã f trưc đĩ. Và tơi đã r trưc khi ti f. Và . do đĩ con đưng li gii là S  e  r  f  G”
16. Con tr quay lui 16 4 bưc t 1 bưc t start start a GOAL b c 0 bưc t e d start f START h 3 bưc t start p r q 2 bưc t start
17. Con tr quay lui 17 1 bưc t 4 bưc t start start a GOAL b c 0 bưc t e d start f START h 3 bưc t start p r q 2 bưc t start
18. Bt đu Tìm kim Theo chiu Rng 18 Vi bt kỳ trng thái s nào đã gán nhãn, ghi nh: previous (s) là trng thái trưc đĩ trên đưng đi ngn nht t trng thái START đn s. Trong vịng lp th k ca thut tốn ta bt đu vi Vk đưc đnh nghĩa là tp các trng thái mà t trng thái start đi đn cĩ đúng k bưc Sau đĩ, trong sut vịng lp, ta s tính Vk+1 , đưc đnh nghĩa là tp các trng thái mà t trng thái start đi đn cĩ đúng k+1 bưc Chúng ta bt đu vi k = 0, V0 = {START} và đnh nghĩa, previous (START ) = NULL Sau đĩ ta s thêm vào nhng trng thái mt bưc t START vào V1. Và tip tc.
19. BFS 19 a GOAL b c e d f START h p r V0 q
20. BFS 20 a GOAL b c e d f START h p r V0 q V1
21. BFS 21 a GOAL b c e d f START h p r V0 q V1 V2
22. BFS 22 a GOAL b c e d f V3 START h p r V0 q V1 V2
23. BFS V4 23 a GOAL b c e d f V3 START h p r V0 q V1 V2
24. Tìm kim Theo Chiu Rng 24 V0 := S (tp các trng thái ban đu) previous (START ) := NIL k := 0 while (khơng cĩ trng thái đích trong Vk và Vk khác rng) do Vk+1 := tp rng Vi mi trng thái s trong Vk Vi mi trng thái s’ trong succs (s) Nu s’ chưa gán nhãn ðt previous (s’ ) := s Thêm s’ vào Vk+1 k := k+1 If Vk rng thì FAILURE Else xây dng li gii: ðt Si là trng thái th i trên đưng đi ngn nht. ðnh nghĩa Sk = GOAL, và vi mi i <= k, đnh nghĩa Si1 = previous (Si).
25. BFS V4 25 a GOAL b c e d f V3 START h p r V0 q V1 V2
26. Mt cách khác: ði lui 26 a GOAL b c e d f START h p r q Gán nhãn tt c các trng thái cĩ th đn G trong 1 nhưng khơng th đi đn nĩ trong ít hơn 1 bưc. Gán nhãn tt c các trng thái cĩ th đn G trong 2 nhưng khơng th đi đn nĩ trong ít hơn 2 bưc. V.v. cho đn khi đn start. Nhãn “s bưc ti đích” xác đnh đưng đi ngn nht. Khơng cn thêm thơng tin lưu tr.
27. Các chi tit ca Theo Chiu Rng 27
    Vn tt nu cĩ nhiu hơn mt trng thái đích.
    Vn tt nu cĩ nhiu hơn mt trng thái đu.
    Thut tốn này hot đng theo kiu tin t đu. Thut tốn nào hot đng theo kiu tin t đu đưc gi là suy din tin .
    Bn cũng cĩ th hot đng quay lui t đích.
    Thut tốn này rt ging thut tốn Dijkstra.
    Bt kỳ thut tốn nào hot đng theo kiu quay lui t đích đưc gi là suy din lùi .
    Lùi so vi tin. Cái nào tt hơn?
28. Chi phí chuyn đi 28 a GOAL 2 2 c b 5 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 p 4 3 r 15 q Lưu ý rng BFS tìm đưng đi ngn nht theo s bin đi. Nĩ khơng tìm thy đưng đi cĩ chi phí ít nht. Bây gi chúng ta xem xét mt thut tốn tìm đưng đi chi phí thp nht. Trong vịng lp th k, vi bt kỳ trng thái S nào, đt g(s) là chi phí đưng đi cĩ chi phí nh nht đn S trong k bưc hay ít hơn.
29. Theo Chiu Rng Chi phí Thp nht 29 Vk = tp các trng thái cĩ th đn đưc trong đúng k bưc, và vi nĩ đưng đi kbưc chi phí thp nht thì ít chi phí hơn bt kỳ đưng đi nào cĩ đ dài nh hơn k. Nĩi cách khác, Vk = tp trng thái mà giá tr ca nĩ thay đi so vi vịng lp trưc. V0 := S (tp trng thái đu) previous (START ) := NIL g(START ) = 0 k := 0 while (Vk khác rng) do Vk+1 := rng Vi mi s trong Vk Vi mi s’ trong succs (s) Nu s’ chưa đưc gán nhãn HAY nu g(s) + Cost (s,s’ ) < g(s’ ) ðt previous (s’ ) := s ðt g(s’ ) := g(s) + Cost (s,s’ ) Thêm s’ vào Vk+1 k := k+1 Nu GOAL chưa gán nhãn, thốt FAILURE Ngli xây dng li gii theo: ðt Sk là trng thái th k trên đưng đi ngn nht. ðnh nghĩa Sk = GOAL, và vi mi i <= k, đnh nghĩa Si1 = previous (Si).
30. Tìm kim Chi phí ðng nht 30
    Mt cách tip cn BFS đơn gin v mt khái nim khi cĩ chi phí chuyn đi
    Dùng hàng đi ưu tiên
31. Hàng đi Ưu tiên 31 Mt hàng đi ưu tiên là mt cu trúc d liu trong đĩ ta cĩ th thêm và ly các cp (thing, value) vi các tốn t sau: Init PriQueue(PQ) khi to PQ rng. InsertPriQueue(PQ, thing, value) thêm (thing, value) vào hàng đi. Popleast(PQ) tr v cp (thing, value) vi giá tr thp nht, và loi b nĩ khi hàng đi.
32. Hàng đi Ưu tiên 32 Mt hàng đi ưu tiên là mt cu trúc d liu trong đĩ ta cĩ th thêm và ly các cp (thing, value) vi các tốn t sau: Init PriQueue(PQ) khi to PQ rng. InsertPriQueue(PQ, thing, value) thêm (thing, value) vào hàng đi. Popleast(PQ) tr v cp (thing, value) vi giá tr thp nht, và loi b nĩ khi hàng đi. Hàng đi Ưu tiên cĩ th đưc Rt r (dù khơng cài đt theo mt cách sao cho tuyt đi, nhưng r khơng tin đưc!) chi phí ca các tốn t thêm và ly là O(log (s mc trong hàng đi ưu tiên ))
33. Tìm kim Chi phí ðng nht (UCS) 33
    Mt cách tip cn BFS đơn gin v mt khái nim khi cĩ chi phí chuyn đi
    Dùng hàng đi ưu tiên PQ = Tp trng thái đã đưc m hay đang đi m ð ưu tiên ca trng thái s = g(s) = chi phí đn s dùng đưng đi cho bi con tr quay lui.
34. Bt đu UCS 34 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q PQ = { (S,0) }
35. Lp UCS 35 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (S,0) } 2. Thêm các con
36. Lp UCS 36 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (p,1), (d,3) , (e,9) } 2. Thêm các con
37. Lp UCS 37 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (d,3) , (e,9) , (q,16) } 2. Thêm các con
38. Lp UCS 38 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (b,4) , (e,5) , (c,11) , (q,16) } 2. Thêm các con
39. Lp UCS 39 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (b,4) , (e,5) , (c,11) , (q,16) } 2. Thêm các con
40. Lp UCS 40 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (e,5) , (a,6) , (c,11) , (q,16) } 2. Thêm các con
41. Lp UCS 41 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (a,6),(h,6),(c,11),(r,14),(q,16) } 2. Thêm các con
42. Lp UCS 42 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (h,6),(c,11),(r,14),(q,16) } 2. Thêm các con
43. Lp UCS 43 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (q,10), (c,11),(r,14) } 2. Thêm các con
44. Lp UCS 44 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (q,10), (c,11),(r,14) } 2. Thêm các con
45. Lp UCS 45 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (c,11),(r,13) } 2. Thêm các con
46. Lp UCS 46 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (r,13) } 2. Thêm các con
47. Lp UCS 47 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (f,18) } 2. Thêm các con
48. Lp UCS 48 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (G,23) } 2. Thêm các con
49. Lp UCS 49 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { (G,23) } 2. Thêm các con
50. Kt thúc UCS 50 a GOAL 2 2 c b 2 5 1 8 2 e 3 d f 9 1 9 START h 1 4 5 4 3 p 15 r q Lp: 1. Ly trng thái chi phí thp nht t PQ PQ = { } 2. Thêm các con
51. Biu din cây tìm kim 51 a GOAL b c e d f START h p q r
52. ðánh giá mt thut tốn tìm kim 52
    Tính đy đ : thut tốn cĩ bo đm tìm thy li gii nu cĩ hay khơng?
    Cĩ bo đm tìm thy ti ưu? (nĩ s tìm thy đưng đi cĩ chi phí ít nht?)
    ð phc tp v thi gian
    ð phc tp v khơng gian (s dng b nh) Các bin: N s trng thái ca bài tốn B nhân t phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc ngn nht Chúng ta đánh giá thut tốn như th nào?
53. ðánh giá mt thut tốn 53 N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc (chi phí) ít nht Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu tt c L L Search chuyn đi O(min(N,B )) O(min(N,B )) cùng chi phí LCBFS Least Cost CC L L BFS O(min(N,B )) O(min(N,B )) UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B ))
54. Tìm kim Theo Chiu Sâu 54 a GOAL 2 2 c b 5 5 1 8 2 e d 3 f 9 1 9 START h 1 4 5 p 4 3 r 15 q Mt thay th cho BFS. Luơn m t node va mi m nht, nu nĩ cĩ bt kỳ node con chưa th nào. Ngưc li quay li node trưc đĩ trên đưng đi.
55. DFS trên thc t 55 a GOAL b c START e START d d f START d b START h START d b a START d c p r q START d c a START d e START d e r START d e r f START d e r f c START d e r f c a START d e r f GOAL
56. Duyt cây tìm kim DFS 56 a GOAL b c e d f Bn cĩ th v th START h t mà trong đĩ p q r các node ca cây tìm kim đưc ving?
57. Thut tốn DFS 57 Ta dùng mt cu trúc d liu gi là Path đ biu din đưng đi t START đn trng thái hin ti. VD. Path P = Cùng vi mi node trên đưng đi, chúng ta phi nh nhng con nào ta vn cĩ th m. VD. ti đim sau, ta cĩ P =
58. Thut tốn DFS 58 ðt P = While (P khác rng và top(P) khơng là đích) if m rng ca top(P) rng then loi b top(P) (“pop ngăn xp”) else gi s mt thành viên ca m rng ca top(P) loi s khi m rng ca top(P) to mt mc mi trên đnh đưng đi P: s (expand = succs(s)) Thut tốn này cĩ th đưc vit gn dưi If P rng dng đ qui, dùng ngăn xp ca chương trình tr v FAILURE đ cài đt P. Else tr v đưng đi cha trng thái ca P
59. ðánh giá mt thut tốn 59 N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc (chi phí) ít nht Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu chi L L Search phí chuyn O(min(N,B )) O(min(N,B )) đi như nhau LCBFS Least Cost CC L L BFS O(B ) O(min(N,B )) UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B )) DFS Depth First Search
60. ðánh giá mt thut tốn 60 N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc (chi phí) ít nht Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu chi L L Search phí chuyn O(min(N,B )) O(min(N,B )) đi như nhau LCBFS Least Cost CC L L BFS O(min(N,B )) O(min(N,B )) UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B )) DFS Depth First KK Search N/A N/A
61. ðánh giá mt thut tốn 61 N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc (chi phí) ít nht LMAX ð dài đưng đi dài nht t start đn bt c đâu Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu chi L L Search phí chuyn O(min(N,B )) O(min(N,B )) đi như nhau LCBFS LeastGi Cost s CC Khơng gianO(min(N,B Tìm L)) O(min(N,B L)) BFS kim khơng chu trình UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B )) DFS Depth First Search
62. ðánh giá mt thut tốn 62 N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đdàiđưng đit start đngoal visbưc (chi phí) ít nht LMAX ð dài đưng đi dài nht t start đn bt c đâu Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu chi L L Search phí chuyn O(min(N,B )) O(min(N,B )) đi như Gi s Khơngnhau gian Tìm LCBFS Leastkim Cost khơngCC chu trình L L BFS O(min(N,B )) O(min(N,B )) UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B )) DFS Depth First CK LMAX Search O(B ) O(LMAX)
63. Câu hi suy nghĩ 63
    Làm sao đ ngăn A nga lp vơ tn trong DFS ? B
    Làm sao bt buc A nĩ đưa ra mt li gii ti ưu? B C
64. Câu hi suy nghĩ Tr li 1: 64 PCDFS (Path Checking DFS):
    Làm sao đ ngăn Don’tA recurse on a state nga lp vơ tn if that state is already in trong DFS ? the current pathB
    Tr li 2: Làm sao bt buc A nĩ đưa ra mt li MEMDFS (Memorizing DFS): gii ti ưu? RememberB all states expanded so far. Never C expand anything twice.
65. Câu hi suy nghĩ Tr li 1: 65 PCDFS (Path Checking DFS):
    Làm sao đ ngăn KhơngA gi li mt trng nga lp vơ tn thái nu nĩ đã cĩ trên trong DFS ? đưng đi B
    Tr li 2: Làm sao bt buc A nĩ đưa ra mt li MEMDFS (Memorizing DFS): gii ti ưu? NhB tt c trng thái đã m. Khơng bao gi m C hai ln.
66. Câu hi suy nghĩ Tr li 1: 66 PCDFS (Path Checking DFS):
    Làm sao đ ngăn KhơngA gi li mt trng nga lp vơ tn thái nu nĩ đã cĩ trên trong DFS ? đưng đi B
    Tr li 2: Làm sao bt buc A nĩ đưa ra mt li MEMDFS (Memoizing DFS): gii ti ưu? NhB tt c trng thái đã m. Khơng bao gi m C hai ln.
67. N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc (chi phí) ít nht LMAX ð dài đưng đi khơng chu trình dài nht t start đn bt c đâu Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu chi L L Search phí chuyn O(min(N,B )) O(min(N,B )) đi như nhau (1) LCBFS Least Cost CC L L BFS O(B ) O(min(N,B )) UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B )) PCDFS Path Check CK LMAX DFS O(B ) O(LMAX) MEM DFS Memoizing CK LMAX LMAX DFS O(min(N,B )) O( min (N,B ))
68. Lp Sâu dn 68 Lp sâu dn là mt thut tốn đơn gin dùng DFS làm mt th tc con: 1. Thc hin DFS ch tìm các đưng đi cĩ đ dài 1 hay ít hơn. (DFS b các đưng đi nào dài hơn hay bng 2) 2. Nu “1” tht bi, thc hin DFS ch tìm các đưng đi cĩ đ dài 2 hay ít hơn. 3. Nu “2” tht bi, thc hin DFS ch tìm các đưng đi cĩ đ dài 3 hay ít hơn. .và tip tc cho đn khi thành cơng. Chi phí là O(b1 + b2 + b3 + b4 + bL) = O(bL)
69. ðánh giá mt thut tốn N s trng thái trong bài tốn B tha s phân nhánh trung bình (s con trung bình) ( B>1) L đ dài đưng đi t start đn goal vi s bưc (chi phí) ít nht LMAX ð dài đưng đi khơng chu trình dài nht t start đn bt c đâu Q kích c hàng đi ưu tiên trung bình Thut tốn ð Ti ưu Thi gian Khơng gian BFS Breadth First C Nu chi L L Search phí chuyn O(min(N,B )) O(min(N,B )) đi như nhau (1) LCBFS Least Cost CC L L BFS O(B ) O(min(N,B )) UCS Uniform CC L L Cost Search O(log(Q) * min(N,B )) O(min(N,B )) PCDFS Path Check CK LMAX DFS O(B ) O(LMAX) MEM DFS Memoizing CK LMAX LMAX DFS O(min(N,B )) O( min (N,B )) Iterative C (1) L ID Deepening O(B ) O(L)
70. ðiu cn nm 70
    Hiu thu đáo v BFS, LCBFS, UCS, DFS.
    Hiu các khái nim v vic liu mt tìm kim là đy đ, ti ưu hay khơng, đ phc tp v thi gian và khơng gian ca nĩ
    Hiu ý tưng đng sau lp sâu dn.
71. Thc mc 71