Задача из Моего Собеседования в Amazon - Поиск в Ширину

Разбираем задачу из моего первого собеседования в Amazon. Я устраивался на позицию Junior Backend в Берлинский офис.
Задача решается с помощью известного алгоритма BFS (поиск в ширину).

[denys_barkhatov]

С анимацией отлично получилось.
Очень интересно смотреть твои разборы задач + тембр и подача приятные.
Если позволяет время - пиши побольше видео.

[misterbob]

Никогда даже не хотел понимать задачи с шахматной доской, после просмотра понял алгоритм 💪🏾

[amirilifee]

Саша анимация вообще супер!!! Видео было настолько интересным что ни секунды не промотал. Спасибо за такое понятное и четкое объяснение

[jpxfrd]

Долго тебя не было, рад новому видео!

[GSergeiA]

Мощно ты запарился за анимации!) Но получилось явно очень наглядно и понятно!

[khetagabramov]

Для всех, кто пишет что в алгоритме ошибка, так как мы смотрим только на предыдущий слой и теряем информацию о предыдущих слоях:

На самом деле ошибки нет, вероятно комментаторы путают с алгоритмом DFS или вариантом BFS на очереди (где нужно запоминать все посещенные вершины).

Почему этот алгоритм корректен? Если предположить что на текущем шаге мы попытаемся пойти из ячейки X в ячейку Y, в которой уже были, но которая лежит не в предыдущем слое, то значит она лежит в предпредыдущем или более ранних слоях. Но тогда мы бы перешли по этому ребру Y - X в тот момент, когда рассматривали эту клетку Y и в этом случае X лежало бы не в текущем слое, а в следующем за слоем, в котором лежит Y. Но в предположении X лежит именно в текущем, а Y лежит не в предыдущем. Значит предположение неверно, а значит достаточно рассматривать для клеток, которые мы хотим посетить, лежат ли они в предыдущем слое. И этого будет достаточно.

[olegorlov]

Если брать очень большое поле, то для общего случая нахождения кратчайшего пути стоит добавит разбивку на сектора.
В случае с конем можно сделать еще проще, первые ходы должны делаться с учетом кратчайшей дистанции, и только начиная с дистанции в 4 клетки выполнять обозначенный автором кульбит

[_Smaie_]

Здесь можно (даже бы я сказал нужно) использовать алгоритм А*, а за эвристическию функцию можно взять манхеттенское расстояние от коня до конечной клетки

[laremin_developer]

Выпускай чаще пожалуйста, ты лучший мой мотиватор )))

[antonkuzin]

Привет! Заметил пару неточностей.
1. Ты говоришь, что не посещаешь уже посещенные клетки. Но это утверждение верно только для предыдущего слоя - в коде ты никак не помечаешь те клетки, что были посещены ещё раньше.
2. Формально это можно назвать обходом графа в ширину, но мне кажется, это решение методом динамического программирования. А если попытаться оптимизироавть решение и не проверять заведомо более длинные пути (а ограничиться только квадратом (0, 0) (n, n)), то это уже точно не будет обходом графа в ширину(так как мы не посещаем все вершины).
3. Решение данной конкретной задачи обходом графа в ширину довольно неэффективно - сложность получается ~(2n)^2*Log(n), тогда как методом динамического программирования мы можем обойтись n^2, перебрав каждую вершину урезанного квадрата лишь единожды. n это большая по модулю координата целевой точки.

Upd: попытавшись набросать решение методом динамического программирования, понял, что у меня не получается) Конь ходит слишком сложно, чтобы за один проход можно было заполнить массив, не возвращаясь к уже посещённым клеткам. А вот в обходе графа ограничить поле всё равно было бы нелишним.

[EvilYarik]

Тут экспоненциальный рост клеток с каждым слоем и симметрия 4-го порядка, стоила взять координаты цели по модулю и начать с двух ходов 1, 2 и 2, 1 на первом слое. Так-же можно игнорировать все клетки с отрицательными координатами, это сэкономит память.

[ДаниилМонахов-рч]

Вообще в классическом БФС используется очередь (Queue), а не некие уровни.
1. Запихиваешь в очередь первую клетку.
2. Извлекаешь.
3. Находишь всех соседей, в нашем случае восемь возможных ходов коня.
4. Фильтруешь уже посещённые.
5. Запихиваешь в очередь.
6. Гото 2 до победы.

Если смотреть только на previous_layer, то потеряется информация о посещённых клетках на предыдущих ходах.

[danieldeveloper]

Congrats Alex! Good explanation.

Here is a point you can deal better with:
You were java dev, and you use java terminology in your verbal explanations, but code is written in python. So little fellas can easily miss those word about hashed collection.

Hope you'll continue doing videos like this)

[lknfgjk]

Спасибо! Отличное видео, интересная задача! Ждем новых роликов.

[yohohowowowo]

Можно ещё параллельно вычислять дорогу от коня к точке и от точки к коню ровно до тех пор покуда не найдётся первое пересечение. Действий суммарно будет больше, но зато массив будет меньше...хотел сказать я, но потом обнаружил одно геометрическое свойство: сумма длин окружностей, пересекающихся в одной точке равна длине окружности с радиусом, равным расстоянию между центрами этих окружностей)))

[НиколайВоронин-оъ]

Спасибо за bfs!
Но в аналитическом решении сложность О(1).
N = (lnl + lml)/3 ± 4. Начальные координаты коня (0, 0), конечные (n, m). Если рассмотреть как ходить в конце (варианты), то формула будет без погрешностей.

[МаксимМаликов-гъ]

Решение автора работает похоже на работу ИИ, он также связывает всё послойно, и между всеми элементами одного слоя и другого присутствует связь, таким образом происходит имитация синапсов, что помогает ему осмыслить любые возможные варианты.

[alexeyromanovds]

Спасибо за задачу! Очень подробно объяснил)

[flashbackenigma]

Блин, смотрю каждое твое видео. Спасибо за контент. Тоже мечтаю попасть в google

[kirill.leontovich]

Во-первых нормализовать данные. Стартовая клетка пусть будет (0, 0), а координаты цели во-первых возьмем по модулю, что не изменит количество шагов, а перенесет цель в верхний правый квадрант заеркально осей, и затем если Х > Y поменяем их местами, чтобы поместить цель выше диагонали (0, 0) - (N, N). Для квадрата 5х5 проще всего создать хэш-таблицу, выйдет всего 14 элементов. Если цель дальше 5 клеток то "прыгаем" к ней двигая доску, или вычитая (2, 1) из координат цели, добавляя к счетчику 1. Если на очередной итерации цель ушла левее оси Y (отрицательный X), либо "упала" под диагональ (Y < X), то вычитаем не (2, 1), а либо (2, -1), либо (1, 2) соответственно. Физический смысл легко увидеть если нарисовать каждую из ситуаций. Как только на очередной итерации мы попали в квадрат 5х5 к цели, снова нормализуем координаты и берем значение из таблицы, добавляем к счетчику итераций и получаем итоговое.

Некрасивая таблица из 14 значений с лихвой компенсируется сложностью О(n) и нулевым выделением памяти на каждой итерации. Описывать сложнее, чем написать код.