Раньше я думал, что BFS страшный. Это не так уж плохо. Хотите хорошую структуру данных для практики, но не можете создать сложный график? Просто создайте сетку с препятствиями! Вы также можете использовать свою файловую систему для дерева, возможно, это будет в описании к следующему посту. В этом случае мы будем использовать сетку. Старый добрый двумерный массив. Давайте заполним доску некоторыми неотрицательными целыми числами:
void iterativeFill(int[][] b){
int x = 0;
for(int i = 0; i < b.length; i++){
for(int j = 0; j < b[i].length; j++){
b[i][j] = x++;
}
}
}
Давайте разместим несколько препятствий в случайных местах в каждом ряду. Мы поместим препятствия numPerRow со значениями -1 в сетку, если препятствие не является нашим целевым элементом.
void randomObstacles( int[][] board, int numPerRow, int target){
for (int r = 0; r < board.length; r++ ){
for(int s = 0; s < numPerRow; s++){
int randomColumn = (int)(Math.random()*board[r].length);
if(board[r][randomColumn] != target){
board[r][randomColumn] = -1;
}
}
}
}
Теперь общий цикл для BFS:
- удалить элемент из очереди
- проверить, нашли ли мы нашу цель
- отметить как посещенный
- добавить соседей этой ячейки в очередь, но только если эти соседи не посещаются, не являются препятствиями и находятся в пределах сетки
Кроме того, мы будем отслеживать ячейки, которые мы посещаем, чтобы мы могли распечатать нашу сетку, когда мы ищем и наблюдаем, как bfs работают. Для этого случая мы сделаем поисковик немного ограниченным, ограничив его движение только вверх или вправо. Это даст нам несколько интересных случаев в зависимости от расположения препятствий, которые не позволят ему найти цель.
Вот наша сетка с препятствиями в ячейках -1. Давайте установим нашу цель как ячейку со значением 28 и нашим источником в нижней левой ячейке.
Приготовьтесь к потрясающим визуальным эффектам:
Выделим старт, финиш и препятствия на пути
Теперь давайте посмотрим, как BFS делает свое дело.
Вот полный код.
Так в чем сложность этого плохого мальчика? Ну, в худшем случае это примерно близко к каждой ячейке и двум краям каждой ячейки, так как мы смотрим только вверх и вправо.
Давайте визуализируем часть среды выполнения, посмотрев на количество циклов BFS, которые мы выполнили на матрице 10 на 10. При 1000 прогонах мы получаем медиану 58, 90-й процентиль 66 и 10-й процентиль 35.
