Cấu trúc dữ liệu - Tìm kiếm

*TÌM KIẾMRef: Tô Hoài ViệtKhoa Công nghệ Thông tinĐại học Khoa học Tự nhiên TPHCMthviet@fit.hcmuns.edu.vn*Tổng quátBài toán tìm kiếmTìm kiếm Theo chiều RộngTính tối ưu, Tính đầy đủ, Độ phức tạp thời gian và không gianCây Tìm kiếmTìm kiếm Theo chiều Sâu*Một bài toán Tìm kiếmLàm sao để đi từ S đến G? Và số biến đổi có thể ít nhất là gì?STARTGOALdbpqcehafr*Hình thức hoá một bài toán tìm kiếmMột bài toán tìm kiếm có năm thành phần:Q , S , G , succs , costQ là một tập hữu hạn các trạng thái.S  Q một tập khác rỗng các trạng thái ban đầu.G  Q một tập khác rỗng các trạng thái đích.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 trạng thái. succs(s) nghĩa là “tập các trạng thái có thể đến từ s trong một bước”.cost : Q , Q  Số Dương là một hàm nhận hai trạng thái, s và s’, làm đầu vào. Nó trả về chi phí một bước của việc di chuyển từ s đến s’. Hàm chi phí chỉ được định nghĩa khi s’ là trạng thái con của s.*Bài toán Tìm kiếmQ = {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 tất cả các biến đổiSTARTGOALdbpqcehafr*Bài toán Tìm kiếmQ = {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 tất cả các biến đổiSTARTGOALdbpqcehafrTại sao ta quan tâm? Bài toán nào giống như vậy?*Các Bài toán Tìm kiếm*Các Bài toán Tìm kiếmLập lịch8-HậuGì nữa?Giải toán*Tìm kiếm Theo Chiều RộngGán nhãn tất cả trạng 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 tất cả trạng 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 tất cả trạng 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 trạng thái Goal được đi đến.STARTGOALdbpqcehafr*STARTGOALdbpqcehafrTìm kiếm Theo Chiều Rộng0 bước từ start*STARTGOALdbpqcehafrTìm kiếm Theo Chiều Rộng0 bước từ start1 bước từ start*STARTGOALdbpqcehafrTìm kiếm Theo Chiều Rộng0 bước từ start1 bước từ start2 bước từ start*STARTGOALdbpqcehafrTìm kiếm Theo Chiều Rộng0 bước từ start1 bước từ start2 bước từ start3 bước từ start*STARTGOALdbpqcehafrTìm kiếm Theo Chiều Rộng0 bước từ start1 bước từ start2 bước từ start3 bước từ start4 bước từ start*Ghi nhớ đường đi!Ngoài ra, khi gán nhãn một trạng thái, ghi nhận trạng thái trước đó. Ghi nhận này được gọi là con trỏ quay lui. Lịch sử trước đó được dùng để phát sinh con đường lời giải, khi đã tìm được đích:“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”STARTGOALdbpqcehafr*STARTGOALdbpqcehafrCon trỏ quay lui0 bước từ start1 bước từ start2 bước từ start3 bước từ start4 bước từ start*STARTGOALdbpqcehafrCon trỏ quay lui0 bước từ start1 bước từ start2 bước từ start3 bước từ start4 bước từ start*Bắt đầu Tìm kiếm Theo chiều RộngVới bất kỳ trạng thái s nào đã gán nhãn, ghi nhớ:previous(s) là trạng thái trước đó trên đường đi ngắn nhất từ trạng thái START đến s.Trong vòng lặp thứ k của thuật toán ta bắt đầu với Vk được định nghĩa là tập các trạng thái mà từ trạng thái start đi đến có đúng k bướcSau đó, trong suốt vòng lặp, ta sẽ tính Vk+1, được định nghĩa là tập các trạng thái mà từ trạng thái start đi đến có đúng k+1 bướcChúng ta bắt đầu với k = 0, V0 = {START} và định nghĩa, previous(START) = NULLSau đó 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.*STARTGOALdbpqcehafrBFSV0*STARTGOALdbpqcehafrBFSV0V1*STARTGOALdbpqcehafrBFSV0V1V2*STARTGOALdbpqcehafrBFSV0V1V2V3*STARTGOALdbpqcehafrBFSV4V0V1V2V3*Tìm kiếm Theo Chiều RộngV0 := S (tập các trạng thái ban đầu)previous(START) := NILk := 0while (không có trạng thái đích trong Vk và Vk khác rỗng) do Vk+1 := tập rỗng Với mỗi trạng thái s trong Vk Với mỗi trạng thái s’ trong succs(s) Nếu s’ chưa gán nhãn Đặt previous(s’) := s Thêm s’ vào Vk+1 k := k+1If Vk rỗng thì FAILUREElse xây dựng lời giải: Đặt Si là trạng thái thứ i trên đường đi ngắn nhất. Định nghĩa Sk = GOAL, và với mọi i 1)Lđọ dài đường đi từ start đến goal với số bước ngắn nhấtChúng ta đánh giá thuật toán như thế nào?*Đánh giá một thuật toánNsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtQkích cỡ hàng đợi ưu tiên trung bìnhThuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu tất cả chuyển đổi cùng chi phíO(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))*Tìm kiếm Theo Chiều SâuMột thay thế cho BFS. Luôn mở từ node vừa mới mở nhất, nếu nó có bất kỳ node con chưa thử nào. Ngược lại quay lại node trước đó trên đường đi.STARTGOALdbpqcehafr299811235344151552*DFS trên thực tếSTARTSTART dSTART d bSTART d b aSTART d cSTART d c aSTART d eSTART d e rSTART d e r fSTART d e r f cSTART d e r f c aSTART d e r f GOALSTARTGOALdbpqcehafr*Duyệt cây tìm kiếm DFSSTARTGOALdbpqcehafrBạn có thể vẽ thứ tự mà trong đó các node của cây tìm kiếm được viếng?*Thuật toán DFSTa dùng một cấu trúc dữ liệu gọi là Path để biểu diễn đường đi từ START đến trạng thái hiện tại.VD. Path P = Cùng với mỗi node trên đường đi, chúng ta phải nhớ những con nào ta vẫn có thể mở. VD. tại điểm sau, ta cóP = *Thuật toán DFSĐặt P = While (P khác rỗng và top(P) không là đích) if mở rộng của top(P) rỗng then loại bỏ top(P) (“pop ngăn xếp”) else gọi s một thành viên của mở rộng của top(P) loại s khỏi mở rộng của top(P) tạo một mục mới trên đỉnh đường đi P: s (expand = succs(s))If P rỗng trả về FAILUREElse trả về đường đi chứa trạng thái của PThuật toán này có thể được viết gọn dưới dạng đệ qui, dùng ngăn xếp của chương trình để cài đặt P.*Đánh giá một thuật toánThuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu chi phí chuyển đổi như nhauO(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))DFSDepth First SearchNsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtQkích cỡ hàng đợi ưu tiên trung bình*Đánh giá một thuật toánThuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu chi phí chuyển đổi như nhauO(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))DFSDepth First SearchKKN/AN/ANsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtQkích cỡ hàng đợi ưu tiên trung bình*Đánh giá một thuật toánThuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu chi phí chuyển đổi như nhauO(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))DFS**Depth First SearchGiả sử Không gian Tìm kiếm không chu trìnhNsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtLMAXĐộ dài đường đi dài nhất từ start đến bất cứ đâuQkích cỡ hàng đợi ưu tiên trung bình*Thuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu chi phí chuyển đổi như nhauO(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))DFS**Depth First SearchCKO(BLMAX)O(LMAX)Đánh giá một thuật toánGiả sử Không gian Tìm kiếm không chu trìnhNsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtLMAXĐộ dài đường đi dài nhất từ start đến bất cứ đâuQkích cỡ hàng đợi ưu tiên trung bình*Câu hỏi suy nghĩLàm sao để ngăn ngừa lặp vô tận trong DFS ?Làm sao bắt buộc nó đưa ra một lời giải tối ưu?ABABCABABC*Câu hỏi suy nghĩLàm sao để ngăn ngừa lặp vô tận trong DFS ?Làm sao bắt buộc nó đưa ra một lời giải tối ưu?Trả lời 1:PC-DFS (Path Checking DFS):Don’t recurse on a state if that state is already in the current pathTrả lời 2:MEMDFS (Memorizing DFS):Remember all states expanded so far. Never expand anything twice.ABABC*Câu hỏi suy nghĩLàm sao để ngăn ngừa lặp vô tận trong DFS ?Làm sao bắt buộc nó đưa ra một lời giải tối ưu?Trả lời 1:PC-DFS (Path Checking DFS):Không gọi lại một trạng thái nếu nó đã có trên đường điTrả lời 2:MEMDFS (Memorizing DFS):Nhớ tất cả trạng thái đã mở. Không bao giờ mở hai lần.ABABC*Câu hỏi suy nghĩLàm sao để ngăn ngừa lặp vô tận trong DFS ?Làm sao bắt buộc nó đưa ra một lời giải tối ưu?Trả lời 1:PC-DFS (Path Checking DFS):Không gọi lại một trạng thái nếu nó đã có trên đường điTrả lời 2:MEMDFS (Memoizing DFS):Nhớ tất cả trạng thái đã mở. Không bao giờ mở hai lần.Có khi nào PCDFS tốt hơn MEMDFS không?Có khi nào MEMDFS tốt hơn PCDFS không?*Thuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu chi phí chuyển đổi như nhau (1)O(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))PCDFSPath Check DFSCKO(BLMAX)O(LMAX)MEMDFSMemoizing DFSCKO(min(N,BLMAX))O(min(N,BLMAX))IDIterative DeepeningY(1)O(BL)O(L)Nsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtLMAXĐộ dài đường đi không chu trình dài nhất từ start đến bất cứ đâuQkích cỡ hàng đợi ưu tiên trung bình*Lặp Sâu dần Lặp sâu dần là một thuật toán đơn giản dùng DFS làm một thủ tục con:Thực hiện 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 bằng 2)Nếu “1” thất bại, thực hiện DFS chỉ tìm các đường đi có độ dài 2 hay ít hơn.Nếu “2” thất bại, thực hiện DFS chỉ tìm các đường đi có độ dài 3 hay ít hơn. .và tiếp tục cho đến khi thành công.Chi phí làO(b1 + b2 + b3 + b4 + bL) = O(bL)Có thể tốt hơn nhiều so với DFS thông thường. Nhưng chi phí có thể lớn hơn nhiều so với số trạng thái.*Thuật toánĐủTối ưuThời gianKhông gianBFSBreadth First SearchCNếu chi phí chuyển đổi như nhauO(min(N,BL))O(min(N,BL))LCBFSLeast Cost BFSCCO(BL)O(min(N,BL))UCSUniform Cost SearchCCO(log(Q) * min(N,BL))O(min(N,BL))PCDFSPath Check DFSCKO(BLMAX)O(LMAX)MEMDFSMemoizing DFSCKO(min(N,BLMAX))O(min(N,BLMAX))Đánh giá một thuật toánNsố trạng thái trong bài toánBthừa số phân nhánh trung bình (số con trung bình) (B>1)Lđộ dài đường đi từ start đến goal với số bước (chi phí) ít nhấtLMAXĐộ dài đường đi không chu trình dài nhất từ start đến bất cứ đâuQkích cỡ hàng đợi ưu tiên trung bình*Điều cần nắmHiểu thấu đáo về BFS, LCBFS, UCS, DFS, PCDFS, MEMDFSHiểu các khái niệm về việc liệu một tìm kiếm là đầy đủ, tối ưu hay không, độ phức tạp về thời gian và không gian của nóHiểu ý tưởng đằng sau lặp sâu dần.