Metody Graph Traversal zawsze mnie fascynowały. Od wykonywania skutecznej komunikacji peer-to-peer po znajdowanie najbliższych restauracji i kawiarni za pomocą GPS, metody przechodzenia mają zróżnicowany zestaw zastosowań w rzeczywistych scenariuszach. W tym blogu o algorytmie przeszukiwania wszerz, omówimy logikę metod przechodzenia przez wykres i użyjemy przykładów, aby zrozumieć działanie algorytmu przeszukiwania wszerz.
Aby uzyskać dogłębną wiedzę na temat sztucznej inteligencji i uczenia maszynowego, możesz zarejestrować się na żywo by Edureka ze wsparciem 24/7 i dożywotnim dostępem.
Oto lista tematów, które będą omówione na tym blogu:
- Wprowadzenie do przemierzania wykresów
- Co to jest przeszukiwanie wszerz?
- Zrozumienie algorytmu Breadth-First Search na przykładzie
- Algorytm przeszukiwania wszerz. Pseudokod
- Zastosowania wyszukiwania wszerz
Wprowadzenie do przemierzania wykresów
Proces odwiedzania i eksplorowania wykresu w celu przetworzenia nazywa się przechodzeniem wykresu. Mówiąc dokładniej, chodzi o odwiedzanie i badanie każdego wierzchołka i krawędzi na wykresie, tak aby wszystkie wierzchołki były badane dokładnie raz.
Brzmi prosto! Ale jest haczyk.
Istnieje kilka technik przemierzania wykresów, takich jak przeszukiwanie wszerz, przeszukiwanie w głąb i tak dalej. Wyzwaniem jest użycie wykresu technika przechodzenia, która jest najbardziej odpowiednia do rozwiązania konkretnego problemu. To prowadzi nas do techniki przeszukiwania wszerz.
Co to jest algorytm wyszukiwania wszerz?
Algorytm przeszukiwania wszerz jest techniką przechodzenia przez graf, w której wybiera się losowy węzeł początkowy (węzeł źródłowy lub główny) i rozpoczyna przeglądanie warstwy grafu w taki sposób, że wszystkie węzły i ich odpowiednie węzły potomne są odwiedzane i badane.
Zanim przejdziemy dalej i zrozumiemy wyszukiwanie wszerz na przykładzie, zapoznajmy się z dwoma ważnymi terminami związanymi z przemierzaniem wykresu:
- Odwiedzanie węzła: Tak jak sugeruje nazwa, odwiedzanie węzła oznacza odwiedzanie lub wybieranie węzła.
- Badanie węzła: Odkrywanie sąsiednie węzły (węzły potomne) wybranego węzła.
Zobacz powyższy rysunek, aby lepiej to zrozumieć.
Zrozumienie algorytmu wyszukiwania wszerz na przykładzie
Algorytm Breadth-First Search stosuje proste, oparte na poziomie podejście do rozwiązania problemu. Rozważ poniższe drzewo binarne (które jest wykresem). Naszym celem jest przejście przez wykres przy użyciu algorytmu przeszukiwania wszerz.
Zanim zaczniemy, musisz zapoznać się z główną strukturą danych zaangażowaną w algorytm przeszukiwania wszerz.
Kolejka to abstrakcyjna struktura danych zgodna z metodologią First-In-First-Out (dane wstawione jako pierwsze będą dostępne jako pierwsze). Jest otwarty na obu końcach, gdzie jeden koniec jest zawsze używany do wstawiania danych (umieszczania w kolejce), a drugi służy do usuwania danych (usuwania z kolejki).
Przyjrzyjmy się teraz etapom przechodzenia przez wykres przy użyciu wyszukiwania wszerz:
Krok 1: Wybierz pustą kolejkę.
Krok 2: Wybierz węzeł początkowy (odwiedzając węzeł) i wstaw go do kolejki.
Krok 3: Pod warunkiem, że kolejka nie jest pusta, wyodrębnij węzeł z kolejki i wstaw jego węzły podrzędne (eksplorując węzeł) do kolejki.
Krok 4: Wydrukuj wyodrębniony węzeł.
Nie martw się, jeśli jesteś zdezorientowany, zrozumiemy to na przykładzie.
Spójrz na poniższy wykres, użyjemy algorytmu Breadth-First Search do przechodzenia przez wykres.
W naszym przypadku przypiszemy węzeł „a” jako węzeł główny, zaczniemy wędrować w dół i wykonamy kroki wymienione powyżej.
Powyższy obraz przedstawia kompleksowy proces algorytmu przeszukiwania wszerz. Pozwólcie, że wyjaśnię to bardziej szczegółowo.
- Przypisz „a” jako węzeł główny i wstaw go do kolejki.
- Wyodrębnij węzeł „a” z kolejki i wstaw węzły potomne „a”, tj. „B” i „c”.
- Wydrukuj węzeł „a”.
- Kolejka nie jest pusta i ma węzły „b” i „c”. Ponieważ „b” jest pierwszym węzłem w kolejce, wyodrębnijmy go i wstawmy węzły potomne „b”, tj. Węzeł „d” i „e”.
- Powtarzaj te kroki, aż kolejka się opróżni. Zwróć uwagę, że węzły, które są już odwiedzone, nie powinny być dodawane do kolejki jeszcze raz.
Spójrzmy teraz na pseudokod algorytmu Breadth-First Search.
Algorytm przeszukiwania wszerz. Pseudokod
Oto pseudokod implementujący algorytm wyszukiwania wszerz:
Dane wejściowe: s jako węzeł źródłowy BFS (G, s) niech Q będzie w kolejce. Q.enqueue (s) oznacza s jako odwiedzone, podczas gdy (Q nie jest puste) v = Q.dequeue () dla wszystkich sąsiadów w z v na wykresie G, jeśli w nie jest odwiedzane Q.enqueue (w) mark w as odwiedzone
W powyższym kodzie wykonywane są następujące kroki:
- (G, s) to wejście, tutaj G to wykres, a s to węzeł główny
- Utworzono kolejkę „Q” i zainicjowano ją za pomocą węzła źródłowego „s”
- Zaznaczone są wszystkie węzły potomne „s”
- Wyodrębnij „s” z kolejki i odwiedź węzły podrzędne
- Przetwórz wszystkie węzły potomne v
- Przechowuje w (węzły podrzędne) w Q, aby dalej odwiedzać jego węzły podrzędne
- Kontynuuj, aż „Q” będzie pusty
Zanim zakończymy blog, przyjrzyjmy się niektórym zastosowaniom algorytmu Breadth-First Search.
Zastosowania algorytmu przeszukiwania wszerz
Przeszukiwanie wszerz to prosta metoda przeszukiwania wykresów, która ma zaskakujący zakres zastosowań. Oto kilka interesujących sposobów wykorzystania funkcji Bread-First Search:
Crawlery w wyszukiwarkach: Wyszukiwanie wszerz jest jednym z głównych algorytmów używanych do indeksowania stron internetowych. Algorytm rozpoczyna przechodzenie ze strony źródłowej i podąża za wszystkimi linkami powiązanymi ze stroną. Tutaj każda strona internetowa będzie traktowana jako węzeł na wykresie.
Systemy nawigacji GPS: Wyszukiwanie wszerz jest jednym z najlepszych algorytmów używanych do znajdowania sąsiednich lokalizacji za pomocą systemu GPS.
Znajdź najkrótszą ścieżkę i minimalne drzewo rozpinające dla nieważonego wykresu: Jeśli chodzi o wykres nieważony, obliczenie najkrótszej ścieżki jest dość proste, ponieważ ideą najkrótszej ścieżki jest wybranie ścieżki z najmniejszą liczbą krawędzi. Przeszukiwanie wszerz może to umożliwić, przechodząc przez minimalną liczbę węzłów, zaczynając od węzła źródłowego. Podobnie w przypadku drzewa opinającego możemy użyć jednej z dwóch metod przeszukiwania wszerz wszerz lub w pierwszej kolejności w głąb, aby znaleźć drzewo opinające.
Talend open studio do samouczka integracji danych
Nadawanie: Sieć wykorzystuje do komunikacji to, co nazywamy pakietami. Pakiety te są przesyłane metodą traversal, aby dotrzeć do różnych węzłów sieciowych. Jedną z najczęściej używanych metod przemierzania jest przeszukiwanie wszerz. Jest używany jako algorytm służący do przesyłania pakietów rozgłoszonych przez wszystkie węzły w sieci.
Sieć równorzędna: Wyszukiwanie wszerz może być używane jako metoda przechodzenia w celu znalezienia wszystkich sąsiednich węzłów w sieci równorzędnej. Na przykład BitTorrent wykorzystuje wyszukiwanie wszerz do komunikacji peer-to-peer.
Więc to wszystko dotyczyło działania algorytmu Breadth-First Search. Teraz, gdy wiesz, jak przechodzić przez wykresy, jestem pewien, że chcesz dowiedzieć się więcej. Oto kilka odpowiednich blogów, które mogą Cię zainteresować:
W ten sposób dochodzimy do końca tego bloga. Jeśli masz jakieś pytania dotyczące tego tematu, zostaw komentarz poniżej, a my skontaktujemy się z Tobą.
Jeśli chcesz zapisać się na pełny kurs sztucznej inteligencji i uczenia maszynowego, Edureka ma specjalnie wyselekcjonowany to sprawi, że będziesz biegły w technikach, takich jak uczenie się nadzorowane, uczenie się bez nadzoru i przetwarzanie języka naturalnego. Obejmuje szkolenia dotyczące najnowszych osiągnięć i podejść technicznych w dziedzinie sztucznej inteligencji i uczenia maszynowego, takich jak uczenie głębokie, modele graficzne i uczenie się ze wzmocnieniem.