Bài giảng Trí Tuệ Nhân Tạo - Chương 2: Chiến lược tìm kiếm mù - Nguyễn Văn Hòa

pdf

43 trang huongle 2130

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí Tuệ Nhân Tạo - Chương 2: Chiến lược tìm kiếm mù - Nguyễn Văn Hòa", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bai_giang_tri_tue_nhan_tao_chuong_2_chien_luoc_tim_kiem_mu_n.pdf

Nội dung text: Bài giảng Trí Tuệ Nhân Tạo - Chương 2: Chiến lược tìm kiếm mù - Nguyễn Văn Hòa

Ch ươ ng 2: Chi n l ư c tìm ki m mù 1
Ni dung Bài toán Bi ểu di ễn bài toán Tìm ki ếm Các chi ến l ượ c điều khi ển Các đặ c tr ưng c ủa bài toán Vấn đề trong thi ết k ế ch ươ ng trình tìm ki ếm 2
Mô hình ng d ng c a TTNT TTNT = Presentation & Search Tìm ki ếm Tri Th ức Search Knowledge Suy lu ận Engineering Heurictic 3
Các l i bài toán tìm ki m Fully observable, deterministic single -belief -state problem Non-observable sensorless (conformant) problem Partially observable/non-deterministic contingency problem interleave search and execution Unknown state space exploration problem execution first 4
Bài toán Gi ải bài toán b ằng cách tìm ki ếm, g ồm: Cấu trúc bài toán: VD. tìm đườ ng đi trên đồ th ị Bi ểu di ễn bài toán b ằng không gian tr ạng thái Gi ải bài toán = Tìm ra m ột tr ạng thái/con đườ ng trong không gian tr ạng thái (tr ạng thái đầ u -> tr ạng thái đích) 5
Bài toán Tr ạng thái Bi ểu di ễn m ột b ướ c nào đó c ủa bài toán Trong trò ch ơi, nh ư tic-tac-toe, m ỗi bàn c ờ có th ể là tr ạng thái X O O Tr ng thái Tr ng thái Tr ng thái 6
Bài toán (tt) Chuy ển tr ạng thái, lu ật chuy ển Bi ểu di ễn cho kh ả n ăng c ủa vi ệc chuy ển t ừ tr ạng thái nào đó đế n tr ạng thái khác. Ví d ụ: trong trò ch ơi, đó là lu ật ch ơi c ủa game. O O O 7
Bài toán (tt) Tr ạng thái đầ u Tr ạng thái xu ất phát c ủa bài toán Một bài toán có th ể có nhi ều tr ạng thái kh ởi đầ u Ví d ụ: game tic-tac-toe, tr ạng thái r ỗng Tr ạng đích Tr ạng thái mà bài toán đã đượ c gi ải Một bài toán có th ể có nhi ều tr ạng thái đích O X Ví d ụ: game tic-tac-toe, tr ạng thái đích là: X X O 8
Bài toán (tt) Không gian tr ạng thái: một h ệ th ống g ồm 4 thành ph ần [N,A,S,G] N là t ập nút c ủa Graph. M ỗi nút là m ột tr ạng thái c ủa quá trình gi ải quy ết v ấn đề A: T ập các cung n ối gi ữa các nút N. M ỗi cung là m ột bướ c trong gi ải quy ết v ấn đề . Cung có th ể có h ướ ng S: T ập các tr ạng thái b ắt đầ u. S khác r ỗng. G: T ập các tr ạng thái đích. G Không r ỗng Không gian tr ạng thái s ẽ đượ c xây d ựng DẦN khi ch ươ ng trình ch ạy Với bài toán l ớn, không đủ th ời gian, không gian để đặ c t ả cho t ừng tr ạng thái c ụ th ể, và đườ ng chuy ển c ụ th ể 9
Bài toán (tt) Các v ấn đề khó kh ăn trong tìm ki ếm v ới các bài toán TTNT Đặ c t ả v ấn đề ph ức t ạp Không gian tìm ki ếm l ớn Đặ c tính c ủa đố i t ượ ng c ần tìm ki ếm thay đổ i Đáp ứng th ời gian th ực Khó kh ăn v ề k ỹ thu ật Bộ nh ớ và t ốc độ truy xu ất 10
Bài toán (tt) State Space Database Không gian tìm ki ếm th ườ ng là Không gian tìm ki ếm là một graph một danh sách hay cây Tìm ki ếm m ột record/nút Mục tiêu tìm ki ếm là m ột path Ph ần t ử đã duy ệt qua là Ph ải l ưu tr ữ toàn b ộ không gian không còn dùng t ới trong quá trình tìm ki ếm Không gian tìm ki ếm là c ố Không gian tìm ki ếm bi ến độ ng đị nh trong quá trình tìm liên t ục trong quá trình tìm ki ếm ki ếm Đặ c tính c ủa tr ạng thái/nút là Thu ộc tính c ủa m ột ph ức t ạp & bi ến độ ng record/nút là c ố đị nh 11
Ví d bài toán A search problem consists of: A state space N, 1 A transition model E, 1 A start state, goal test, and path cost function A solution is a sequence of actions (a plan) which transforms the start state to a goal state
Chuy n tr ng thái Successor function Successors( ) = {(N, 1, ), (E, 1, )} Actions and Results Actions( ) = {N, E} Result( , N) = ; Result( , E) = Cost( , N, ) = 1; Cost( , E, ) = 1
Bài toán Romania State space: Cities Successor function: Go to adj city with cost = dist Start state: Arad Goal test: Is state == Bucharest? Solution?
Không gian Graphs State space graph: A mathematical a G representation of a search b c problem e For every search problem, d f there ’s a corresponding state S space graph h The successor function is p r represented by arcs q Ridiculously tiny search graph This can be large or for a tiny search problem infinite, so we won ’t create it in memory
Bài toán: Tic tac toe Đồ th ị có h ướ ng không lặp l ại (directed acyclic graph - DAG) 16
Bài toán: 8 puzzle Có kh ả n ăng x ảy ra vòng l ặp không? 17
Chi n l ư c tìm ki m? Khi tìm ki ếm l ời gi ải, t ừ m ột tr ạng thái nào đó ch ưa ph ải là tr ạng thái đích, ta d ựa theo toán t ử sinh ra t ập các tr ạng thái m ới: m ở r ộng. Để đượ c l ời gi ải, ta ph ải liên t ục ch ọn tr ạng thái mới, m ở r ộng, ki ểm tra cho đế n khi tìm đượ c tr ạng thái đích ho ặc không m ở r ộng đượ c KGTT. Tập các tr ạng thái đượ c m ở r ộng s ẽ có nhi ều ph ần tử, vi ệc ch ọn tr ạng thái nào để ti ếp t ục m ở r ộng đượ c g ọi là chi ến l ượ c tìm ki ếm. 18
Đánh giá m t chi n l ư c? Tính đầ y đủ : chi ến l ượ c ph ải đả m b ảo tìm đượ c lời gi ải n ếu có. Độ ph ức t ạp th ời gian: m ất th ời gian bao lâu để tìm đượ c l ời gi ải. Độ ph ức t ạp không gian: t ốn bao nhiêu đơ n v ị b ộ nh ớ để tìm đượ c l ời gi ải. Tính t ối ưu: t ốt h ơn so v ới m ột s ố chi ến l ượ c khác hay không. 19
Thông tin m i nút? Nội dung tr ạng thái mà nút hi ện hành đang bi ểu di ễn. Nút cha đã sinh ra nó. Toán t ử đã đượ c s ử d ụng để sinh ra nút hi ện hành. Độ sâu c ủa nút. Giá tr ị đườ ng đi t ừ nút g ốc đế n nút hi ện hành. 20
Tìm ki m mù? Tr ạng thái đượ c ch ọn để phát tri ển ch ỉ đơ n thu ần dựa theo c ấu trúc c ủa KGTT mà không có thông tin h ướ ng d ẫn nào khác. Nói chung tìm ki ếm mù s ẽ không hi ệu qu ả. Đây là c ơ s ở để chúng ta c ải ti ến và thu đượ c nh ững chi ến l ượ c hi ệu qu ả h ơn. 21
Breadth-First-Search Tạo bi ến Open. Đư a TT b ắt đầ u vào Open. Lặp: ( đế n khi g ặp TT đích) OR (Open tr ống): E = RemoveFirst(Open). Với m ỗi lu ật so trùng đượ c v ới E: Áp d ụng lu ật để sinh TT m ới. Nếu TT m ới là TT đích thì thoát, tr ả v ề TT này. Ng ượ c l ại: Đư a TT m ới vào CU ỐI c ủa Open. 22
Breadth-First-Search (tt) Procedure Breath_first_search; BEGIN Open :=[start]; Close:=[ ]; WHILE (Open <>[ ]) do BEGIN remove X which is the leftmost of Open; IF (X=goal) THEN return (Success) ELSE BEGIN generate children of X; Put X to Close; remove children of X which is in Open or Close; Put remain children on RIGHT end of Open ; END; END; Return (FAIL); END; 23
Breadth First Search G Strategy: expand a c shallowest node first b e Implementation: d f Fringe is a FIFO S h queue p q r S d e p Search b c e h r q Tiers a a h r p q f p q f q c G q c G a [demo: bfs] a
Breadth-First-Search (tt) A B C D Laàn laëp X Open Close E F G 0 [A ] [ ] 1 A [B C D ] [A] 2 B [C D E F ] [A B] H I J 3 C [D E F G ] [A B C ] 4 D [E F G ] [A B C D ] 5 E [F G H I ] [A B C D E ] 6 F [G H I J ] [A B C D E F ] 7 G [H I J ] [A B C D E F ] 25
Depth-First-Search Nếu TT đầ u là đích ⇒ dừng, tr ả v ề success Ng ượ c l ại: L ặp đế n khi g ặp succes hay g ặp error Phát sinh TT con c ủa TT b ắt đầ u, g ọi là E. N ếu không có con nào thì báo error Gọi DFS v ới E nh ư TT b ắt đầ u Nếu success đượ c tr ả v ề thì tr ả v ề success. Ng ượ c l ại: ti ếp t ục l ặp 26
Depth-First-Search (tt) Procedure depth_first_search; Begin Open :=[start]; Close:=[ ]; While (Open <>[ ]) do begin remove X which is the leftmost of Open; If (X=goal) the return (Success) else begin generate children of X; Put X to Close; remove children of X which is in Open or Close; Put remain children on LEFT end of Open; End; End; Return (FAIL); End; 27
Depth First Search a G Strategy: expand b c deepest node first e Implementation: d f Frontier is a LIFO S h p r stack q S d e p b c e h r q a a h r p q f p q f q c G q c G a a [demo: dfs]
Depth-First-Search (tt) A Laàn laëp X Open Close B C D 0 [A] [ ] 1 A [B C D ] [A] E F G 2 B [E F C D ] [A B] 3 E [H I F C D ] [A B E ] 4 H [I F C D ] [A B E H ] H I J 5 I [F C D ] [A B E H I ] 6 F [J C D ] [A B E H I F ] 7 J [C D ] [A B E H I F J ] 8 C [ G D ] [A B E H I F J C 9 G ] 29
Breath First vs Depth First Breath First: open đượ c t ổ ch ức d ạng FIFO (Queue) Depth First: open đượ c t ổ ch ức d ạng LIFO (Stack) Đặ c tính Breath First search hi ệu qu ả khi l ời gi ải n ằm g ần g ốc c ủa cây tìm ki ếm, tìm nhi ều l ời gi ải, luôn tìm ra nghi ệm có s ố cung nh ỏ nh ất Depth First search hi ệu qu ả khi l ời gi ải n ằm sâu trong cây tìm ki ếm và có m ột ph ươ ng án ch ọn h ướ ng đi chính xác Kết qu ả Breath First search ch ắc ch ắn tìm ra k ết qu ả n ếu có Depth First có th ể sa l ầy vào đườ ng quá dài Bùng n ổ t ổ h ợp là khó kh ăn l ớn nh ất cho các gi ải thu ật này 30
Depth first search có gi i h n Depth first search có kh ả n ăng l ặp vô t ận do các tr ạng thái con sinh ra liên t ục. Độ sâu t ăng vô t ận Kh ắc ph ục b ằng cách gi ới h ạn độ sâu c ủa gi ải thu ật Sâu bao nhiêu thì v ừa? Chi ến l ượ c gi ới h ạn: Cố đị nh m ột độ sâu MAX, nh ư các danh th ủ ch ơi c ờ tính tr ướ c đượ c s ố n ướ c nh ất đị nh Theo c ấu hình resource c ủa máy tính Meta knowledge trong vi ệc đị nh gi ới h ạn độ sâu Gi ới h ạn độ sâu ⇒ co h ẹp không gian tr ạng thái ⇒ có th ể mất nghi ệm 31
Các đ c tr ưng c a bài toán Một s ố y ếu t ố c ần phân tích khi ch ọn k ỹ thu ật gi ải BT: Kh ả n ăng phân rã bài toán Kh ả n ăng l ờ đi và quay lui Kh ả n ăng d ự đoán toàn c ục Đích là m ột tr ạng thái hay con đườ ng (t ập các TT) Lượ ng tri th ức c ần để gi ải bài toán Có c ần s ự can thi ệp c ủa con ng ườ i trong quá trình gi ải không? 32
Các đ c tr ưng c a bài toán (tt) Kh ả n ăng phân rã bài toán Phân rã đượ c: nh ư BT tính tích phân ký hi ệu Gi ải b ằng cách Chia nh ỏ BT l ớn thành các BT con độ c l ập Gi ải t ừng BT nh ỏ Kết h ợp thành BT l ớn Không phân rã đượ c: BT th ế gi ới các kh ối (??) 33
Các đ c tr ưng c a bài toán (tt) Các b ướ c gi ải có th ể l ờ đi hay quay lui Có th ể l ờ đi : nh ư BT ch ứng minh đị nh lý Vì: đị nh lý v ẫn đúng sau m ột vài b ướ c áp d ụng các lu ật Có th ể quay lui: nh ư BT 8-puzzle Vì: có th ể di chuy ển theo h ướ ng ng ượ c l ại để v ề TT tr ướ c Không th ể quay lui: nh ư BT ch ơi c ờ Vì: game over! 34
Các đ c tr ưng c a bài toán (tt) Các b ướ c gi ải có th ể l ờ đi hay quay lui: Có th ể l ờ đi : Có th ể áp d ụng chi ến l ượ c điều khi ển đơ n gi ản không c ần quay lui Dể dàng hi ện th ực. Có th ể quay lui: Chi ến l ượ c ph ức t ạp h ơn để quay lui đượ c t ại nh ững b ướ c l ỗi. Có th ể dùng Push-Down Stack. Không th ể quay lui: Dùng các chi ến l ượ c ph ức t ạp h ơn vì m ỗi khi ra quy ết đị nh thì đó là quy ết đị nh cu ối cùng. Có th ể dùng gi ải pháp Planning. Sẽ đượ c xem xét trong các ch ươ ng sau. 35
Các đ c tr ưng c a bài toán (tt) Kh ả n ăng d ự đoán c ủa bài toán: Có th ể d ự đoán đượ c: nh ư BT 8 puzzle ⇒ có th ể đề ra 1 chu ỗi các n ướ c đi và t ự tin vào k ết qua s ẽ xãy ra ⇒ Có th ể quay lui đượ c Không th ể d ự đoán đượ c: nh ư các game có đố i kháng Cần theo đuổi nhi ều k ế ho ạch Có chi ến l ượ c/ đánh giá để ch ọn k ế ho ạch t ốt 36
Các đ c tr ưng c a bài toán (tt) Lời gi ải là tuy ệt đố i hay t ươ ng đố i Tuy ệt đố i (best -path): nh ư bài toán TSP Tính toán khó h ơn (t ổng quát) Cần gi ải thu ật tìm ki ếm toàn di ện h ơn Tươ ng đố i (any-path): nh ư bài toán suy lu ận đờ i th ườ ng (xem sau) Có th ể dùng heuristic để gi ải trong th ời gian h ợp lý 37
Các đ c tr ưng c a bài toán (tt) Lời gi ải là tr ạng thái hay con đườ ng (t ập các TT) Tr ạng thái: nh ư bài toán tìm ra cách hi ểu phù h ợp cho câu. Ví d ụ: “The bank president ate a dish of pasta salad with the fork.” Từng t ừ nh ư: bank, president, có th ể đượ c hi ểu theo nhi ều cách Một ki ểu tìm ki ếm nào đó đượ c th ực hi ện để tìm ra cách hi ểu toàn b ộ cho câu Con đườ ng Song, điều này c ũng t ươ ng đố i. Vì có th ể bi ểu di ễn tr ạng thái để nó có th ể bao g ồm thông tin v ề m ột ph ần hay toàn bộ con đườ ng 38
Các đ c tr ưng c a bài toán (tt) Vai trò c ủa tri th ức là gì? Cần ít tri th ức: Nh ư bài toán: “ch ơi c ờ” Tri th ức ~ lu ật để di chuy ển h ợp l ệ, c ơ ch ế điều khi ển, chi ến l ượ c điều khi ển để t ăng t ốc tìm ki ếm Cần nhi ều tri th ức Nh ư bài toán: Hi ểu câu chuy ện trên t ạp chí Tri th ức: nhi ều, c ả nh ững cái đã ghi t ườ ng minh và c ả nh ững cái không đượ c ghi trong chính câu chuy ện 39
Vn đ trong thi t k CT tìm ki m Sự tìm ki ếm Tìm ki ếm ~ duy ệt cây, t ừ TT b ắt đầ u -> TT đích Cả cây tìm ki ếm th ườ ng không đượ c xây d ựng s ẵn Cấu trúc đồ th ị th ườ ng thay th ế cho cây trong bi ểu di ễn KGTT Các v ấn đề Xác đị nh h ướ ng tìm (forward hay backward reasoning). Cách l ựa ch ọn lu ật để áp d ụng (matching) Cách bi ểu di ễn nút (NODE) c ủa quá trình tìm ki ếm Các NODE trong đồ th ị có th ể đượ c phát sinh nhi ều lần, và có th ể đã đượ c xem xét tr ướ c đó trong quá trình duy ệt ⇒ cần lo ại b ỏ nh ững NODE l ặp l ại ⇒ Cần l ưu lại các NODE đã xét. 40
Vn đ trong thi t k CT Gi ải thu ật ki ểm tra NODE l ặp l ại (DFS): Xem xét t ập NODE đã t ạo ra, để xem NODE m ới đã có ch ưa Nếu ch ưa thì thêm NODE m ới vào đồ th ị Nếu đã có: Thi ết l ập điểm m ở r ộng k ế ti ếp là con c ủa NODE đang tồn t ại , NODE có th ể b ỏ đi Nếu GT có l ưu gi ữ con đườ ng t ốt nh ất hi ện có thì c ần xem xét xem nó đạ t đế n NODE m ới trên con đườ ng t ốt hơn không, n ếu v ậy thì c ập nh ật l ại con đườ ng t ốt nh ất 41
BÀI T ẬP 1 Xét đ th tr ng thái sau đây, v i m i chi n l ư c tìm ki m bên d ư i hãy li t kê v i danh sách th t các nút đư c duy t qua: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1/ Tìm ki m r ng (BFS) 2/ Tìm ki m sâu (DFS) 3/ Tìm ki m sâu v i đ sâu là 3 42
BÀI T ẬP 2 Gi s P là nút m c tiêu c a đ th bên d ư i. Hãy li t kê danh sách th t các nút duy t qua ng v i t ng chi n l ư c tìm ki m. A B C D EGF H I J KL M N O P QN ST U 1/ Tìm ki m r ng (BFS) 2/ Tìm ki m sâu (DFS) 3/ Tìm ki m sâu v i đ sâu là 3 43