0

我正在尝试为矩形网格编写 DFS，其中我从某个（x，y）坐标开始并且必须达到目标坐标（xg，yg）。我需要我的函数返回一个路径，该路径实际上是我所采取的方向列表，比如

action=['Up','Left','Left','Bottom']

到目前为止我的代码是这样的

def depthFirstSearch():
    visited=[]                # stores the vertices that I have visited  
    action=[]                 # this is what I have to return
    stack=Stack()             # the general stack used in DFS
    forward=Stack()           # stores the forward direction 
    reverse=Stack()           # stores the backward direction, in case we need to backtrack
    stack.push(getStartState())

    while not stack.isEmpty():
        tmp=stack.pop()
        if(GoalState(tmp)):
            return action
        if not tmp in visited:
            visited.append(tmp)
            if not forward.isEmpty():
                dirn=forward.pop()
                action.append(dirn)
                reverse.append(opposite(dirn))

        child1=getSuccessors(tmp)   # returns all the possible childs and direction as a list
        child2=[]

        for st in child1:
            if not st in visited:
                child2.append(st)

        if child2:
            for state in child2:
                stack.push(state[0])
                forward.push(state[1])
                reverse.push(oppposite(state[1])
        elif not child2:
            action.append(reverse.pop())

我是 python 新手，如果有人能在这里帮助我，我将不胜感激。我遇到了缩进问题。此外，我不太确定我的 DFS 存储路径的逻辑。请帮忙 ！！

4

1 回答 1

0

这是一篇解释深度优先搜索的文章。您所做的是以下，您有start节点，在您的情况下(x,y)，然后检查您访问的步骤是否已达到深度优先搜索的方式goal是(xg,yg)，它维护一个堆栈并将每个访问的节点推入堆栈和弹出它们并检查它是否是目标。在您的程序中，您必须将该检查步骤写入列表。我希望该教程链接可以帮助您入门。

于 2012-10-14T04:03:29.480 回答