Trí Tuệ Nhân Tạo – Cải Tiến Thuật Toán Tìm Kiếm Sâu Lặp - Đồ thị không gian trạng thái

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


]

[]

[A
0
]

2

1

[D
1
]

[B
1
], [C
1
],[F
2
]

[]

[A
0
],[D
1

[C
1
]

[B
1
],[E
2
]

[F
2
]

[A
0
],[D
1
],[C
1
]
5

1

[E
2
]

[B


[F
2
], [E
2
]

[A
0
],[D
1
],[C
1
],[B
1
]

7

1

[I
2
]

[G
2
]

[F

2
],[I
2
], [G
2
]

[A
0
],[D
1
],[C
1
],[B
1
]2[G
2
],[I
2
],[E
2
],
[F
2

]

[]

[A
0
],[D
1
],[C
1
],[B
1
],[F
2
] I F
A
G
E
D
C
B
K
L
Generated by Foxit PDF Creator © Foxit Software

A

A

A

C

D

B

B

F

nullTheo mảng Father ta tìm được đường đi : A D F 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.

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;

Generated by Foxit PDF Creator © Foxit Software
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 u
0
;
If u
0
là đích then
Begin
Thông báo đỉnh ban đầu cũng là đỉnh kết thúc;
Exit;