Przynoszę Wam na tacy wytłumaczenie (plus kodzik) algorytmu jakim jest przeszukiwanie wszerz. Temat dotyczy problemu wyszukania najkrótszej drogi do celu, więc może wzbudzać ciekawość początkujących, jak i przyciągać już doświadczone "stare wygi" ;). Wszystko wytłumaczę punkt po punkcie jak należy się z tym obchodzić i jak rozumieć działanie.

PRZESZUKIWANIE WSZERZ OPERUJE NA GRAFIE!

Zanim przejdziemy do samego problemu algorytmicznego, muszę wprowadzić Was powierzchownie w temat grafów. Graf jest taką strukturą danych, która ukazuje powiązania (relacje) między różnymi obiektami. Można go pokrótce nazwać "modelem zbioru połączeń". Dwa terminy jakie trzeba zapamiętać i nie ma od nich ucieczki to węzły i krawędzie. Węzeł jest to obiekt, który należy rozumieć jako element lub przedmiot. O wiele ważniejszy jest fakt, iż może on wchodzić w relacje z innymi węzłami jakie określa się wtedy "sąsiadami", czyli są to węzły bezpośrednio połączone z innym węzłem. Krawędź jako drugie istotne pojęcie w teorii grafów jest właśnie tym połączeniem od jednego węzła do drugiego. Możecie natrafić na połączenia ze strzałką, a relacja "idzie" od węzła A do węzła B i nie da się w drugą stronę (i wtedy jest to graf skierowany) albo bez strzałki i wtedy relacja jest obustronna (wtedy to jest graf nieskierowany).

Na ten moment więcej wiedzieć o grafach nie musicie. O wszystkich detalach zostaniecie poinformowani w osobnym artykule o grafach jako o strukturze danych.

WRÓĆ DO TEMATU!

A teraz przechodzimy do sedna sprawy. "Breadth first search" czyli przeszukiwanie wszerz, rozwiązuje problem należący do kategorii wyszukiwania najkrótszej ścieżki (ang. "shortest path problem"). Oznacza to, że dzięki prawidłowemu opanowaniu materiału w tym artykule, będziecie w stanie nie tylko sami dodawać węzły i krawędzie do własnego grafu, ale także zaprogramować odnajdywanie poszukiwanego elementu na podstawie własnego kryterium! Także czytajcie uważnie, bo jest okazja do zrozumienia jednego z cenniejszych algorytmów!

Problem: odnalezienie odpowiedniego węzła w grafie na podstawie podanego kryterium

Przeszukiwanie wszerz pozwala uzyskać odpowiedź na dwa pytania:

1. czy istnieje droga z węzła startowego do węzła docelowego?
2. jaka jest droga z węzła startowego do węzła docelowego (jeśli punkt pierwszy jest spełniony)?

Może nas interesować sama odpowiedź decyzyjna (punkt 1), ale o wiele częściej wykorzystywane jest opracowanie całej drogi od punktu A do punktu B. Teraz tłumaczę algorytm krok po kroku.

JAK DZIAŁA ALGORYTM PRZESZUKIWANIA WSZERZ?

Mamy taki oto graf składający się z wielu węzłów:

Rysunek graficzny prezentujący graf nieskierowany na potrzeby eksperymentu.

i interesuje nas opracowanie drogi od punktu oznaczonego kolorem zielonym do punktu o kolorze czerwonym. Pierwszym zadaniem przeszukiwania wszerz jest pobranie oraz usunięcie ze zbioru węzła początkowego i sprawdzenie jego właściwości (np. długości nazwy) czy przypadkiem nie jest on przez nas poszukiwanym. Jeżeli to nie on, to dodaje do zbioru węzłów wszystkich jego sąsiadów, a sam węzeł oznacza jako "odwiedzony" lub "rozpatrzony" (to jest cholernie ważne i zapobiega zapętleniu programu!!!). Ten sam ciąg instrukcji powtarza się dopóty, dopóki nie opróżni się zbioru węzłów do sprawdzenia (albo nie odnajdzie się tego elementu, na jakim nam zależy).

Musicie też mieć na względzie tę rzecz, że kolejność dodawanych nowych węzłów do rozpatrzenia odgrywa kolosalną rolę! Nowe elementy mają być dodawane na sam KONIEC listy, za każdym razem kiedy algorytm wywnioskuje, że to nie ten którego szukamy. To działa tak, jakbyśmy szukali pracy dla przykładu. Najpierw staramy się samodzielnie. Kiedy nie idzie ten wariant, prosimy o pomoc najbliższych znajomych. Jeżeli to nie przynosi rezultatu, sięgamy do znajomych znajomych i tak dalej. W takiej kolejności ma się to odbywać i wtedy jest zapewnienie, że program będzie działał zgodnie z teorią.

Wniosek jest prosty: żeby algorytm działał prawidłowo, musi zachowywać odpowiednią kolejność "przepytywania" poszczególnych węzłów. Pisząc krótko, "wchodzi" zawsze pierwszy, a na końcu dodawani są sąsiedzi i ZAWSZE mają być umieszczeni na samym końcu!!! Sposób przeprowadzania operacji w podanej kolejności doczekało się słynnego terminu "Last In, First Out" w skrócie "LIFO", a strukturą danych w takim przypadku jest kolejka. Kolejkę wyróżnia możliwość "wyciągania" elementów tylko z jej początku, a nowe elementy pojawiają się zawsze na końcu (jak w prawdziwej kolejce po mięso za komuny).

Przeszukiwanie wszerz ma oczywiście swoje wady, jak wszystko inne w dziedzinie informatycznej. Najważniejsze rzecz jaka rzuca się w oczy to brak rozróżniania "wagi" dostępnych ścieżek. Algorytm nie weźmie pod uwagę, że mogą istnieć inne przebiegi dróg od punktu A do B i wszystkie węzły traktuje jednolicie (po prostu weźmie pierwszą dostępną ścieżkę i taką zwróci). Jeśli pragniecie opracowania drogi w wyznaczonym grafie biorąc pod uwagę jakieś przeszkody symulujące "trudny teren" (węzły przez które można przejść, ale będą bardziej kosztowne), to tu przeszukiwanie wszerz odpada i musicie sięgnąć choćby po bardzo popularny algorytm Dijkstry, który będzie pasować świetnie dla tego typu przypadków.

SPYTAJ O TO SAMO!

Nim zaczniecie kopiować kod, zapytajcie o złożoność obliczeniową! Dla najgorszego przypadku, będzie równa sumie wierzchołków (węzłów) i krawędzi:

O(|V| + |E|), gdzie V = zbiór wierzchołków, E = zbiór krawędzi

Przeszukiwanie wszerz w najgorszym przypadku musi przeczesać wszystkie węzły w podanym grafie celem wykonania posłusznie swojego zadania. Mamy sumę, ponieważ za każdym razem dodajemy do zbioru wszystkie pozostałe węzły będące w bezpośrednim sąsiedztwie z już zweryfikowanym wierzchołkiem, jeżeli okaże się że to nie ten, który nas interesuje.

KOD ŹRÓDŁOWY

Raz kolejny częstuję Was kodem źródłowym w języku Java, aby atrakcyjność tego materiału weszła na wyższy poziom!

KLASA "MAIN"

public class Main {
	public static void main(String[] args) {
		new BFS();
	}
}

KLASA "NODE"

import java. util.LinkedHashSet;

public class Node {
	private final String name;
	private final LinkedHashSet<Node> neighbours = new LinkedHashSet<>();
	
	private boolean visited = false;
	
	@Override
	public int hashCode() {
		return name.hashCode();
	}
	
	@Override
	public boolean equals(Object o) {
		if(getClass() != o.getClass()) {
			return false;
		}
		
		Node node = (Node)o;
		
		return getName().equals(node.getName());
	}
	
	public Node(String name) {
		this.name = name;
	}
	
	public void addNeighbour(Node node) {
		neighbours.add(node);
	}
	
	public void setAsVisited() {
		visited = true;
	}
	
	public String getName() {
		return name;
	}
	
	public LinkedHashSet<Node> getNeighbours() {
		return neighbours;
	}
	
	public boolean isVisited() {
		return visited;
	}
}

KLASA "GRAPH"

import java. util.LinkedHashSet;

public class Graph {
	private final LinkedHashSet<Node> nodes = new LinkedHashSet<>();
	
	public Graph() {
		configureNodes();
	}
	
	public boolean isEmpty() {
		return nodes.isEmpty();
	}
	
	public Node popFirst() {
		Node node = nodes.iterator().next();
		
		nodes.remove(node);
		
		return node;
	}
	
	public void addNeighbours(Node node) {
		nodes.addAll(node.getNeighbours());
	}
	
	private void configureNodes() {
		Node nodeA = new Node("Magnes");
		Node nodeB = new Node("Foremka");
		Node nodeC = new Node("Bibuła");
		
		nodes.add(nodeA);
		nodes.add(nodeB);
		nodes.add(nodeC);
		
		nodeB.addNeighbour(nodeA);
		nodeC.addNeighbour(nodeA);
	}
}

KLASA "BFS"

public class BFS {
	private final Graph graph = new Graph();
	
	private Node foundNode = null;
	
	public BFS() {
		searchNodes();
		writeResult();
	}
	
	private void searchNodes() {
		while (!graph.isEmpty() && foundNode == null) {
			Node currentNode = graph.popFirst();
			
			if(!currentNode.isVisited()) {
				if(isSearchedNode(currentNode)) {
					foundNode = currentNode;
				} else {
					graph.addNeighbours(currentNode);
					currentNode.setAsVisited();
				}
			}
		}
	}
	
	private void writeResult() {
		String text = (foundNode == null) ? "Nie znaleziono szukanego węzła." : "Znaleziono szukany węzeł o nazwie: " + foundNode.getName();
		
		System.out.println(text);
	}
	
	private boolean isSearchedNode(Node node) {
		return node.getName().length() == 7;
	}
}

Wyjaśniamy "as always" po kolei. Klasa przeznaczona dla węzła (klasa "Node") posiada nazwę, zmienną boolowską czy węzeł został już zbadany oraz zbiór węzłów sąsiednich (węzły, których łączy relacja z tym węzłem). Korzystamy z odmiany "LinkedHashSet", ażeby zapamiętywać kolejność dodawanych węzłów w charakterze sąsiadów. Zadbałem też o identyfikację unikatowości tychże węzłów z powodu korzystania ze zbioru, przesłaniając metody "hashCode" oraz "equals" (zapraszam do artykułu o Javie, jeśli wyjaśnienia są alarmująco potrzebne). Reszta to już gettery i settery.

Dalej mamy klasę dla konstrukcji grafu. W niej także umieściłem "LinkedHashSet", ale już dla samych węzłów czy też wierzchołków. W metodzie jako jedynej o prywatnym modyfikatorze dostępu, znajdziecie instrukcje dodające poszczególne węzły do samego grafu, jak również do zbioru sąsiadów danych węzłów. Metoda "isEmpty" ma za zadanie zwrócić stan rozmiaru zbioru czy znajdują się jeszcze jakiekolwiek węzły do analizy (tak naprawdę powinno się operować na kopii tego zbioru, gdyż to de facto "kurczy" sam graf "pożerając" jeden węzeł po drugim na potrzeby pętli "while", ale nie chciałem już bardziej poszerzać przykładu). "popFirst" symuluje to, co znajdziecie w wielu językach programowania w strukturach danych typu "lista" (tablica również w niektórych językach, choć to nie leży w naturze tej struktury danych). Mianowicie, zwraca pierwszy w kolejności element (korzystam tu z tzw. "iteratora" i metody "next"), przypisuje referencję do zmiennej lokalnej, a zaraz potem go usuwa ze zbioru i jednocześnie zwraca na wyjściu. Zbiór nie posiada takiej funkcjonalności bo to nie jest jego działka, więc trzeba było taką metodę zbudować ręcznie. A metoda "addNeighbours" dodaje do grafu sąsiadów wskazanego w parametrze formalnym węzła.

Całe przeszukiwanie wszerz jako algorytm funkcjonuje w klasie "BFS". W środku niej znajdziecie dwie dane składowe, pierwsza definiuje instancję naszego grafu, a druga określa referencję znalezionego węzła, aby go później wypisać na ekranie terminala celem udowodnienia jego skuteczności. Interesuje nas metoda "searchNodes", w której to ponownie widzimy starą dobrą pętlę "while", która to pilnuje aby doprowadzić do wyczerpania elementów w zbiorze, choć może też przerwać wykonywanie wcześniej poprzez znalezienie poszukiwanego węzła.

W środku pętli pobieramy ORAZ usuwamy pierwszy element ze zbioru. Następnie instrukcja warunkowa weryfikuje jego stan czy przypadkiem nie został sprawdzony wcześniej (ponieważ usuwamy te elementy ze zbioru, to tak naprawdę nie jest to konieczne, ale staje się to potrzebne kiedy graf pozostaje nietknięty). Jeżeli nie został wcześniej "odwiedzony", to badamy czy jest to ten, którego szukamy. Za to odpowiada metoda zwracająca boolean'a i tam dorzucacie sobie takie kryterium, jakie chcecie. Ja dałem bardzo trywialne, żeby nie rzec śmieszne, kryterium (długość łańcucha znaków nazwy), a Wy możecie zaimplementować jakieś nowe dane składowe do obiektów węzłów i uzależniać poszukiwania od wskazanej wartości. W każdym razie, jeżeli to ten węzeł spełnia nasze wymagania, to program przypisuje jego referencję do instancji węzła określanego dalej jako "znaleziony poszukiwany" i przerywa dalsze działanie pętli. Kiedy tak się nie dzieje, to wywołuje metodę dodającą do grafu wszystkich sąsiadów zbadanego węzła i zmienia jego stan na "odwiedzony". I to wszystko! Na samym końcu jest wypis rezultatów, ale o tym już nie trzeba pisać.

Mamy następny algorytm za sobą! Przeszukiwanie wszerz to jedna z metod do wykorzystania problemów "pathfindingu" (wyszukiwanie najkrótszej ścieżki), choć do tych celów częściej używa się bardziej złożonych algorytmów (to sprawdza węzły trochę "brute-force'owo")...

PODOBNE ARTYKUŁY

• Przypadek optymistyczny, średni i najgorszy w algorytmice
• Sortowanie szybkie. Teoria i kod źródłowy
• Dziel i rządź. Metodyka rozwiązywania problemu