Dydaktyka >
Notatki
BFS - przeglądanie grafu wszerz
Niech dany będzie graf nieskierowany, który ma n wierzchołków i m krawędzi. Graf będziemy pamiętali w komputerze za pomocą listy sąsiedztwa, tzn. dla każdego wierzchołka u=1,2,...,n będziemy pamiętali listę (właściwie to wektor z biblioteki STL) jego sąsiadów. W poniższym programie zmienna G jest tablicą wektorów z biblioteki STL. Z góry zakładamy, że graf nie będzie miał więcej niż 106 wierzchołków.
Kod w języku C++ z wykorzystaniem wektorów (vector) i kolejki (queue) z biblioteki STL. #include<vector> #include<queue> using namespace std; vector<int> G[1000001]; bool col[1000001]; int dist[1000001]; // Przeglądanie grafu wszerz // Obliczamy wartości dist[...] oznaczające // odległości od wierzchołka 'a' void bfs(int a) { queue<int> Q; Q.push(a); col[a] = true; // wstaw wierzchołek 'a' do kolejki dist[a] = 0; while( !Q.empty() ) // dopóki kolejka nie jest pusta { int u = Q.front(); Q.pop(); for (int i=0; i<G[u].size(); i++) { int v = G[u][i]; if ( col[v]==false ) { Q.push(v); col[v] = true; dist[v] = dist[u]+1; } } } } |
Odległość edycyjna
Dla danych dwóch słow A i B wyznaczyć ich odległość edycyjną, tzn. ile co najmniej znaków należy usunąć lub wstawić w jednym słowie, aby uzyskać drugie. Na przykład dla słów: deskorolka i stokrotka, ich odległość wynosi 7, bo Oto program w C++, który rozwiązuje ten problem. // Odległość edycyjna dwóch słów #include<iostream> using namespace std; int D[1001][1001]; int main() { int n, m, i, j; string A, B; cin >> A >> B; // wczytaj słowa A i B n = A.size(); m = B.size(); for (i=0; i<=n; i++) D[i][0]=i; for (j=0; j<=m; j++) D[0][j]=j; for (i=1; i<=n; i++) for (j=1; j<=m; j++) if (A[i-1]==B[j-1]) D[i][j] = D[i-1][j-1]; else D[i][j] = min( D[i-1][j], D[i][j-1] ) + 1; cout << D[n][m] << "\n"; return 0; } |
Algorytm Dijkstry
Wyobraź sobie, że masz sieć połączeń pomiędzy miastami; każde połączenie ma przypisany pewien koszt, oraz że chcesz znaleźć najtańszą drogę od miasta A do miasta B. Jak taki problem rozwiązać? Jak robią to: Google Maps, albo każdy dobry Nawigator GPS?
Rzecz jasna --- korzystają z algorytmu Dijkstry. Wczoraj na naszych lekcjach opowiedzieliśmy sobie, jak on działa. W załączniku znajduje się moja prezentacja zawierająca symulację działania tego algorytmu i nie tylko (o tym porozmawiamy po feriach).
W skrócie, algorytm Dijkstry służy do znajdowania najkrótszych ścieżek z wybranego wierzchołka (źródła) do wszystkich pozostałych wierzchołków w grafie ważonym z nieujemnymi wagami. Oto jego zapis w pseudojęzyku
Założenie, że w grafie wszystkie wagi na krawędziach są nieujemne jest bardzo istotne. Spróbuj skonstruować przykład grafu, dla którego algorytm Dijkstry źle zadziała, tj. nie znajdzie najkrótszych ścieżek od źródła. Wskazówka: twój graf powinien mieć co najmniej jedną krawędź z ujemną wagą :-) ImplementacjaUwaga poniższy kod został napisany na sucho, tzn. nawet go nie kompilowałem. Zresztą na pewno by się skompilował, bo wczytywanie grafu poniżej zostało podane jako przykład. Nie umieściłem go nawet w żadnej funkcji. W poniższym programie brakuje nawet funkcji main. Poniższy program proszę potraktować jako materiał dydaktyczny, a nie kod gotowy do zastosowania techniki Kopiego Pejsta (CTRL+C, CTRL+V). W poniższym programie zastosowałem inny sposób realizacji kolejki priorytetowej niż zrobiłem to kiedyś na mojej RNO-Wiki, czyli tutaj. #include<queue> #include<vector> #include<iostream> using namespace std; vector< pair<int,int> > G[1000000]; // reprezentacja grafu z wagami //~~~~~~~~~~~~~~~~~~~~~~~ /** Wczytywanie grafu **/ //~~~~~~~~~~~~~~~~~~~~~~~ int n,m; cin >> n >> m; // wczytaj liczbę wierzchołków i krawędzi for (int i=0; i<m; i++) { cin >> a >> b >> c; // wczytaj krawędź a--b z kosztem c G[a].push_back( make_pair(b,c) ); G[b].push_back( make_pair(a,c) ); // assert( c>=0 ); // upewnij się, że wagi są nieujemne } //~~~~~~~~~~~~~~~~~~~~~~~ /** Algorytm Dijkstry **/ //~~~~~~~~~~~~~~~~~~~~~~~~ int dist[1000000]; // tablica obliczonych odległości od źródła bool mark[1000000]; // będziemy zaznaczali wierzchołki, które zostały z kolejki usunięte #define INF 2000000000 priority_queue< pair<int,int> > Q; // kolejka wierzchołków do obsługiwania // zasada jest taka: w kolejce trzymamy pary (-c, u), gdzie c oznacza koszt // ścieżki do źródła z wierzchołka o numerze u void dijkstra(int s) // s = source, czyli numer wierzchołka (źródła) { int u,d; // inicjalizacja for (int u=0; u<n; u++) { mark[u] = false; dist[u] = INF; } dist[s] = 0; // ustawiamy odległość źródła od źródła na zero Q.push( make_pair(0,s) ); // wstawiamy wierzchołek s do kolejki while( !Q.empty() ) { // wyciągamy wierzchołek nr u, dla którego odległość d od źródła s jest najmniejsza u = Q.front().second(); d = -Q.front().first(); Q.pop(); if ( mark[u]==true ) continue; // jeśli już go kiedyś usunęliśmy, to możemy nic nie robić, bo na pewno wtedy miał mniejsze d mark[u] = true; // oznaczamy, że wierzchołek u został usunięty z kolejki for (int i=0; i<G[u].size(); i++) { // rozpatrujemy krawędź u--v z kosztem c int v = G[u][i].first(); int c = G[u][i].second(); // jeśli v nie ma jeszcze obliczonej najkrótszej odległości od źródła s, // oraz to co ma dotychczas obliczone da się poprawić, to poprawiamy if ( !mark[v] && dist[v] > dist[u]+c ) { dist[v] = dist[u]+c; Q.push( make_pair(-dist[v],v) ); // i wstawiamy v do kolejki // Uwaga: może się więc zdażyć, że v jest kilka razy w kolejce // nie przeszkadza nam to, bo razem z v są różne koszty. // Gdy będziemy usuwali v z kolejki, to na pewno weźmiemy tego z najmniejszą odległością od źródła // Następnych będziemy po prostu pomijali, czyli usuwali nic nie robiąc (patrz na instrukcję continue sprzed 18 wierszy) } } } } Prezentacja działania |
Kolejka priorytetowa
Obiecałem dzisiaj klasie Ia, że napiszę trochę o kolejce priorytetowej. Otóż mówiliśmy na lekcji, że jest ona dziwnym tworem, nazwaliśmy go WORKIEM, do którego można wrzucać liczby i wyjmować w kolejności zgodnej z ich priorytetem. W STL-u, tj. po wpisaniu na samym początku tego #include<queue>możemy korzystać z kolejki w następujący sposób priority_queue<int> Q; // deklaracja kolejki priorytetowej Q Q.push( 10 ); // wrzuca do kolejki liczbę 10 x = Q.top(); // podstawia pod x wartość liczby w kolejce Q z największym priorytetem Q.pop(); // usuwa z kolejki Q liczbę z największym priorytetemDomyślnie największy priorytet mają liczby największe, tzn. jeśli wykonamy Q.push(20); Q.push(30); Q.push(4); x = Q.top();to wartość zmiennej x będzie wynosiła 30. Jeśli chcemy, aby największy priorytet miały liczby o najmniejszej wartości, to zgodnie z tym, co pisałem już kiedyś na moim blogu [tutaj], musimy zadeklarować kolejkę w następujący sposób: |
1-5 of 5