是否可以在不复制访问节点的情况下迭代地进行深度优先搜索？

Question

背景

我正在二维网格中搜索单词。
我们可以搜索left/right和up/down。
例如，在此网格中，从 (0,0) 开始搜索 "abef" 将 return True

示例（网格 1）：

我在哪里

递归版本给出了预期的结果（参见下面的 dfs_rec()）。
迭代版本也给出了预期的结果（见下文 dfs_iter()）。但是，在这个版本中，我将 visited 集的副本复制到每个节点的堆栈上。

我的问题是

有没有办法避免在迭代版本中复制（visited.copy()），而在递归版本中add/remove到单个visited集？

进一步的细节和我尝试过的东西...

在 dfs_rec() 中有一个名为 visited 的 set()，它已通过 visited.add((row,col)) 和 visited.remove((row,col))[=43 更改=]
但在 dfs_iter() 中，我每次都将 visited.copy() 压入堆栈，以防止节点被错误地标记为已访问。
我见过一些迭代示例，它们使用单个 visited 集合，没有复制或从集合中删除任何内容，但这并没有给我这些示例中的正确输出（参见下面使用 grid3 的 dfs_iter_nocopy()）。

以这个网格为例：

假设您搜索 "abexxxxxx"（覆盖整个网格），预期输出将是 True

但是 dfs_iter_nocopy() 会在 grid2 或 grid3 之一上给出不正确的输出（它们只是镜像，一个会通过，一个会失败），具体取决于按照您将节点推入堆栈的顺序。
发生的事情是，当您搜索 "abexxxxxx" 时，它会搜索这样的路径（只命中 5 个 x，而它需要 6 个）。

它将 (1,0) 处的 x 标记为已访问，当需要搜索该分支时，它会在 (1,0) 处停止，如下所示：

代码

def width  (g): return len(g)
def height (g): return len(g[0])
def valid (g,r,c): return r>=0 and c>=0 and r<height(g) and c<width(g)

def dfs_rec (grid, word, row, col, visited):

    if not valid(grid, row, col): return False  # (row,col) off board
    if (row,col) in visited:      return False  # already checked
    if grid[row][col] != word[0]: return False  # not right path

    if grid[row][col] == word: # len(word)==1
        return True

    visited.add((row,col))

    if dfs_rec(grid, word[1:], row, col+1, visited): return True
    if dfs_rec(grid, word[1:], row+1, col, visited): return True
    if dfs_rec(grid, word[1:], row, col-1, visited): return True
    if dfs_rec(grid, word[1:], row-1, col, visited): return True

    # Not found on this path, don't block for other paths
    visited.remove((row,col))

    return False

def dfs_iter (grid, start_word, start_row, start_col, start_visited):

    stack = [ (start_row, start_col, start_word, start_visited) ]

    while len(stack) > 0:

        row,col,word,visited = stack.pop()

        if not valid(grid, row, col): continue
        if (row,col) in visited: continue
        if grid[row][col] != word[0]: continue

        if grid[row][col] == word:
            return True

        visited.add((row,col))

        stack.append( (row, col+1, word[1:], visited.copy()) )
        stack.append( (row+1, col, word[1:], visited.copy()) )
        stack.append( (row, col-1, word[1:], visited.copy()) )
        stack.append( (row-1, col, word[1:], visited.copy()) )

    return False

def dfs_iter_nocopy (grid, start_word, start_row, start_col):

    visited = set()
    stack = [ (start_row, start_col, start_word) ]

    while len(stack) > 0:

        row,col,word = stack.pop()

        if not valid(grid, row, col): continue
        if (row,col) in visited: continue
        if grid[row][col] != word[0]: continue

        if grid[row][col] == word:
            return True

        visited.add((row,col))

        stack.append( (row, col+1, word[1:]) )
        stack.append( (row+1, col, word[1:]) )
        stack.append( (row, col-1, word[1:]) )
        stack.append( (row-1, col, word[1:]) )

    return False

if __name__ == '__main__':

    grid  = [ 'abc', 'def', 'hij' ]
    grid2 = [ 'abx', 'xex', 'xxx' ]
    grid3 = [ 'xba', 'xex', 'xxx' ]

    print( dfs_rec(grid, 'abef', 0, 0, set() ) == True   )
    print( dfs_rec(grid, 'abcd', 0, 0, set() ) == False )
    print( dfs_rec(grid, 'abcfjihde', 0, 0, set() ) == True )
    print( dfs_rec(grid, 'abefjihd', 0, 0, set() ) == True )
    print( dfs_rec(grid, 'abefjihda', 0, 0, set() ) == False )
    print( dfs_rec(grid, 'abefjihi', 0, 0, set() ) == False )

    print( dfs_iter(grid, 'abc', 0, 0, set() ) == True   )
    print( dfs_iter(grid, 'abef', 0, 0, set() ) == True   )
    print( dfs_iter(grid, 'abcd', 0, 0, set() ) == False )
    print( dfs_iter(grid, 'abcfjihde', 0, 0, set() ) == True )
    print( dfs_iter(grid, 'abefjihd', 0, 0, set() ) == True )
    print( dfs_iter(grid, 'abefjihda', 0, 0, set() ) == False )
    print( dfs_iter(grid, 'abefjihi', 0, 0, set() ) == False )

    print( dfs_rec(grid2, 'abexxxxxx', 0, 0, set() ) == True   )
    print( dfs_iter(grid2, 'abexxxxxx', 0, 0, set() ) == True   )
    print( dfs_iter_nocopy(grid2, 'abexxxxxx', 0, 0 ) == True   )
    print( dfs_rec(grid3, 'abexxxxxx', 0, 2, set() ) == True   )
    print( dfs_iter(grid3, 'abexxxxxx', 0, 2, set() ) == True   )
    print( dfs_iter_nocopy(grid3, 'abexxxxxx', 0, 2 ) == True   ) # <-- Problem, prints False

Answer 1

您注意到递归版本能够通过在回溯时用 visited.remove((row,col)) 重置它来使用单个 visited 累加器。所以这里也可以通过模拟函数调用栈来做同样的事情，这样我们就知道什么时候回溯了。

def dfs_iter_nocopy (grid, start_word, start_row, start_col):
    visited = []   # order now matters
    last_depth = 0 # decreases when backtracking 
    stack = [ (start_row, start_col, start_word, last_depth+1) ]

    while len(stack) > 0:
        row, col, word, depth = stack.pop()
        if not valid(grid, row, col): continue
        while last_depth >= depth: # just backtracked
            last_depth -= 1
            visited.pop()          # simulate returning from the call stack
        if (row,col) in visited: continue
        if grid[row][col] != word[0]: continue
        
        if grid[row][col] == word:
            return True

        visited.append((row,col))
        last_depth = depth
        depth += 1 # simulate adding recursive call to the call stack
        stack.append( (row, col+1, word[1:], depth) )
        stack.append( (row+1, col, word[1:], depth) )
        stack.append( (row, col-1, word[1:], depth) )
        stack.append( (row-1, col, word[1:], depth) )
    return False

深度会随着探索新的图块而增加，但会随着我们用尽特定路径的可能性并恢复到较早的分叉而减少。这就是我所说的回溯。

编辑：变量名

是否可以在不复制访问节点的情况下迭代地进行深度优先搜索？

Is it possible to do a depth first search iteratively without copying visited nodes?

python

algorithm

graph-theory

depth-first-search

tree-search

背景

我在哪里

我的问题是

进一步的细节和我尝试过的东西...

代码