BREATH FIRST SEARCH

BREATH FIRST SEARCH

1. 1. Thuật toán Breadth First Search:
      • Đây là thuật toán tìm đường đi từ đỉnh xuất phát đến đỉnh kết thúc bằng các duyệt theo chiều rộng.
      • Đây là thuật toán nằm trong nhóm thuật toán tìm kiếm mù, thuật toán không quan tâm đến trọng số trên đường đi mà chỉ duyệt theo những đỉnh kề liên tiếp nó.
      • Xuất phát tử một đỉnh và đi tới các đỉnh kề nó, tiếp tục cho đến khi không còn đỉnh nào để đi.
      • Trong quá trình đi đến đỉnh kề, tiến hành lưu lại đỉnh kề để khi đi ngược lại từ đỉnh kết thúc đến đỉnh xuất phát ta có được đường đi ngắn nhất.
      • Mô tả thuật toán:  Cách đỉnh đã được xét thì không thể xét lại lần 2 nữa. Cơ chế lưu lại đỉnh kề sẽ là lưu các đỉnh kề thành 1 danh sách và lấy từ từ danh sách các đỉnh kề ra để xét, khi mà một đỉnh kề của một đỉnh đang xét được thêm vào danh sách thì nó sẽ được thêm vào cuối của danh sách hay còn gọi là cơ chế Queue(hàng đợi). Cơ chết này có nghĩa khi thêm một phần tử thì phần tử đó sẽ được thêm ở cuối danh sách hàng đợi, còn lấy phần tử ra thì sẽ lấy ra ở đầu danh sách hàng đợi. Đó chính là điểm nổi bật để phân biệt thuật toán này với các thuật toán khác.

• • • Ưu điểm
• Dễ cài đặt.
• Nếu số đỉnh là hữu hạn, thuật toán chắc chắn tìm ra kết quả.
  • • Khuyết điểm

• Mang tính chất vét cạn, không nên áp dụng nếu duyệt số đỉnh quá lớn.
• Mang tính chất mù quáng, duyệt tất cả đỉnh, không chú ý đến thông tin trong các đỉnh để duyệt hiệu quả, dẫn đến duyệt qua các đỉnh không cần thiết
• Chiếm thời gian và không gian bộ nhớ khi số đình duyệt nhiều.

• • •  
    • Chi tiết chạy từng bước của thuật toán BFS:

Breadth_First_Search (BFS)

Begin            Bước 1: Khởi tạo danh sách L chỉ chứa trạng thái ban đầu

            Bước 2: Loop do

                                  2.1 If L rỗng then

                                              {Thông báo tìm kiếm thất bại; Stop};

                                           2.2 Loại trạng thái u ở đầu danh sách L;

                                           2.3 If u là trạng thái kết thúc then

                                                       {Thông báo tìm kiếm thành công; Stop};

                                           2.4 for mỗi trạng thái v kề với trạng thái u do

{Đặt v vào cuối danh sách L;

                                                                        father(v) = u};