Szukam motywacji

OK, nie udało się z moim pomysłem… No i nie mogę tego przeboleć. Myśl, że muszę zaczynać od początku, a przynajmniej cofnąć się o parę miesięcy strasznie mnie przygnębia.

Jutro muszę koniecznie napisać wersję klasyczną BFS-a na Hadoop i przetestować ją dla małych danych, średnich i wreszcie dla danych z Wikipedii.

Następnie należy zmienić jeden warunek w algorytmie, żeby działał dla grafów z wagami. Algorytm nie powinien przestać analizować wierzchołków jak już je odwiedzi lecz w każdym momencie kiedy jakaś ścieżka jest polepszana, jest niezbędna dodatkowa iteracja algorytmu.

W doborze algorytmów ogranicza mnie przede wszystkim dostępna biblioteka Sparka z którą muszę porównywać moje rozwiązania.

Muszę się też zastanowić, czy nie da się jakoś wykorzystać algorytmu do znalezienia połączonych komponentów (ang. connected components) w grafie – taki algorytm istnieje w Sparku i chyba można go prosto napisać w środowisku równoległym. Ale zanim to zrobię, warto skończyć wreszcie tego BFS-a!

Plan na jutro:

  1. BFS dla grafu bez wag. Klasyczne rozwiązanie Hadoop. Dla danych małych, średnich i wreszcie dużych, niemieszczących się w pamięci maszyny.
  2. BFS dla grafu z wagami. Powinno być łatwo przerobić algorytm poprzedni. Opisać. Pokazać promotorowi. Mieć jeden algorytm (w dwóch przypadkach) z głowy.
  3. Rozważyć algorytmy APSP, Connected components, Triangle Count i Page Rank. Powinno wystarczyć. Nie powinno być trudno.

Motywacjo, przybywaj!

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ń )

w

Connecting to %s