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

Question

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

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 并返回 "limit reached"。注意：最小路径是 3

Answer 1

当搜索进行到更深层次时，将哨兵压入堆栈并递减限制。当你从堆栈中弹出一个哨兵时，增加级别。

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())

如果图形中存在循环或多条路线，您还需要跟踪访问过哪些节点，以免重复工作或陷入无限循环。

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

Implementing Depth Limited Path Finding with Stack

python

search

depth-first-search