Math
Wszerz i w głąb
Dwie kopie labiryntu, dwa przejścia, komórka na takt. Warstwa, w której przeszukiwanie wszerz znajduje komórkę, JEST najkrótszą odległością - to tożsamość. W głąb nigdy nie jest krócej, a o ile dłużej, zależy od celu.
Co się dzieje
Jeden labirynt, dwa przeszukiwania, jedno odkrycie na krok. Po lewej przeszukiwanie wszerz bierze komórki z KOLEJKI - kto pierwszy przyszedł, ten pierwszy wychodzi - więc rozchodzi się pierścieniami, a pierścień, w którym znajduje komórkę, to jej najkrótsza odległość: w labiryncie bez wag przeszukiwanie wszerz JEST szukaniem najkrótszej ścieżki. Po prawej przeszukiwanie w głąb bierze je ze STOSU - kto ostatni przyszedł, ten pierwszy wychodzi - więc nurkuje w pierwszy zakręt i wycofuje się dopiero w ślepym zaułku; jego trasa to trasa, bez obietnicy, że krótka. Niebieskie komórki czekają w strukturze, szarozielone są zakończone, złoty kwadrat jest rozwijany, a pod każdym labiryntem wypisane są prawdziwa kolejka i stos, następna komórka pierwsza. Rysuj ściany, klikaj w labirynt, by przewidzieć, dokąd dalej pójdzie to przeszukiwanie, i rób krok. Jeśli cel jest odcięty ścianami, oba przeszukiwania kończą się na brzegu składowej startu i mówią to wprost.
Równania modułu
Równania labirynt na siatce m x m, czterech sąsiadów, start w lewym górnym rogu; kolejność sąsiadów: w górę, w prawo, w dół, w lewo - taka sama w obu przeszukiwaniach wszerz: warstwa, na której znaleziono komórkę, JEST długością najkrótszej ścieżki - tożsamość, sprawdzona względem NIEZALEŻNEJ relaksacji do punktu stałego oraz, na małych siatkach, względem pełnego wyliczenia ścieżek prostych pusta siatka: odległość do (i, j) = i + j; liczba komórek w odległości d = min(d, m−1) − max(0, d−m+1) + 1; najszersza warstwa = m przy d = m − 1; przeciwległy róg = 2(m−1) = 40 przy m = 21 oba przeszukiwania obejmują TEN SAM zbiór - składową startu, policzoną niezależnie przez las zbiorów rozłącznych - i każde patrzy na każdą krawędź dwa razy: 2|E| = 1196 przy 21x21 i 20 % ścian przeszukiwanie w głąb nigdy nie daje drogi krótszej, a o ile dłuższej, zależy od KOMÓRKI: do przeciwległego rogu pustej siatki zajmuje tyle samo, 2(m−1) kroków, a do komórki o krok poniżej startu zajmuje 421 przy m = 21 na pustej siatce drzewo przeszukiwania w głąb jest ŚCIEŻKĄ HAMILTONA - każda komórka ma co najwyżej jedno dziecko, najgłębsza leży na głębokości m²−1, a parzystość decyduje, gdzie kończy się wąż: (1,0) dla parzystego m, (m−1,0) dla nieparzystego m 21x21, 20 % ścian, cel w przeciwległym rogu: wszerz 40 kroków po odwiedzeniu 370 komórek; w głąb 50 kroków po odwiedzeniu 53 - oba płacą, ale inną monetą ten sam labirynt, cel w środku: wszerz 20, w głąb 156; a na 297 z 371 osiągalnych komórek droga w głąb jest co najmniej trzy razy dłuższa
