Przeszukiwanie wszerz (ang. breadth-first search, w skrócie BFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przeglądaniu wierzchołków grafu według ich odległości od wierzchołka źródłowego (wyrażanej w liczbie krawędzi).
Zwyczajowo przyjmuje się, że:
Oznaczmy przez v liczbę wierzchołków grafu i przez e liczbę jego krawędzi. Początkowa część algorytmu ma złożoność O(v) – oznaczamy każdy wierzchołek. Liczba relacji sąsiedztwa jest równa liczbie krawędzi (lub jej dwukrotności, jeśli graf jest nieskierowany), więc złożoność czasowa głównej pętli algorytmu to O(e). Łącznie złożoność algorytmu jest więc rzędu O(v+e).
Jeśli każdy wierzchołek jest osiągalny ze źródła (po zakończeniu działania algorytmu nie będzie nieodwiedzonych wierzchołków), to e ≥ (v−1). Przy takim założeniu złożoność czasowa algorytmu wynosi O(e).
Za pomocą przeszukiwania grafu wszerz można wyznaczyć najkrótsze pod względem liczby krawędzi (ale nie wag!) ścieżki między wierzchołkiem źródłowym a pozostałymi wierzchołkami. Algorytm ten może być więc wykorzystany do rozwiązania szczególnego przypadku problemu najkrótszej ścieżki, gdy wszystkie krawędzie mają taką samą dodatnią wagę. Przeszukiwanie wszerz jest częścią składową niektórych bardziej zaawansowanych algorytmów grafowych, np. algorytmu Edmondsa-Karpa.
Dodano: 21 listopada 2017 17:35, ostatnia edycja: 30 stycznia 2019 15:55.
Drzewo decyzyjne – metoda graficzna wspierająca podejmowanie decyzji, jak również model stosowany w uczeniu maszynowym do klasyfikacji lub regresji.
Podejmowanie decyzji z wykorzystaniem drzewa decyzyjnego odbywa się poprzez odpowiadanie na kolejne pytania. Pojedyncze pytanie musi być proste i dotyczyć jednego konkretnego atrybutu. Pytania ułożone są w strukturę hierarchiczną – wybór następnego pytania (lub końcowej decyzji) zależy od odpowiedzi udzielonej na poprzednie.
Proste drzewo decyzyjne może być w pełni zaprojektowane już przy tworzeniu programu i zaimplementowane w kodzie np. za pomocą instrukcji warunkowych. W uczeniu maszynowym drzewo jest generowane automatycznie na podstawie próbek ze zbioru uczącego.
Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.
Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.
Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.