Đề tài Cài đặt thuật toán tìm kiếm sâu dần

Bài Tập Lớn Môn Trí Tuệ Nhân Tạo Đề Tài : Cài đặt thuật toán tìm kiếm sâu dần *Mục Lục 1. Kỹ Thuật tìm kiếm sâu dần. 2. Giải thuật. 3. Nhận xét. 4.Ví dụ. 1.Tìm kiếm sâu dần (Iterative deepening search) Kết hợp của tìm kiếm rộng và tìm kiếm sâu trên cơ sở cho biết mức sâu n rồi tìm kiếm rộng ứng mới mức sâu đó. Chúng ta có nhận xét, nếu cây tìm kiếm chứa nhánh vô hạn , khi sử dụng tìm kiếm theo độ sâu, ta có thể mắc kẹt ở đó và không tìm ra nghiệm. Nếu cây chứa nhiều nhánh thì có thể mắc kẹt và không tìm ra nghiệm khi sử dụng tìm kiếm chiều rộng. Để khắc phục điều đó, ta tìm kiếm theo độ sâu chỉ tới mức d nào đó, nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu d+1.quá trình này được lặp lại với d lần lượt là 1, 2, .. đến một độ sâu max nào đó. Như vậy, thuật toán tìm kiếm sâu dần (DDS)sử dụng thủ tục tìm kiếm sâu hạn chế(DLS) như thủ tục con. 2. Giải thuật. Trong thủ tục tìm kiếm sâu hạn chế, d là tham số đọ sâu, hàm depth ghi lại độ sâu của mỗi đỉnh Procedure DLS(d); Begin khởi tạo danh sách L chỉ chứa trạng thái ban đầu u0; depth(u0)<-0; 2.loop do 2.1 if L rỗng then {thông báo thất bại ;stop}; 2.2 Loại trạng thái u ở đầu danh sách L; 2.3 if u là trạng thái kết thúc then {thong báo thành công; Stop}; 2.4 if depth(u)<=d then For mỗi trạng thái v kề u do {đặt v vào đầu danh sách L; depth(v)<-depth(u)+1}; End; Procedure DDS; Begin For d<-0 to max do {DLS(d); If thành công then exit} End; 3.Nhận xét. Kỹ thuật tìm kiếm sâu dần kết hợp ưu điểm của tìm kiếm bề rông và tìm kiếm theo độ sâu. -Chỉ cần không gian nhớ như tìm kiếm theo độ sâu. -Trong tìm kiếm sâu dần , ta phải phát triển lặp lại nhiều lần cùng một trạng thái .Điều đó cho ta cảm giac lãng phí thời gian , tuy nhiên thời gian phát triển lặp lại ấc trạng thái là không đáng kể so với tìm kiếm chiều rộng. Mỗi lần gọi thủ tục tìm kiếm sâu hạn chế tới mức d, nếu cây tìm kiếm có nhân tố nhánh b, thì số đỉnh cần phát triển là : 1 +b +b2 + …+bd . Nếu nghiệm ở độ sâu d, thì trong tìm kiếm sâu dần, ta phải gọi thủ tục tìm kiếm sâu hạn chế với mức độ sâu lần lượt là 0, 1, 2,..,d . Do đó các đỉnh ở mức 1 phải phát triển lặp d lần. các đỉnh ở mức 2 lặp d-1 lần,..,các đỉnh mức d lặp 1 lần. Như vậy tổng số đỉnh cần phát triển là (d+1)1+db+(d-1)b2+…+2bd-1+1bd. Do đó thời gian tìm kiếm độ sâu lặp là O(bd). Tóm lại. Tìm kiếm sâu dần có độ phức tạp thời gian la O(bd)(bằng độ phức tạp của tk rộng) và độ phức tạp không gian là O(bd) (như tk chiều sâu).>>Đây là chiến lược tìm kiếm tốt nhất trong các chiến lược tìm kiếm mù 4.Minh họa: Tìm kiếm sâu dần l =0: Tìm kiếm sâu dần l =1: Tìm kiếm sâu dần l =2: Tìm kiếm sâu dần l =3: