Etiam id libero non erat fermentum varius eget at elit.
Suspendisse vel mattis diam.
Ut sed dui in lectus hendrerit interdum nec ac neque.
Praesent a metus eget augue lacinia accumsan ullamcorper sit amet tellus.
Duis cursus egestas hendrerit.
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 : 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 sau đây là giải thuật : 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ì...
Comments
Post a Comment