使用堆栈实现深度受限的路径查找

user4858185 发表于 Dev

用户名

嘿，就像标题所说的那样，我正在尝试在Python3中实现深度限制搜索，该搜索将返回给定图形，起始顶点和目标顶点的路径。我在如何强制执行搜索限制方面有些挣扎。到目前为止，我有：

def dfs(g, v, goal, limit=-1):

    SENTINEL = object()    
    visitedStack = [v]
    path = ""

    while visitedStack:
        currentVertex = visitedStack.pop()    

        if g.getVertex(currentVertex) != None:
            if g.getVertex(currentVertex).visited == False:
                path += currentVertex + ' -> '

                g.getVertex(currentVertex).hasBeenVisited()

                if currentVertex == goal: 
                    return path[:-3]

                elif currentVertex == SENTINEL:
                    limit += 1

                elif limit != 0:
                    limit -= 1
                    visitedStack.append(SENTINEL)
                    visitedStack.extend(g.getVertex(currentVertex).getConnections()) 

     return "Depth limit was reached"

编辑：我更改了一些代码来检查访问的顶点。编辑后，有时返回的搜索无法正常工作。例如，我将深度限制设置为3，但返回的路径为4或5。其他时候，我会将限制设置为7并返回“达到限制”。注意：最小路径为3

根二

当搜索到更深的层次时，将一个哨兵推到堆栈上并减小限制。当您从堆栈弹出哨兵时，请增加级别。

def dfs_limit(g, start, goal, limit=-1):
    '''
    Perform depth first search of graph g.
    if limit >= 0, that is the maximum depth of the search.
    '''
    SENTINEL = object()
    visitedStack = [start]
    path = []

    while visitedStack:
        currentVertex = visitedStack.pop()

        if currentVertex == goal: 
            path.append(currentVertex)
            return ' -> '.join(path)

        elif currentVertex == SENTINEL:
            #finished this level; go back up one level
            limit += 1
            path.pop()

        elif limit != 0:
            # go one level deeper, push sentinel
            limit -= 1
            path.append(currentVertex)
            visitedStack.append(SENTINEL)
            visitedStack.extend(g.getVertex(currentVertex).getConnections())