存储python的深度优先搜索路径

我想写一个矩形网格的DFS，我从某个（x，y）坐标开始，必须达到目标坐标（xg，yg）。我需要我的函数返回这实际上是我采取的路线清单的路径，像存储python的深度优先搜索路径

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

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存储路径的逻辑。请帮忙！！

来源

2012-10-14 OneMoreError

请正确缩进您的代码，以便我们可以按照您的想法。应该将所有代码段放在'depthFirstSearch'内吗？ – jsbueno

希望这会说清楚。早点对不起！ – OneMoreError

你的问题不是很清楚。您的意思是说，当搜索到达死胡同时，路径需要包括回溯？ – Gene

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

来源

2012-10-14 04:03:29

这里的问题是，假设我在节点（x，y）上有两个孩子（x1，y1）和（x2，y2），这两个孩子都不是目标状态。现在，当我去（x1，y1）时，从那里我不能直接去（x2，y2）。我首先需要回到（x，y），然后再回到（x2，y2）。 – OneMoreError

尝试将x1，y1作为单个节点，在元组或两个元素列表中进行处理。 –

这将如何帮助？ – OneMoreError

存储python的深度优先搜索路径

回答

相关问题