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.
Nội dung trích xuất từ 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 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 A B D C I F L E G K - Đồ thị không gian trạng tháiDemo 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 d Xét Đỉnh OPEN NEXT CLOSEduyệt 1 [A0] [] []1 1 [A0] [B1], [C1], [D1] [] [A0]2 1 [D1] [B1], [C1],[F2] [] [A0],[D1]3 1 [F2] [B1], [C1] [F2] [A0],[D1]4 1 [C1] [B1],[E2] [F2] [A0],[D1],[C1]5 1 [E2] [B1] [F2], [E2] [A0],[D1],[C1]6 1 [B1] [G2],[I2] [F2], [E2] [A0],[D1],[C1],[B1]7 1 [I2] [G2] [F2], [E2],[I2] [A0],[D1],[C1],[B1]8 1 [G2] [] [F2], [E2],[I2], [G2] [A0],[D1],[C1],[B1] 2 [G2],[I2],[E2],[F2] [] [A0],[D1],[C1],[B1]9 2 [F2] [G2],[I2],[E2],[K3] [] [A0],[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 LFather null A A A C D B B F nullTheo mảng Father ta tìm được đường đi : A D F KFather 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.U0 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) Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only.Procudure Interative_Depening_Search;Begin Khởi tạo danh sách OPEN rỗng ; Khởi tạo danh sách CLOSE rỗng ; Khởi tạo danh sách NEXT chứa u0 ; If u0 là đích then Begin Thông báo đỉnh ban đầu cũng là đỉnh kết thúc; Exit; End; For d  1 to max do //dự đoán bước nhảy d sao cho phù hợp với bài toán. Begin Copy danh sách NEXT vào danh sách OPEN; Xóa danh sách NEXT ( về trạng thái rỗng ); Depth_Limited_Search(d); If ( thành công ) then exit ; End; Thông báo không tìm thấy ;End; 26/9/2010 --LeeThong--Generated by Foxit PDF Creator © Foxit Softwarehttp://www.foxitsoftware.com For evaluation only. ...