Tất cả những gì bạn cần biết về thuật toán tìm kiếm đầu tiên theo chiều rộng

Phương pháp Graph Traversal luôn khiến tôi khá thích thú. Từ thực hiện giao tiếp ngang hàng hiệu quả đến việc tìm kiếm các nhà hàng và quán cà phê gần nhất bằng cách sử dụng GPS, các phương pháp truyền tải có một loạt các ứng dụng trong kịch bản thế giới thực. Trong blog này về Thuật toán tìm kiếm theo chiều rộng-Đầu tiên, chúng ta sẽ thảo luận về logic đằng sau các phương pháp duyệt biểu đồ và sử dụng các ví dụ để hiểu hoạt động của thuật toán Tìm kiếm theo chiều rộng-Đầu tiên.

Để có kiến ​​thức chuyên sâu về Trí tuệ nhân tạo và Máy học, bạn có thể đăng ký trực tiếp của Edureka với hỗ trợ 24/7 và quyền truy cập trọn đời.

Đây là danh sách các chủ đề sẽ được đề cập trong blog này:

1. Giới thiệu về truyền tải đồ thị
2. Tìm kiếm theo chiều rộng-đầu tiên là gì?
3. Hiểu thuật toán Breadth-First Search với một ví dụ
4. Mã giả của thuật toán tìm kiếm đầu tiên theo chiều rộng
5. Các ứng dụng của Breadth-First Search

Giới thiệu về truyền tải đồ thị

Quá trình truy cập và khám phá một biểu đồ để xử lý được gọi là duyệt đồ thị. Cụ thể hơn, đó là tất cả về việc thăm và khám phá từng đỉnh và cạnh trong đồ thị sao cho tất cả các đỉnh được khám phá chính xác một lần.

Điều đó nghe có vẻ đơn giản! Nhưng có một cơ hội.

Có một số kỹ thuật duyệt biểu đồ như Tìm kiếm đầu tiên theo chiều rộng, Tìm kiếm đầu tiên theo chiều sâu, v.v. Thách thức là sử dụng một biểu đồ kỹ thuật duyệt phù hợp nhất để giải quyết một vấn đề cụ thể. Điều này đưa chúng ta đến với kỹ thuật Breadth-First Search.

fibonacci đệ quy c ++

Thuật toán tìm kiếm theo chiều rộng-đầu tiên là gì?

Thuật toán Breadth-First Search là một kỹ thuật duyệt biểu đồ, trong đó bạn chọn một nút ban đầu ngẫu nhiên (nút nguồn hoặc nút gốc) và bắt đầu duyệt qua lớp biểu đồ theo cách mà tất cả các nút và các nút con tương ứng của chúng đều được truy cập và khám phá.

Trước khi chúng ta đi sâu hơn và hiểu Tìm kiếm theo chiều rộng-Đầu tiên bằng một ví dụ, hãy làm quen với hai thuật ngữ quan trọng liên quan đến truyền qua biểu đồ:

1. Ghé thăm một nút: Giống như tên cho thấy, ghé thăm một nút có nghĩa là truy cập hoặc chọn một nút.
2. Khám phá một nút: Khám phá các nút lân cận (nút con) của một nút đã chọn.

Tham khảo hình trên để hiểu rõ hơn.

Hiểu thuật toán tìm kiếm theo chiều rộng-đầu tiên với một ví dụ

Thuật toán Breadth-First Search tuân theo một cách tiếp cận đơn giản dựa trên mức độ để giải quyết một vấn đề. Hãy xem xét cây nhị phân dưới đây (là một đồ thị). Mục đích của chúng tôi là duyệt qua biểu đồ bằng cách sử dụng Thuật toán tìm kiếm theo chiều rộng-đầu tiên.

Trước khi chúng ta bắt đầu, bạn phải làm quen với cấu trúc dữ liệu chính liên quan đến thuật toán Breadth-First Search.

Hàng đợi là một cấu trúc dữ liệu trừu tượng tuân theo phương pháp nhập trước vào trước (dữ liệu được đưa vào trước sẽ được truy cập trước). Nó được mở ở cả hai đầu, trong đó một đầu luôn được dùng để chèn dữ liệu (enqueue) và đầu kia được dùng để xóa dữ liệu (dequeue).

Bây giờ chúng ta hãy xem xét các bước liên quan đến việc duyệt qua biểu đồ bằng cách sử dụng Tìm kiếm theo chiều rộng-Đầu tiên:

Bước 1: Lấy hàng đợi trống.

Bước 2: Chọn một nút bắt đầu (truy cập một nút) và chèn nó vào Hàng đợi.

Bước 3: Miễn là Hàng đợi không trống, hãy trích xuất nút từ Hàng đợi và chèn các nút con của nó (khám phá một nút) vào Hàng đợi.

Bước 4: In nút đã trích xuất.

Đừng lo lắng nếu bạn bối rối, chúng tôi sẽ hiểu điều này bằng một ví dụ.

Hãy xem biểu đồ bên dưới, chúng tôi sẽ sử dụng thuật toán Breadth-First Search để duyệt qua biểu đồ.

Trong trường hợp của chúng tôi, chúng tôi sẽ chỉ định nút ‘a’ làm nút gốc và bắt đầu di chuyển xuống dưới và làm theo các bước được đề cập ở trên.

Hình ảnh trên mô tả quá trình end-to-end của Breadth-First Search Algorithm. Hãy để tôi giải thích điều này sâu hơn.

1. Gán ‘a’ làm nút gốc và chèn nó vào Hàng đợi.
2. Trích xuất nút ‘a’ từ hàng đợi và chèn các nút con của ‘a’, tức là ‘b’ và ‘c’.
3. In nút ‘a’.
4. Hàng đợi không trống và có nút ‘b’ và ‘c’. Vì ‘b’ là nút đầu tiên trong hàng đợi, hãy giải nén nó và chèn các nút con của ‘b’, tức là nút ‘d’ và ‘e’.
5. Lặp lại các bước này cho đến khi hàng đợi trống. Lưu ý rằng các nút đã được truy cập sẽ không được thêm vào hàng đợi lần nữa.

Bây giờ chúng ta hãy xem xét mã giả của thuật toán Breadth-First Search.

Mã giả của thuật toán tìm kiếm đầu tiên theo chiều rộng

Đây là mã giả để triển khai Thuật toán tìm kiếm theo chiều rộng-đầu tiên:

Đầu vào: s là nút nguồn BFS (G, s) cho Q là hàng đợi. Q.enqueue (các) mark s là đã thăm trong khi (Q không trống) v = Q.dequeue () cho tất cả các lân cận w của v trong Đồ thị G nếu w không được truy cập Q.enqueue (w) mark w là đã thăm

Trong đoạn mã trên, các bước sau được thực hiện:

1. (G, s) là đầu vào, ở đây G là đồ thị và s là nút gốc
2. Hàng đợi ‘Q’ được tạo và khởi tạo bằng nút nguồn ‘s’
3. Tất cả các nút con của 's' đều được đánh dấu
4. Trích xuất 's' từ hàng đợi và truy cập các nút con
5. Xử lý tất cả các nút con của v
6. Lưu trữ w (nút con) trong Q để truy cập thêm vào các nút con của nó
7. Tiếp tục cho đến khi ‘Q’ là trống

Trước khi kết thúc blog, chúng ta hãy xem xét một số ứng dụng của thuật toán Breadth-First Search.

Ứng dụng của thuật toán tìm kiếm đầu tiên theo chiều rộng

Tìm kiếm theo chiều rộng là một phương pháp duyệt đồ thị đơn giản có nhiều ứng dụng đáng ngạc nhiên. Dưới đây là một số cách thú vị mà Tìm kiếm trên bánh mì đang được sử dụng:

Trình thu thập thông tin trong Công cụ Tìm kiếm: Breadth-First Search là một trong những thuật toán chính được sử dụng để lập chỉ mục các trang web. Thuật toán bắt đầu duyệt từ trang nguồn và đi theo tất cả các liên kết được liên kết với trang. Ở đây mỗi trang web sẽ được coi là một nút trong biểu đồ.

Hệ thống định vị GPS: Breadth-First Search là một trong những thuật toán tốt nhất được sử dụng để tìm các vị trí lân cận bằng cách sử dụng hệ thống GPS.

Tìm Đường dẫn ngắn nhất & Cây kéo dài tối thiểu cho đồ thị không có trọng số: Khi nói đến một đồ thị không có trọng số, việc tính toán đường đi ngắn nhất khá đơn giản vì ý tưởng đằng sau đường đi ngắn nhất là chọn một đường đi có số cạnh ít nhất. Breadth-First Search có thể cho phép điều này bằng cách duyệt qua một số lượng tối thiểu các nút bắt đầu từ nút nguồn. Tương tự như vậy, đối với cây bao trùm, chúng ta có thể sử dụng một trong hai phương pháp Breadth-First Search hoặc Depth-first traversal để tìm cây bao trùm.

Phát thanh truyền hình: Mạng sử dụng những gì chúng ta gọi là các gói để liên lạc. Các gói này tuân theo một phương thức truyền tải để đến các nút mạng khác nhau. Một trong những phương pháp duyệt được sử dụng phổ biến nhất là Breadth-First Search. Nó đang được sử dụng như một thuật toán được sử dụng để giao tiếp các gói được quảng bá trên tất cả các nút trong mạng.

Mạng ngang hàng: Breadth-First Search có thể được sử dụng như một phương pháp duyệt để tìm tất cả các nút lân cận trong Mạng ngang hàng. Ví dụ: BitTorrent sử dụng Breadth-First Search để giao tiếp ngang hàng.

Đó là tất cả về hoạt động của thuật toán Breadth-First Search. Bây giờ bạn đã biết cách duyệt qua biểu đồ, tôi chắc chắn rằng bạn muốn tìm hiểu thêm. Dưới đây là một số blog có liên quan để bạn quan tâm:

3. Giới thiệu về chuỗi Markov với ví dụ - Chuỗi Markov với Python

Với điều này, chúng ta đến phần cuối của blog này. Nếu bạn có bất kỳ thắc mắc nào liên quan đến chủ đề này, vui lòng để lại bình luận bên dưới và chúng tôi sẽ liên hệ lại với bạn.

Nếu bạn muốn đăng ký một khóa học hoàn chỉnh về Trí tuệ nhân tạo và Học máy, Edureka có một điều đó sẽ giúp bạn thành thạo các kỹ thuật như Học có giám sát, Học không giám sát và Xử lý ngôn ngữ tự nhiên. Nó bao gồm đào tạo về những tiến bộ và phương pháp tiếp cận kỹ thuật mới nhất trong Trí tuệ nhân tạo & Máy học như Học sâu, Mô hình đồ họa và Học tăng cường.