Utrata sposobu rozwiązania

Udało mi się wykonać niezbędne testy, żeby móc stwierdzić co jest nie tak. Niestety, dane se się zgadzały i już po pierwszym punkcie mojego testu stwierdziłam, że coś jest nie tak z algorytmem BFS w wersji rozproszonej. Wykonałam BFS w Hadoop ale bez rozdzielania wierzchołków na maszyny i wyniki były identyczne ze Sparkiem, więc najwidoczniej coś mi nie działało z moim programem rozproszonym.

Dopiero po rozpisaniu grafu (a nie było to proste przy tak dużej liczbie danych) udało mi się znaleźć mniejszy scenariusz dla którego rozproszony algorytm nie zadziałał.

Graf dla mniejszych danych w którym algorytm się wywala wygląda następująco (liczby przed średnikiem to wierzchołki, a po średniku to ich sąsiedzi):
0;1,5
1;0,2
2;1,3
3;2,4
4;3,8
5;0,6
6;5,7
7;6,8
8;7,4

Teraz załóżmy, że w maszynie A lądują wiersze 1 i 2, a wiersze 3,4,5,6,7,8 lądują w maszynie B. Wiersz zerowy ląduje w obu maszynach bo jest to wierzchołek startowy.

Najkrótszą trasą z 0 do 4 jest 0-1-2-3-4, czyli ma długość 4. Rozproszony algorytm powie niestety że 5. A to dlatego, że jeśli analizujemy wierzchołek x i jego sąsiad y był już odwiedzony, to krawędź między nimi uznaje się za zbędną – skoro y był odwiedzony to znaczy, że już w jakiś sposób się go wcześniej odwiedziło, więc znana jest krótsza droga do niego niż przez x. Tak więc maszyna B obliczy trasę do 4 o długości 5 następująco: 0-5-6-7-8-4. Przy odwiedzaniu 3 uzna, że krawędź między 3 i 4 jest zbędna, bo 4 już zostało wcześniej odwiedzone.

Przy połączeniu wszystkich informacji, 3 nie będzie miało odległości 6, jak obliczyła maszyna B (0-5-6-7-8-4-3) tylko 3 (0-1-2-3), ale krawędź między 3 i 4 została wcześniej usunięta. W ten sposób 0-1-2-3-4 nigdy nie zostanie obliczona i zostanie trasa do 4 o długości 5… Więc jest błąd.

Algorytm może zakładać, że krawędź między wierzchołkiem x i y jest zbędna wtedy i tylko wtedy jeśli y został wcześniej odwiedzony i wszystkie wierzchołki na poziomie y zostały odwiedzone. Rozpraszając wierzchołki po maszynach w losowy sposób, nie zwracając uwagę na poziomy w grafie, nie jesteśmy w stanie zagwarantować podkreślonego warunku – stąd mój błąd.

Wygląda na to, że zostaje mi do zaimplementowania klasyczna wersja algorytmu BFS która ma tyle iteracji co głębokość grafu, a jest to dość proste rozwiązanie.Szkoda, bo nie chciałam iść na łatwiznę tylko wymyślić jakąś optymalizację i przez to straciłam dużo czasu. Teraz wracam do początku żeby zaimplementować podstawową wersję. Szkoda!

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

Connecting to %s