Dydaktyka‎ > ‎

Notatki

Pary z biblioteki STL

opublikowane: 15 lis 2016, 12:39 przez Rafał Nowak

Notatka zapisana została w dokumencie PDF i dostępna pod tym adresem.

BFS - przeglądanie grafu wszerz

opublikowane: 26 lut 2015, 08:32 przez Rafał Nowak   [ zaktualizowane 26 lut 2015, 08:36 ]

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.

  • Algorytm BFS(a) przegląda graf zaczynając od wierzchołka a.
  • W algorytmie wykorzystuje się kolejkę, do przechowywania wierzchołków, które należy odwiedzić.
  • Każdy wierzchołek, który trafia do kolejki jest oznaczany; w programie nadajemy mu wartość col[u] = true.
  • Algorytm dodatkowo wyznacza tablicę dist[u], która przechowuje informacje o odległościach odwiedzonych wierzchołków od wierzchołka początkowego a.
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

opublikowane: 3 mar 2011, 08:23 przez Rafał Nowak   [ zaktualizowane 26 lut 2015, 09:03 przez Rafał Nowak ]

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 destokoroltka (skreślone i czerwone znaki oznaczają edycję).

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

opublikowane: 10 lut 2011, 00:19 przez Rafał Nowak   [ zaktualizowane 3 mar 2016, 00:36 przez Rafał Nowak ]

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ą :-)

Implementacja

Uwaga 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
Algorytmy grafowe

Kolejka priorytetowa

opublikowane: 26 sty 2011, 06:06 przez Rafał Nowak   [ zaktualizowane 3 mar 2016, 00:36 przez Rafał Nowak ]

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 priorytetem
Domyś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:
// deklaracja kolejki priorytetowej Q, w której element top()
// ma najmniejszą wartość
priority_queue<int, vector<int>, greater<int> > Q;
Przykładowe programy można znaleźć na mojej RNO-Wiki [tutaj], a szczegółową dokumentację techniczną na stronie autorów biblioteki STL - tutaj.

1-5 of 5