Các phương pháp Graph Traversal luôn khiến tôi thích thú. Từ việc 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.
Dưới đây là danh sách các chủ đề sẽ được đề cập trong bài viết này:
- Giới thiệu về truyền tải đồ thị
- Tìm kiếm theo chiều rộng-đầu tiên là gì?
- Hiểu thuật toán Breadth-First Search với một ví dụ
- Mã giả của thuật toán tìm kiếm đầu tiên theo chiều rộng
- Các ứng dụng của Breadth-First Search
Quá trình truy cập và khám phá một biểu đồ để xử lý được gọi là truyền qua biểu đồ. 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 theo chiều rộng-Đầu tiên, Tìm kiếm đầu tiên theo chiều sâu, v.v. Thách thức là sử dụng kỹ thuật duyệt đồ thị 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 Tìm kiếm theo chiều rộng-Đầu tiên.
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 đồ thị, 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 đồ:
- Ghé thăm một nút: Giống như tên cho thấy, truy cập một nút có nghĩa là truy cập hoặc chọn một nút.
- 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.
Tìm 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 phương pháp đơ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 First-In-First-Out [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 một biểu đồ bằng cách sử dụng Breadth-First Search:
Bước 1: Thực hiện một hàng đợi trống.
Bước 2: Chọn một nút bắt đầu [đang truy cập một nút] và chèn nó vào Hàng đợi.
Bước 3: Với điều kiện là Hàng đợi không trống, 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 đã giải nén.
Đừ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 nhìn vào 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ậ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.
- Gán 'a' làm nút gốc và chèn nó vào Hàng đợi.
- 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'.
- In nút 'a'.
- 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'.
- 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 lại vào hàng đợi.
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:
Input: s as the source node BFS [G, s] let Q be queue. Q.enqueue[ s ] mark s as visited while [ Q is not empty] v = Q.dequeue[ ] for all neighbors w of v in Graph G if w is not visited Q.enqueue[ w ] mark w as visited- [G, s] là đầu vào, ở đây G là đồ thị và s là nút gốc
- Hàng đợi 'Q' được tạo và khởi tạo bằng nút nguồn 's'
- Tất cả các nút con của 's' đều được đánh dấu
- Trích xuất 's' từ hàng đợi và truy cập các nút con
- Xử lý tất cả các nút con của v
- Lưu trữ w [nút con] trong Q để truy cập thêm vào các nút con của nó
- Tiếp tục cho đến khi 'Q' trống
Ứ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 mở rộng 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 pháp truyền tải để đến được 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. Với điều này, chúng ta đi đến phần cuối của bài viết này. Nếu bạn muốn xem thêm các bài viết về các công nghệ thịnh hành nhất trên thị trường như Python, DevOps, Ethical Hacking, thì bạn có thể tham khảo trang web chính thức của Edureka.
Hãy chú ý tìm các bài viết khác trong loạt bài này sẽ giải thích các khía cạnh khác nhau của Khoa học Dữ liệu.
1. Hướng dẫn Khoa học Dữ liệu
2. Toán học và thống kê cho khoa học dữ liệu
3. Hồi quy tuyến tính trong R
4. Thuật toán học máy
5. Hồi quy logistic trong R
6. Giải thuật phân loại
7. Rừng Ngẫu Nhiên Trong R
8. Cây quyết định trong R
9. Giới thiệu về Học máy
10. Naive Bayes ở R
11. Thống kê và Xác suất
12. Làm thế nào để tạo một cây quyết định hoàn hảo?
13. 10 lầm tưởng hàng đầu về vai trò của nhà khoa học dữ liệu
14. Các dự án khoa học dữ liệu hàng đầu
15. Nhà phân tích dữ liệu so với Kỹ sư dữ liệu và Nhà khoa học dữ liệu
16. Các loại trí tuệ nhân tạo
17. R vs Python
18. Trí tuệ nhân tạo so với Học máy và Học sâu
19. Dự án Máy học
20. Câu hỏi và câu trả lời phỏng vấn nhà phân tích dữ liệu
21. Khoa học dữ liệu và công cụ học máy cho người không phải lập trình viên
22. 10 khuôn khổ học máy hàng đầu
23. Thống kê cho Học máy
24. Rừng Ngẫu Nhiên Trong R
25. Học tập có giám sát
26. Phân tích phân biệt tuyến tính trong R
27. Điều kiện tiên quyết cho Học máy
28. Các ứng dụng web tương tác sử dụng R Shiny
29. 10 cuốn sách hàng đầu về học máy
30. Học không giám sát
31. 10 cuốn sách hay nhất về khoa học dữ liệu
32. Máy học sử dụng R
Được xuất bản lần đầu tại //www.edureka.co vào ngày 6 tháng 9 năm 2019.
Bài hôm nay chúng ta cùng tìm hiểu về thuật toán tìm Breadth First Search [tìm kiếm theo chiều rộng] 1. Kiến thức cơ bản về thuật toán BFS.
+Breadth First Search là một thuật toán duyệt hoặc tìm kiếm một phần tử trên một cấu trúc dữ liệu dạng cây hay một đồ thị.
+ Nó khác với DFS đó là nó sẽ ưu tiên theo chiều ngang, nghĩa là duyệt từ trái qua phải hết rồi mới duyệt tiếp xuống dưới cho từng phần tử
Như vậy thứ tự đi trong hình minh họa ở trên như sau:
- Bắt đầu từ 1 => 2 => 7 => 8 => hết node ngang.
- Tiếp tục 2 => 3 => 6 hết node ngang.
- Bắt đầu 7 => không có node ngang.
- Tiếp tục 8=>9 => 12 hết node ngang
- Bắt đầu 3 => 4 => 5 => hết node ngang
- Tiếp tục 6 => không có node ngang
- Bắt đầu 9 => 10=> 11 hết node ngang
- Tiếp tục 12 => không có node ngang
- Bắt đầu 4 => hết node
- Tiếp tục 5 => hết node
- Bắt đầu 10 => hết node
- Tiếp tục 11 => hết node
– Sử dụng cấu trúc dữ liệu hàng đợi để lưu trữ node.
– Là cấu trúc dữ liệu dạng đồ thị, hay dạng cây.
– Độ phức tạp thời gian là: O[|V| + |E|] V là số đỉnh duyệt qua và E là số cạnh duyệt qua
– Độ phức tạp không gian là O[|V|]. Số đỉnh là số phần tử cần lưu trữ vào bộ nhớ.
3. Thực hành Breath First Search.Thực hiện được hai bước cho bài toán thực hành thuật toán Breath First Search.
+ Xây dựng được cấu trúc dữ liệu dạng cây, với phần tử cha là phần tử đầu tiên của cây.
+ Viết hàm tìm kiếm, duyệt các phần tử bắt đầu từ phần tử cha ở trên.
a. Áp dụng với bài toán đơn giản cho hình minh họa ở trên.
KẾT QUẢ CHÚNG TA CẦN CÓ ĐƯỢC ĐÓ LÀ HIỆN THỊ: 1 – 2 7 8 – 3 6 9 12 – 4 5 10 11.
+ Node là một đối tượng chung, và mỗi node có thể trỏ đến nhiều node khác là kiểu dữ liệu như nó.
=> xây dựng node là một class, và trong nó lại lưu trữ một list các đối tượng chính nó.
list lưu trữ các node chính là một cấu trúc dữ liệu kiểu Hàng Đợi.
xây dựng một class như sau:
Định nghĩa hàm AddChild để thêm node và hàm tìm kiếm duyệt node, hàm in dữ liệu
Xây dựng hàm tạo cây nhị phân lưu trữ dữ liệu.
Ok. Như vậy là chúng ta đã có thể demo được thuật toán DFS bằng code c++ với bài toán cơ bản nhất.
b. Áp dụng vào bài toán hướng đối tượng. Giống như DFS.
Vẫn là hình minh họa như DFS, nhưng các bạn sẽ thấy,
cách duyệt của BFS sẽ là duyệt tất cả các phòng ban, sau đó mới duyệt các bộ phận của từng phòng ban.
Khác với DFS là duyệt từng phòng ban và duyệt hết các bộ phận phòng ban rồi mới sang phòng ban kết tiếp.
Từ video thực hành bài toán nâng cao của DFS mà tôi đã thực hành trên video, các bạn thử áp dụng với BFS.