Math
Ширина и глубина
Два одинаковых лабиринта, два обхода, клетка в такт. Слой, на котором ширина нашла клетку, равен кратчайшему пути — это тождество. Глубина не короче никогда, а насколько длиннее — зависит от того, куда идти.
Что происходит
Один лабиринт, два поиска, одно открытие за шаг. Слева поиск в ширину берёт клетки из ОЧЕРЕДИ — первым пришёл, первым ушёл, — поэтому расходится кольцами, и кольцо, на котором он находит клетку, — её кратчайшее расстояние: в невзвешенном лабиринте поиск в ширину И ЕСТЬ поиск кратчайшего пути. Справа поиск в глубину берёт их из СТЕКА — последним пришёл, первым ушёл, — поэтому ныряет в первый поворот и отступает только из тупика; его маршрут — просто маршрут, без обещания краткости. Синие клетки ждут в структуре, серо-зелёные завершены, золотой квадрат раскрывается, а под каждым лабиринтом перечислены настоящие очередь и стек, следующая клетка первой. Рисуйте стены, нажимайте в лабиринте, чтобы предсказать, куда поиск пойдёт дальше, и делайте шаг. Если цель отрезана стенами, оба поиска заканчиваются на краю компоненты старта и прямо говорят об этом.
Уравнения модуля
Уравнения лабиринт на сетке m x m, четыре соседа, старт в левом верхнем углу; порядок соседей: вверх, вправо, вниз, влево - одинаков в обоих поисках поиск в ширину: номер слоя, на котором найдена клетка, РАВЕН длине кратчайшего пути - это тождество, проверенное по НЕЗАВИСИМОЙ релаксации до неподвижной точки и, на малых сетках, по полному перебору простых путей пустая сетка: расстояние до (i, j) = i + j; клеток на расстоянии d = min(d, m−1) − max(0, d−m+1) + 1; самый широкий слой = m при d = m − 1; дальний угол = 2(m−1) = 40 при m = 21 оба поиска покрывают ОДНО И ТО ЖЕ множество - компоненту связности старта, независимо подсчитанную лесом непересекающихся множеств - и каждый просматривает каждое ребро дважды: 2|E| = 1196 при 21x21 и 20 % стен поиск в глубину никогда не бывает короче, а насколько он длиннее, зависит от КЛЕТКИ: до дальнего угла пустой сетки он делает те же 2(m−1) шагов, а до клетки на шаг ниже старта - 421 при m = 21 на пустой сетке дерево поиска в глубину - это ГАМИЛЬТОНОВ ПУТЬ: у каждой клетки не более одного потомка, самая глубокая лежит на глубине m²−1, а чётность решает, где кончается змейка: (1,0) при чётном m, (m−1,0) при нечётном m 21x21, 20 % стен, цель в дальнем углу: в ширину 40 шагов после просмотра 370 клеток; в глубину 50 шагов после просмотра 53 - платят оба, но разной монетой тот же лабиринт, цель в центре: в ширину 20, в глубину 156; а на 297 из 371 достижимых клеток путь поиска в глубину не менее чем втрое длиннее
