BFS THUẬT TOÁN TÌM KIẾM THEO CHIỀU RỘNG
Trong trí tuệ nhân tạo hay lý thuyết đồ thị, thuật toán tìm kiếm theo chiều rộng (BFS) là một thuật toán phát triển các nút chưa xét theo chiều rộng và các nút được xét theo thứ tự độ sâu tăng dần .BFS phù hợp với các bài toán tìm đường từ gốc đến 1 điểm đích cho trước và thuật toán sẽ tốt nhất khi ở trong đồ thị không có trọng số. khi đó, thuật toán sẽ luôn tìm được đường tới đích ngắn nhất có thể.
Cách cài đặt giải thuật :
Mô tả :
- fringe : là một cấu trúc kiểu hàng đợi (FIFO) lưu giữ các nút sẽ được duyệt
- closed : cấu trúc hàng đợi queue lưu giữ các nút đã được duyệt .
- G(N, A) : cây biểu diễn không gian trạng thái bài toán.
- no : trạng thái đầu của bài toán
- DICH : tập hợp các trạng thái đích của bài toán.
- NB(n) : tập hợp các trạng thái con của cua nút đang xét n
Mô tả :
- Chèn đỉnh gốc no vào hàng đợi
- Lấy ra đỉnh đầu tiên trong hàng đợi và thăm nó
- Nếu đỉnh này chính là đỉnh đích, dừng quá trình tìm kiếm và trả về kết quả.
- Nếu không phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được thăm trước đó vào hàng đợi.
- Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được thăm – dừng việc tìm kiếm và trả về "không thấy".
- Nếu hàng đợi không rỗng thì quay về bước 2.
ví dụ minh họa :
Giả sử ta có đồ thị :
Để được giải thích chi tiết và code của thuật toán trong C xin xem video sau :
Comments
Post a Comment