Download miễn phí Bài tập lớn Cài đặt thuật toán tìm kiếm sâu dần
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ù
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
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:
...