Python 深度优先搜索在找到时停止

Question

我对此有疑问。当搜索区域上述坐标的格子状态==5时，表示停止移动到该位置。出于某种原因，它继续存在，我一直在努力找出原因。我假设它会在其他人的眼中变得显而易见！

def depthfirstsearch(visited,graph,vertex):
    # Do a depth-first search of all neighbours if found stop.
    moveto(vertex,3)
    visited.append(vertex)
    if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
        x = vertex[0] - 1
        y = vertex[1]
        moveto((x, y), 0)
        return
    else:
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                depthfirstsearch(visited, graph, neighbour)

Answer 1

您的函数 return 找到目标后就会启动。

if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
    # ..
    return

但是，它 returns None 并且递归调用没有做任何事情，因为它 returned:

if neighbour not in visited:
    depthfirstsearch(visited, graph, neighbour)

如果对 depthfirstsearch() 的调用找到了目标，您希望该函数也能 return，并得到肯定的结果。如果调用没有找到它，您会希望它继续搜索。

因此，您需要：

if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
    # ..
    return True

并且：

if neighbour not in visited:
    if depthfirstsearch(visited, graph, neighbour):
        return True

最后，您可以依赖函数 returning None 完成时无需显式 returning，但这有点难看。 None 的计算结果为 False 作为 bool，但为了清楚起见，您也可以只在最后 return False 和 type-safeness.

所以，结果：

def depthfirstsearch(visited,graph,vertex):
    # Do a depth-first search of all neighbours if found stop.
    moveto(vertex,3)
    visited.append(vertex)
    if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
        x = vertex[0] - 1
        y = vertex[1]
        moveto((x, y), 0)
        # found it, report success
        return True
    else:
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                if depthfirstsearch(visited, graph, neighbour):
                    # found in recursion, report success
                    return True
    # if this point is reached, this call didn't find it anywhere
    return False

Python 深度优先搜索在找到时停止

Python Depth First Search stop when found

python

depth-first-search

python-3.x