Đang chuẩn bị liên kết để tải về tài liệu:
Trí Tuệ Nhân Tạo – Cải Tiến Thuật Toán Tìm Kiếm Sâu Lặp

OPEN là danh sách để lưu các đỉnh đã được sinh ra và chờ phát triển ( chờ duyệt ). CLOSE là danh sách để lưu các đỉnh đã phát triển ( đã duyệt ). NEXT là danh sách để lưu các đỉnh đã được sinh ra nhưng có Depth ( độ sâu ) lớn hơn d. OPEN , NEXT , CLOSE kiểu Stack. U0 là đỉnh ban đầu. Father là danh sách để ghi lại cha của mỗi đỉnh trên đường đi. | Generated by Foxit PDF Creator Foxit Software http www.foxitsoftware.com For evaluation only. Trí Tuệ Nhân Tạo - Cải Tiến Thuật Toán Tìm Kiếm Sâu Lặp Demo tìm kiếm đường đi từ đỉnh trạng thái A đến đỉnh K với bước nhảy độ sâu là 1 . Lần duyệt d Xét Đỉnh OPEN NEXT CLOSE 1 Ao 1 1 Ao B1 C1 D1 Ao 2 1 D1 B1 C1 F2 AoL D1 3 1 F2 B1 C1 F2 AoL D1 4 1 C1 B1 E2 F2 Ao D1 C1 5 1 E2 B1 F2 E2 Ao D1 C1 6 1 B1 G2 I2 F2 E2 Ao D1 C1 B1 7 1 I2 G2 F2 E2 i2 Ao D1 C1 B1 8 1 GJ F2 E2 i2 G2 Ao D1 C1 B1 2 G2 i2 E2 F2 Ao D1 C1 B1 9 2 F2 G2 i2 E2 K3 Ao D1 C1 B1 F2 Generated by Foxit PDF Creator Foxit Software http www.foxitsoftware.com For evaluation only. Mảng Father sau khi tìm được đỉnh K Đỉnh A B C D E F G I K L Father null A A A C D B B F null Theo mảng Father ta tìm được đường đi A-----k D---- F------k K Father của A là null vì A là root. Father của L là null vì L chưa được sinh ra trong OPEN chưa tìm thấy . Muốn tìm thấy đỉnh đích có độ sâu là n thì chỉ cần duyệt đến độ sâu n-1 là sẽ tìm thấy . Mã giả của thuật toán OPEN là danh sách để lưu các đỉnh đã được sinh ra và chờ phát triển chờ duyệt . CLOSE là danh sách để lưu các đỉnh đã phát triển đã duyệt . NEXT là danh sách để lưu các đỉnh đã được sinh ra nhưng có Depth độ sâu lớn hơn d. OPEN NEXT CLOSE kiểu Stack. Uo là đỉnh ban đầu. Father là danh sách để ghi lại cha của mỗi đỉnh trên đường đi. Hàm Depth dung để ghi lại độ sâu của mỗi đỉnh. Generated by Foxit PDF Creator Foxit Software http www.foxitsoftware.com For evaluation only. Procedure Depth_Limited_Search d Begin While OPEN khác rỗng do Begin Xóa đỉnh u ở đầu OPEN If Depth u d then Begin Thêm u vào CLOSE For mỗi trạng thái v kề u do If v chưa xuất hiện trong OPEN và NEXT và CLOSE then Begin Father v u If v là đích then Begin Thông báo tìm kiếm thành công Exit End Thêm v vào đầu OPEN Depth v Depth u 1 End End Else Begin Thêm u vào NEXT End End End