Rozdział 5: Grafy w Algorytmach

Grafy są fundamentalną strukturą danych, która modeluje połączenia i relacje między obiektami. Mają one szerokie zastosowanie w informatyce i nie tylko, od modelowania sieci społecznych i linków stron internetowych, po rozwiązywanie problemów w transporcie, harmonogramowaniu i alokacji zasobów. W tym rozdziale zbadamy podstawowe właściwości i algorytmy do pracy z grafami, koncentrując się na grafach nieskierowanych, przeszukiwaniu w głąb i wszerz, minimalnych drzewach rozpinających oraz najkrótszych ścieżkach.

Grafy Nieskierowane

Graf nieskierowany to zbiór wierzchołków (lub węzłów) połączonych krawędziami. Formalnie definiujemy graf nieskierowany G jako parę (V, E), gdzie V jest zbiorem wierzchołków, a E jest zbiorem niuporządkowanych par wierzchołków, zwanych krawędziami. Krawędź (v, w) łączy wierzchołki v i w. Mówimy, że v i w są sąsiednimi lub sąsiadami. Stopień wierzchołka to liczba krawędzi do niego przylegających.

Oto prosty przykład grafu nieskierowanego:

   A --- B
  /     / \
 /     /   \
C --- D --- E

W tym grafie, zbiór wierzchołków V = {A, B, C, D, E} i zbiór krawędzi E = {(A, B), (A, C), (B, D), (B, E), (C, D), (D, E)}.

Istnieje kilka sposobów reprezentacji grafu w programie. Dwie powszechne reprezentacje to:

1. Macierz Sąsiedztwa: Binarna macierz n x n A, gdzie n to liczba wierzchołków. Element A[i][j] jest prawdziwy, jeśli istnieje krawędź z wierzchołka i do wierzchołka j, w przeciwnym razie fałszywy.

2. Listy Sąsiedztwa: Tablica Adj o rozmiarze n, gdzie n to liczba wierzchołków. Element Adj[v] to lista zawierająca sąsiadów wierzchołka v.

Wybór reprezentacji zależy od gęstości grafu (stosunku krawędzi do wierzchołków) i operacji, które chcemy wykonywać. Macierze sąsiedztwa są proste, ale mogą być nieefektywne dla rzadkich grafów. Listy sąsiedztwa są bardziej oszczędne w pamięci dla rzadkich grafów i zapewniają szybszy dostęp do sąsiadów wierzchołka.

Oto przykład, jak moglibyśmy reprezentować powyższy graf przy użyciu list sąsiedztwa w Javie:

List<Integer>[] graph = (List<Integer>[]) new List[5];
graph[0] = Arrays.asList(1, 2);        // A -> B, C
graph[1] = Arrays.asList(0, 3, 4);     // B -> A, D, E
graph[2] = Arrays.asList(0, 3);        // C -> A, D
graph[3] = Arrays.asList(1, 2, 4);     // D -> B, C, E
graph[4] = Arrays.asList(1, 3);        // E -> B, D

Przeszukiwanie w głąb (DFS)

Przeszukiwanie w głąb (DFS) to podstawowy algorytm przeszukiwania grafu, który eksploruje jak najdalej wzdłuż każdej gałęzi przed cofnięciem się. Może być używany do rozwiązywania wielu problemów związanych z grafami, takich jak znajdowanie składowych spójnych, sortowanie topologiczne i wykrywanie cykli.

Algorytm DFS działa w następujący sposób:

1. Rozpocznij od wierzchołka źródłowego s.
2. Oznacz bieżący wierzchołek jako odwiedzony.
3. Rekurencyjnie odwiedź wszystkie nieodwiedzone wierzchołki w sąsiedztwie bieżącego wierzchołka.
4. Jeśli wszystkie wierzchołki sąsiednie bieżącego wierzchołka zostały odwiedzone, cofnij się do wierzchołka, z którego bieżący wierzchołek został zbadany.
5. Jeśli pozostały jeszcze nieodwiedzone wierzchołki, wybierz jeden z nich i powtórz od kroku 1.

Oto prosta implementacja DFS w Javie, wykorzystująca listy sąsiedztwa:

boolean[] visited;
 
void dfs(List<Integer>[] graph, int v) {
    visited[v] = true;
    for (int w : graph[v]) {
        if (!visited[w]) {
            dfs(graph, w);
        }
    }
}

Aby przeprowadzić pełne przeszukiwanie DFS, należy wywołać dfs(graph, s) dla każdego wierzchołka s w grafie, gdzie visited jest zainicjalizowane na false dla wszystkich wierzchołków.

DFS ma wiele zastosowań. Na przykład, możemy go użyć do znalezienia składowych spójnych w nieskierowanym grafie, uruchamiając DFS z każdego nieodwiedzonego wierzchołka i przypisując każdy wierzchołek do składowej na podstawie drzewa DFS.

Przeszukiwanie wszerz (BFS)

Przeszukiwanie wszerz (BFS) to kolejny podstawowy algorytm przeszukiwania grafu, który eksploruje wierzchołki warstwami. Odwiedza wszystkie wierzchołki na bieżącym poziomie głębokości, zanim przejdzie do wierzchołków na następnym poziomie.

Algorytm BFS działa w następujący sposób:

1. Rozpocznij od wierzchołka źródłowego s i oznacz go jako odwiedzony.
2. Umieść s w kolejce FIFO.
3. Dopóki kolejka nie jest pusta: a. Pobierz wierzchołek z początku kolejki. b. Dla każdego nieodwiedzonego sąsiada w tego wierzchołka: i. Oznacz go jako odwiedzony. ii. Umieść go na końcu kolejki.Oto tłumaczenie pliku Markdown na język polski, z zachowaniem oryginalnego kodu:

Dopóki kolejka nie jest pusta:

• Odejmij wierzchołek v z kolejki.
• Dla każdego nieznanego wierzchołka w sąsiadującego z v:
  • Oznacz w jako odwiedzony.
  • Dodaj w do kolejki.

Oto implementacja BFS w Javie przy użyciu list sąsiedztwa:

boolean[] visited;
 
void bfs(List<Integer>[] graph, int s) {
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    queue.offer(s);
 
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph[v]) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

BFS jest szczególnie przydatny do znajdowania najkrótszych ścieżek w grafach nieważonych. Odległość od wierzchołka źródłowego do dowolnego innego wierzchołka to minimalna liczba krawędzi na ścieżce między nimi. BFS gwarantuje znalezienie najkrótszej ścieżki.

Drzewa Rozpinające o Minimalnym Koszcie

Drzewo rozpinające o minimalnym koszcie (MST) to podzbiór krawędzi połączonego, ważonego nieskierowanego grafu, który łączy wszystkie wierzchołki, bez cykli i o minimalnym możliwym całkowitym ciężarze krawędzi.

Dwa klasyczne algorytmy znajdujące MST to algorytm Kruskala i algorytm Prima.

Algorytm Kruskala działa następująco:

1. Utwórz las F, w którym każdy wierzchołek jest osobnym drzewem.
2. Utwórz zbiór S zawierający wszystkie krawędzie w grafie.
3. Dopóki S nie jest pusty, a F nie jest jeszcze drzewem rozpinającym:
   • Usuń krawędź o minimalnym ciężarze z S.
   • Jeśli usunięta krawędź łączy dwa różne drzewa, dodaj ją do F, łącząc dwa drzewa w jedno.

Algorytm Prima działa następująco:

1. Zainicjuj drzewo jednym wierzchołkiem, wybranym dowolnie z grafu.
2. Rozwijaj drzewo o jedną krawędź: spośród wszystkich krawędzi łączących drzewo z wierzchołkami, które nie są jeszcze w drzewie, znajdź krawędź o minimalnym ciężarze i przenieś ją do drzewa.
3. Powtarzaj krok 2, aż wszystkie wierzchołki znajdą się w drzewie.

Oto implementacja algorytmu Prima w Javie:

int minKey(int[] key, boolean[] mstSet, int V) {
    int min = Integer.MAX_VALUE, min_index = -1;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}
 
void primMST(int[][] graph, int V) {
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        key[i] = Integer.MAX_VALUE;
        mstSet[i] = false;
    }
 
    key[0] = 0;
    parent[0] = -1;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }
 
    printMST(parent, graph, V);
}

Drzewa rozpinające o minimalnej sumie wag (MST) mają wiele zastosowań, takich jak projektowanie sieci (komunikacyjnych, elektrycznych, hydraulicznych, komputerowych) oraz przybliżanie problemów komiwojażera.

Najkrótsze ścieżki

Problem najkrótszej ścieżki polega na znalezieniu ścieżki między dwoma wierzchołkami w grafie, tak aby suma wag jej krawędzi była minimalna. Problem ten ma wiele odmian, takich jak najkrótsze ścieżki z jednego źródła, wszystkie najkrótsze ścieżki oraz najkrótsze ścieżki do jednego celu.

Algorytm Dijkstry jest zachłannym algorytmem, który rozwiązuje problem najkrótszych ścieżek z jednego źródła dla grafu z nieujemnymi wagami krawędzi. Działa on w następujący sposób:

1. Utwórz zbiór sptSet (zbiór drzewa najkrótszych ścieżek), który śledzi wierzchołki uwzględnione w drzewie najkrótszych ścieżek.
2. Przypisz wartość odległości do wszystkich wierzchołków w grafie. Zainicjuj wszystkie wartości odległości jako NIESKOŃCZONOŚĆ. Przypisz wartość odległości jako 0 dla wierzchołka źródłowego.
3. Dopóki sptSet nie obejmuje wszystkich wierzchołków, wybierz wierzchołek v, który nie znajduje się w sptSet i ma minimalną wartość odległości. Dodaj v do sptSet.

Zaktualizuj wartości odległości wszystkich sąsiednich wierzchołków v. Aby zaktualizować wartości odległości, iteruj przez wszystkie sąsiednie wierzchołki. Dla każdego sąsiedniego wierzchołka w, jeśli suma odległości v.Oto tłumaczenie na język polski:

Wartość v (z źródła) i waga krawędzi v-w jest mniejsza niż wartość odległości w, następnie zaktualizuj wartość odległości w.

Oto implementacja algorytmu Dijkstry w Javie:

public void dijkstra(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
    boolean[] sptSet = new boolean[V];
 
    for (int i = 0; i < V; i++) {
        dist[i] = Integer.MAX_VALUE;
        sptSet[i] = false;
    }
 
    dist[src] = 0;
 
    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
 
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
 
    printSolution(dist);
}

Algorytm Bellmana-Forda to inny algorytm służący do znajdowania najkrótszych ścieżek z pojedynczego źródła do wszystkich innych wierzchołków w ważonym grafie skierowanym. W przeciwieństwie do algorytmu Dijkstry, algorytm Bellmana-Forda może obsługiwać grafy z ujemnymi wagami krawędzi, o ile nie ma w nich ujemnych cykli.

Algorytm działa w następujący sposób:

1. Zainicjuj odległości od źródła do wszystkich wierzchołków jako nieskończoność, a odległość do samego źródła jako 0.
2. Zrelaksuj wszystkie krawędzie |V| - 1 razy. Dla każdej krawędzi u-v, jeśli odległość do v może być skrócona przez wzięcie krawędzi u-v, zaktualizuj odległość do v.
3. Sprawdź, czy nie ma cykli o ujemnej wadze. Wykonaj krok relaksacji dla wszystkich krawędzi. Jeśli jakakolwiek odległość się zmieni, to znaczy, że istnieje cykl o ujemnej wadze.

Oto implementacja algorytmu Bellmana-Forda w Javie:

public void bellmanFord(int[][] graph, int src) {
    int V = graph.length;
    int[] dist = new int[V];
 
    for (int i = 0; i < V; i++)
        dist[i] = Integer.MAX_VALUE;
    dist[src] = 0;
 
    for (int i = 1; i < V; i++) {
        for (int u = 0; u < V; u++) {
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                        && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }
 
    for (int u = 0; u < V; u++) {
        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE
                    && dist[u] + graph[u][v] < dist[v]) {
                System.out.println("Graf zawiera cykl o ujemnej wadze");
                return;
            }
        }
    }
 
    printSolution(dist);
}

Algorytmy najkrótszych ścieżek mają liczne zastosowania, takie jak w systemach nawigacyjnych, protokołach routingu sieciowego i planowaniu transportu. Są to podstawowe narzędzia w teorii grafów i są niezbędne w wielu zadaniach przetwarzania grafów.

Wniosek

Grafy są wszechstronnymi i potężnymi strukturami danych, które mogą modelować szeroki zakres problemów. W tym rozdziale zbadaliśmy podstawowe właściwości i typy grafów oraz studiowaliśmy podstawowe algorytmy grafowe, w tym przeszukiwanie w głąb, przeszukiwanie wszerz, drzewa rozpinające o minimalnym koszcie oraz najkrótsze ścieżki.

Przeszukiwanie w głąb i przeszukiwanie wszerz zapewniają systematyczne sposoby eksploracji grafu i stanowią podstawę wielu zaawansowanych algorytmów grafowych. Algorytmy drzew rozpinających o minimalnym koszcie, takie jak Kruskala i Prima, znajdują drzewo łączące wszystkie wierzchołki z minimalnym całkowitym ciężarem krawędzi. Algorytmy najkrótszych ścieżek, takie jak Dijkstry i Bellmana-Forda, znajdują ścieżki o minimalnym ciężarze między wierzchołkami.

Zrozumienie tych podstawowych koncepcji i algorytmów jest kluczowe dla skutecznej pracy z grafami i rozwiązywania złożonych problemów w różnych dziedzinach. Wraz z dalszym postępem w nauce algorytmów, będziesz spotykać się z bardziej zaawansowanymi algorytmami grafowymi, które opierają się na tych podstawowych technikach.

Grafy dostarczają potężnego języka do opisywania i rozwiązywania problemów w informatyce i nie tylko. Opanowanie algorytmów grafowych wyposażi Cię w wszechstronny zestaw narzędzi do modelowania i rozwiązywania szerokiego zakresu problemów obliczeniowych.# Wyzwania NLP

Wyzwanie 1: Klasyfikacja sentymentu

Celem tego wyzwania jest zbudowanie modelu, który będzie w stanie klasyfikować tekst jako pozytywny lub negatywny.

# Importuj niezbędne biblioteki
import pandas as pd
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import train_test_split
 
# Wczytaj dane
data = pd.read_csv('reviews.csv')
 
# Podziel dane na zbiór treningowy i testowy
X_train, X_test, y_train, y_test = train_test_split(data['text'], data['sentiment'], test_size=0.2, random_state=42)
 
# Utwórz obiekt CountVectorizer i przekształć dane
vectorizer = CountVectorizer()
X_train_vectorized = vectorizer.fit_transform(X_train)
X_test_vectorized = vectorizer.transform(X_test)
 
# Utwórz model logistycznej regresji i naucz go
model = LogisticRegression()
model.fit(X_train_vectorized, y_train)
 
# Oceń model na zbiorze testowym
accuracy = model.score(X_test_vectorized, y_test)
print(f'Accuracy: {accuracy:.2f}')

Wyzwanie 2: Rozpoznawanie nazw encji

Celem tego wyzwania jest zbudowanie modelu, który będzie w stanie rozpoznawać nazwy encji w tekście.

# Importuj niezbędne biblioteki
import spacy
 
# Załaduj model języka
nlp = spacy.load('en_core_web_sm')
 
# Przykładowy tekst
text = "My name is John and I live in New York City."
 
# Przetwórz tekst za pomocą modelu
doc = nlp(text)
 
# Wyświetl rozpoznane nazwy encji
for entity in doc.ents:
    print(f'{entity.text} ({entity.label_})')

Wyzwanie 3: Tłumaczenie maszynowe

Celem tego wyzwania jest zbudowanie modelu, który będzie w stanie tłumaczyć tekst z jednego języka na inny.

# Importuj niezbędne biblioteki
from transformers import MarianMTModel, MarianTokenizer
 
# Załaduj model i tokenizer
model = MarianMTModel.from_pretrained('Helsinki-NLP/opus-mt-en-pl')
tokenizer = MarianTokenizer.from_pretrained('Helsinki-NLP/opus-mt-en-pl')
 
# Przykładowy tekst do tłumaczenia
text = "Hello, how are you?"
 
# Przetłumacz tekst
input_ids = tokenizer.encode(text, return_tensors='pt')
output_ids = model.generate(input_ids, max_length=50, num_beams=4, early_stopping=True)[0]
translated_text = tokenizer.decode(output_ids, skip_special_tokens=True)
 
print(f'Translated text: {translated_text}')