Kĩ thuật lập trình - Chương 2: Biểu diễn bài toán và tìm lời giải

1Chương 2: Biểu diễn bài toán & tìm lời giải 2Nội 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ế CT tìm kiếm 3Mô hình ứng dụng của TTNT TTNT = Presentation & Search Tri Thức Knowledge Engineering Tìm kiếm Search Suy luận Heurictic 4Bà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: 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)
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 O Trạng thái Trạng thái O X Trạng thái 5Bài toán (tt)
Chuyển trạng thái, luật chuyển  Biểu diễn cho sự có thể 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 6Bà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 OX X XO
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  Ví dụ: game tic-tac-toe, trạng thái ñích là: 7Bà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ể 8Bà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 ñối tượng 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 9Bài toán (tt) State Space
Không gian tìm kiếm thường là một graph
Mục tiêu tìm kiếm là một path
Phải lưu trữ toàn bộ không gian trong quá trình tìm kiếm
Không gian tìm kiếm biến ñộng liên tục trong quá trình tìm kiếm
ðặc tính của trạng thái/nút là phức tạp & biến ñộng Database
Không gian tìm kiếm là một list hay tree
Tìm kiếm một record/nút
Phần tử ñã duyệt qua là không còn dùng tới
Không gian tìm kiếm là cố ñịnh trong quá trình tìm kiếm
Thuộc tính của một record/nút là cố ñịnh 10 Bài toán: Tic tac toe ðồ thị có hướng không lặp lại (directed acyclic graph - DAG) 11 Bài toán: 8 puzzle Có khả năng xảy ra vòng lặp không? 12 Chiến lược ñiều khiển
Sự cần thiết của chiến lược ñiều khiển  ðể giải ñược và giải nhanh bài toán
Các yêu cầu của 1 chiến lược tốt  Tạo ra sự thay ñổi  Có tính hệ thống.
Chọn luật radom -> tốt hơn so với trường hợp ñầu, nhưng quá trình giải có thể dài hơn
-> Cần xây dựng khả năng duyệt một cách có hệ thống  Hai cách duyệt có hệ thống: Breadth-First_Search – BrFS và Depth-First-Search (DFS) ñược trình bày sau 13 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. 14 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; 15 Breadth-First-Search (tt) [ ] [A] [A B] [A B C ] [A B C D ] [A B C D E ] [A B C D E F ] [A B C D E F ] [A ] [B C D ] [C D E F ] [D E F G ] [E F G ] [F G H I ] [G H I J ] [H I J ] A B C D E F G 0 1 2 3 4 5 6 7 CloseOpenXLaàn laëp A B C D E F G H I J 16 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 17 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; 18 Depth-First-Search (tt) [ ] [A] [A B] [A B E ] [A B E H ] [A B E H I ] [A B E H I F ] [A B E H I F J ] [A B E H I F J C ] [A] [B C D ] [E F C D ] [H I F C D ] [I F C D ] [F C D ] [J C D ] [C D ] [ G D ] A B E H I F J C G 0 1 2 3 4 5 6 7 8 9 CloseOpenXLaàn laëp A B C D E F G H I J 19 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 giaỉ 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 20 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 21 BT: Traveling Salesman Problem (TSP)
Mô tả: người bàn hàng có N thành phố phải ñi qua, chỉ ñi qua 01 lần/Tp. Mỗi cặp TP có con ñường nối. Tìm con ñường ngắn nhất ñi vòng qua các thành phố và trở lại Tp ban ñầu.  Số con ñường: (N-1)! ->Bùng nổ tổ hợp -> cần chiến lược mới như sau  Kỹ thuật: Nhánh và Cận (branch-and-bound):
Giữ con ñường ngắn nhất ñang xét.
Dừng việc xem xét 1 con ñường nào ñó nếu nó có trị lớn hơn con ñường ngắn nhất ñang xét. 22 Heuristic search (informed search)
Là kỹ thuật cải tiến hiệu quả quá trình tìm kiếm
General-purpose:  Người láng giềng gần nhất:
Bằng cách chọn cách tốt nhất tại mỗi bước.
TSP: Tại mổi thành phố, chọn TP kế tiếp gần nhất -> time là N2 ( cũ là N!)
Special-purpose: hai cách tham gia vào tìm kiếm:  Chính trong các luật.  Hàm heuristic: ñáng giá ưu thế của từng TT cụ thể và chọn TT mong muốn. Có một trade-off giữa thời gian tính hàm và thời gian có lợi do hàm mang lại 23 Heuristic search
Ví dụ  Chess: Ưu thế trên ñối thủ  TSP: Tổng khoảng cách hiện tại  8 puzzle: Tổng khoảng cách các miếng sai vị trí 24 Các ñặc trưng của bài toán
Một số khía cạnh 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à trạng thái hay con ñường  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? 25 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 (??) 26 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! 27 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. 28 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 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 29 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 GT tì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ý 30 Các ñặc trưng của bài toán (tt)
Lời giải là trạng thái hay con ñường  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 31 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 32 Vấn ñề 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 NODE của quá trình tì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. 33 Vấn ñề 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 34 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 10 8 11 15 12 16 17 9 13 14 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 35 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. 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