Przeszukiwanie wszerz (BFS) i jego zastosowanie

We wprowadzeniu eksperymentowałeś z poruszaniem postaci przez labirynt w celu dotarcia do mety. Zaczęliśmy od ustalenia że meta jest dokładnie zero kroków od samej siebie. Potem znaleźliśmy wszystkie pola będące krok od celu. Potem wszystkie pola będące dwa kroki od celu. Potem trzy kroki od celu i tak dalej aż do momentu w którym trafiliśmy na pole na którym stała nasza postać. Jeżeli przechowywałeś pole w odległości $k$‍ z którego dostałeś się na pole w odległości $k+1$‍ to mogłeś prześledzić tą trasę w drugą stronę żeby znaleźć drogę od postaci do mety.

Poniżej obrazek który widzieliśmy we wprowadzeniu:

Widać, że jest to graf nieskierowany. Każdy wierzchołek odpowiada polu które nie jest ścianą a każda krawędź pada na przyległe pola.

Droga znaleziona przez powyższą procedurę ma ważną właściwość: żadna inna droga od postaci do mety nie przechodzi przez mniejszą ilość pól. Jest tak ponieważ użyliśmy algorytmu znanego jako przeszukiwanie wszerz. Przeszukiwanie wszerz, znane także jako BFS (breadth-first search) znajduje najkrótszą ścieżkę z danego wierzchołka do wszystkich innych wierzchołków pod względem ilości krawędzi w tej ścieżce.

Weźmy kolejny przykład przeszukiwania wszerz: gra "sześć stopni od Kevina Bacona". W tej grze gracze próbują połączyć aktorów i aktorki z Kevinem Baconem w zależności od tego kto z kim grał w jakim filmie. Im krótszy łańcuch tym lepszy. Zadziwiające jest jak dużo aktorów i aktorek można powiązać z Kevinem Baconem w łańcuchu krótszym niż sześć. Dla przykładu weźmy Kate Bell, australisjką aktorkę. Grała w Makbecie z Nashem Edgertonem w 2006 r.; Edgerton wystąpił w Matriksie Reaktywacji z Laurencem Fishburnem w 2003; Fishburne zaś wystąpił w Rzece tajemnic z Kevinem Baconem w 2003. Zatem liczba Bacona Kate Bell wynosi 3. W rzeczywistości jest kilka sposób na to by sprawdzić, że liczba Bacona dla Kate Bell wynosi 3. Możesz sprawdzić liczbę Bacona dla dowolnego aktora używając strony The Oracle of Bacon.

Jak mogłeś się domyślić, strona The Oracle of Bacon działa na podstawie grafu nieskierowaniego w którym każdy wierzchołek odpowiada aktorowi, jeżeli dana para aktorów występowała w tym samym filmie to między nimi jest krawędź. Algorytm wyszukiwania wszerz rozpoczęty od wierzchołka Kevina Bacona znajdzie najkrótszą ścieżkę do wszystkich innych aktorów i aktorek.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.