需要帮助改进递归 DFS 实现

Question

我正在尝试在 Python 中使用递归实现 DFS 我在python方面不是很好，但正在尝试通过探索和经验来学习它。 以下是我根据可视化设计的代码

rowNums = [0, -1, 0, 1]
colNums = [-1, 0, 1, 0]


class Point():
    x:int
    y:int
    def __init__(self, x, y) -> None:
        self.x = x
        self.y = y

class Node():
    coordinates:Point
    distance:int
    def __init__(self, coords:Point, distance:int):
        self.coordinates = coords
        self.distance = distance

def isSafe(point:Point, nrow, ncol):
    if point.x>=0 and point.x<nrow and point.y>=0 and point.y<ncol:
        return True
    return False


def DFS(maze:list[list[int]], 
        src:Point, 
        dest:Point, 
        nrow:int, 
        ncol:int):
    
    visited = []
    if maze[src.x][src.y] != 1 or maze[dest.x][dest.y] != 1:
        return -1
    
    for i in range(len(maze)):
        visited.append([False]*len(maze[i]))
    
    visited[src.x][src.y] = True
    def recurTillDeath(node:Node):
        point = node.coordinates
        if point.x == dest.x and point.y == dest.y:
            print("Found it")
            return node.distance
        else:
            print(str(point.x) + " " + str(point.y))  
            for i in range(0,4):
                print("i Values for Point ("+ str(point.x) + " " + str(point.y)  +") is "+str(i))
                newP = Point(point.x+rowNums[i],point.y+colNums[i])
                print(str(newP.x) + " " + str(newP.y)) 
                if isSafe(newP,nrow,ncol) and maze[newP.x][newP.y] != 0 and visited[newP.x][newP.y] != True:  
                    visited[newP.x][newP.y]=True
                    val = recurTillDeath(Node(newP,node.distance+1))
                    if val is not None:
                        return val
            
        
    return recurTillDeath(Node(src,0))

if __name__ == "__main__":

    inputMaze = [[1, 0, 0, 0],
                 [1, 1, 0, 1],
                 [0, 1, 0, 0],
                 [1, 1, 1, 1]]

    src  = [0, 0]
    dest = [3, 3]

    srcObject = Point(src[0], src[1])
    destObject = Point(dest[0], dest[1])

    val = DFS(inputMaze, srcObject, destObject, len(inputMaze), len(inputMaze[0]))

    if val == -1:
        print("Path does not exist")
    else:
        print("Length of DFS path is: ", val)

此代码有效，但我想知道，我是否在我的 recurTillDeath 函数中正确使用了递归？是否有更好、更标准化的复现方法？

编辑：当我找到原始问题的解决方案时，修改了问题以寻求代码改进帮助

Answer 1

看起来不错，除了一件事：

DFS 可以 return -1、None 或 non-negative 距离。 -1 仅在源或目标不是具有 1 值的单元格时才 returned。 None 在无法找到路径的所有其他情况下被 returned。这意味着当 val 是 None.

时主程序会误解结果

例如，通过将关键的 1 替换为 0，将输入迷宫更改为没有路径，然后 运行 程序：

inputMaze = [[1, 0, 0, 0],
             [1, 1, 0, 1],
             [0, 1, 0, 0],
             [1, 0, 1, 1]]
#                ^-------------changed to zero

然后你的代码输出：

Length of DFS path is: None

...虽然它确实应该说：

Path does not exist

最好避免 None returns，在这些情况下也避免 return -1。

不是错误，而是在其他情况下可能导致错误的代码味道：当您打算将属性用作 实例时，不要在 class 级别定义属性 属性。它们有不同的用途和行为。在你的代码中没有负面影响，因为在构造函数中，你总是定义同名的实例属性，所以没有混淆。但是 class 成员没有任何用处。

我可能有的所有其他评论都不是错误，而只是代码审查。

我post这里是你的代码的修订版本，其中包含对我所做更改的评论：

from __future__ import annotations

class Point:
    # Remove class members
    def __init__(self, x, y) -> None:
        self.x = x
        self.y = y

    # With this, never worry about how to print a Point
    def __repr__(self):
        return repr((self.x, self.y)) 

    # Make this a method to facilitate navigation from Point to neighbor
    def add(self, point: Point):
        return Point(self.x + point.x, self.y + point.y)

# Use tuples for immutable data, all CAPS for constant names, and combine
# together what is related, which in this case can be Point instances:
DIRECTIONS = (Point(0, -1), Point(-1, 0), Point(0, 1), Point(1, 0))

# Node class is not needed, as distance can be managed 
# via argument and return value

# But use a class for managing the maze
class Maze:
    # Don't ask caller to pass values that can be derived (ncol nrow)
    def __init__(self, maze: list[list[int]]):
        self.maze = maze
        self.nrows = len(maze)
        self.ncols = len(maze[0])

    # Make this a method:
    def isSafe(self, point: Point):
        # Use chained comparisons and just return the result (it is boolean)
        # Also include the cell test
        return (0 <= point.x < self.nrows and 0 <= point.y < self.ncols
                and self.maze[point.x][point.y] != 0)

    # Use lowercase method name
    # By adding visited as parameter, we can use this function for recursion
    def dfs(self, src: Point, dest: Point, visited: list[list[bool]]=None):
        if self.maze[src.x][src.y] != 1 or self.maze[dest.x][dest.y] != 1:
            return -1
    
        if visited is None:  # First call (not recursive)
            # Populate visited without append:
            visited = [[False]*self.ncols for _ in range(self.nrows)]    

        visited[src.x][src.y] = True

        print(src)
        if src.x == dest.x and src.y == dest.y:
            print("Found it")
            return 0  # Distance is 0 -- will increase when backtracking
        else:
            for step in DIRECTIONS:
                newP = src.add(step)
                print(f"Neighbor: {newP}")
                # Comparing with True can be simplified 
                # Incorporate the cell's value check in `isSafe`
                if self.isSafe(newP) and not visited[newP.x][newP.y]:
                    val = self.dfs(newP, dest, visited)  # Use dfs itself
                    if val >= 0:  # Don't work with None
                        return val + 1  # Add the one here! No need for Node.
        return -1  # Always return number


if __name__ == "__main__":
    inputMaze = [[1, 0, 0, 0],
                 [1, 1, 0, 1],
                 [0, 1, 0, 0],
                 [1, 1, 1, 1]]

    src  = [0, 0]
    dest = [3, 3]

    # Create maze instance once, allowing multiple dfs calls if wanted
    maze = Maze(inputMaze)
    # Can unpack using asterisk
    distance = maze.dfs(Point(*src), Point(*dest))

    if distance == -1:
        print("Path does not exist")
    else:
        print("Length of DFS path is: ", distance)