Dwustronne Wyszukiwanie

Cel

W celu skrócenia czasu poszukiwania długości drogi pomiędzy dwoma punktami warto skorzystać z wyszukiwania dwustronnego. Polega ono na wystartowaniu poszukiwać z dwóch stron równocześnie. Metoda ta przyśpiesza proces wyszukiwania celu, ponieważ istnieje znacznie większa szansa, że rozwiązanie zostanie znalezione przed przejściem po wszystkich węzłach grafu jak to może mieć w przypadku np. wyszukiwania metodą BFS czy DFS.

Przykład

Dany jest następujący graf:

Szukamy ścieżki od węzła A do węzła I. Na kolejkę wrzucamy dwa wspomniane węzły. Następnie przeglądamy kolejne węzły jak w zwykłym algorytmie BFS. Do poszukiwań deklarujemy dodatkową tablicę, która będzie wskazywać aktualną odległość do tego węzła. Nie interesuje nas z którego węzła, ponieważ nie dopuścimy do nadpisania odległości. Oznacza to, że kolejne wywołania są następujące:

Podczas przeszukiwań algorytm wykrył, że jeden z sąsiadów aktualnie przeglądanego węzła ma już przypisany dystans. Ze względu na to, że to pierwsze takie wykrycie to znaczy, że właście została odnalezion długość pomiędzy dwoma węzłami, ponieważ wystarczy zsumować odległość sąsiada oraz aktualnego punktu. W tym przypadku F = 2, a G = 1, więc odległość od A do I to 2 + 1 + 1 = 4. Warto zauważyć, że dzięki podwójnemu wyszukiwaniu gałęzie CE oraz HJ wychodzące z punktu F nie musiały zostać wogle odwiedzone.

Implementacja

Poniżej została przedstawiona przykładowa implementacja funkcji SzukajDrogi(), która dla podanej macierzy o rozmiarze n szuka drogi od węzła start do węzła koniec.

1. int SzukajDrogi(int** macierz, int n, int start, int koniec) {
2.   if (start == koniec) return 0;
3.   dane* tab = new dane[n];
4.   for (int i = 0; i < n; i++) {
5.     tab[i].odleglosc = INT32_MAX;
6.     tab[i].aktywny = false;
7.   }
8.   tab[start].odleglosc = 0;
9.   tab[koniec].odleglosc = 0;
10.   tab[koniec].aktywny = true;
11.   queue<int> q;
12.   q.push(start);
13.   q.push(koniec);
14.   while (q.size() != 0) {
15.     int u = q.front();
16.     q.pop();
17.     tab[u].aktywny = false;
18.     for (int i = 0; i < n; i++) {
19.       if (macierz[u][i] == 0)
20.         continue;
21.       if (tab[i].odleglosc == INT32_MAX) {
22.         tab[i].odleglosc = tab[u].odleglosc + 1;
23.         tab[i].aktywny = true;
24.         q.push(i);
25.       } else if(tab[i].aktywny) {
26.         return tab[i].odleglosc + tab[u].odleglosc + 1;
27.       }
28.     }
29.   }
30.   return -1;
31. }

Początkowo funkcja deklaruje pustą tablicę w której będą przechowywane aktualne odległości do każdego węzła. Na kolejkę zostają wrzucone węzły: początkowy oraz końcowy. Dla nich należy też ustawić, że ich odległość wynosi 0. Następnie w pętli przeglądamy kolejnych sąsiadów każdego kolejnego węzła. Jednak, aby przyśpieszyć proces sprawdzenia czy natrafiliśmy na aktywny węzeł to podczas wkładania elementu na tablicę deklarujemy, że jest aktywny, a odwiedzając go deaktywujemy. Jeśli napotkamy aktywnego sąsiada przeglądając węzeł to znaczy, że droga została odnaleziona i zwracamy sumę ich odległości powiększoną o 1 (czyli o krawędź łączącą te węzły).

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   int n, start, koniec;
3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
4.   cin >> n;
5.   cout << "Podaj wezel poczatkowy\n s = ";
6.   cin >> start;
7.   cout << "Podaj wezel koncowy\n k = ";
8.   cin >> koniec;
9.   cout << "Podaj macierz grafu:\n";
10.   int** macierz = new int*[n];
11.   for (int i = 0; i < n; i++) {
12.     macierz[i] = new int[n];
13.     for (int j = 0; j < n; j++) {
14.       cin >> macierz[i][j];
15.     }
16.   }
17.   int odleglosc = SzukajDrogi(macierz, n, start, koniec);
18.   cout << "Najkrotsza droga wynosi " << odleglosc;
19.   system("pause");
20.   return 0;
21. }

• Kod źródłowy Implementacja