Нужна помощь в понимании этого кода глубины поиска - PullRequest
Новая
       26

Нужна помощь в понимании этого кода глубины поиска

0 голосов
/ 02 апреля 2019

Я довольно новичок в программировании на Python, и мне трудно понять следующий код ниже.Он основан на теории графов с использованием DFS, чтобы найти наибольшую область среди всех областей островов.1 представляет остров, а 0 представляет воду в сетке. 

def maxAreaOfIsland(grid):
    row, col = len(grid), len(grid[0])
    def dfs(i, j):
        if 0 <= i <= row - 1 and 0 <= j <= col - 1 and grid[i][j]:
            grid[i][j] = 0

#scans through all rows & cols and 
#turns number in the grid into 0 if all conditions are true?

            return  1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
        return 0  

# recursive function that checks up, down, left, right in the grid. 
# when does it return 1?

    return max(dfs(i, j) for i in range(row) for j in range(col))

maxAreaOfIsland([[1,0,1,1,1],
                 [0,0,0,1,1],
                 [1,1,1,0,1]]) 
Out: 6

Я включил комментарии, которые отражают мое понимание до сих пор, но не уверен, что это правильно.Я в замешательстве, начиная с четвертой строки, особенно в рекурсивной части. Может ли кто-нибудь объяснить подробно? Как правило, такие коды имеют тенденцию иметь очередь / очередь для записи, был ли остров посещен, но я не думаю, что этот код имеет это?

1 Ответ

1 голос
/ 02 апреля 2019

Полагаю, вопрос в том, чтобы понять алгоритм, а не Python.Предоставленный код Python довольно прост.

Код содержит функцию maxAreaOfIsland, которая в свою очередь содержит рекурсивную функцию dfs.Эти 2 функции образуют 2 уровня вычислений.Давайте посмотрим на эти слои отдельно. 

# outer layer
def maxAreaOfIsland(grid):
    row, col = len(grid), len(grid[0])
    # function dfs() definition
    return max(dfs(i, j) for i in range(row) for j in range(col))

Таким образом, внешний слой очень прост - вычислите dfs(i, j) для всех возможных i и j, затем выберите максимальное вычисленное значение. 

# inner layer - slightly modified
def dfs(i, j):
    # recursive case
    if (0 <= i <= row - 1 and 0 <= j <= col - 1) and grid[i][j] == 1:
        grid[i][j] = 0  # this is how we remember visited cells since we don't count zeros
        # optional prints to look at the grid during computation
        # print(i, j)
        # print(*grid, sep='\n', end='\n\n')
        count_current = 1
        count_neighbors = dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1)
        return  count_current + count_neighbors
    # trivial case and out-of-borders case
    else:
        return 0

Внутренний слой немного сложнее.Что оно делает?(1) Он получает i и j.(2) Если ячейка содержит 0, то это тривиальный случай (вода) или мы не в сетке - просто верните 0.(3) Если ячейка содержит 1, то это рекурсивный регистр (земля) - функция начинает подсчитывать количество всех 1, примыкающих к данной ячейке, с каждым счетом 1, превращающимся в 0, чтобы избежать двойного счета.

Ваша примерная сетка имеет 3 строки (0, 1, 2) и 5 ​​столбцов (0, 1, 2, 3, 4).Предположим, мы находимся на i = 0, j = 2.Это 1.Мы считаем его (текущий результат равен 1), превращаем его в 0 и смотрим на его соседей по одному - верхний сосед находится вне сетки, нижний сосед - 0, левый сосед - 0, правый сосед -1.Мы не возвращаем текущий результат, а переходим к правому соседу i = 0, j = 3.Мы считаем это (результат cuurent равен 2), превращаем его в 0 и смотрим на соседей.Верхний сосед находится вне сетки, нижний сосед - 1.Мы останавливаемся здесь, мы не возвращаем текущий результат, мы помним о еще 2 соседях, мы переходим к нижнему соседу i = 1, j = 3.Мы считаем это (текущий результат равен 3), превращаем его в 0 и смотрим на соседейВерхний сосед 1.Мы останавливаемся здесь, мы не возвращаем текущий результат, мы помним о еще 3 соседях, мы переходим к верхнему соседу i = 0, j = 3.И так далее.

Мой совет - нарисовать простую примерную сетку (с ручкой на листе бумаги) и вручную применить к ней алгоритм dfs.

...