为什么我的深度优先搜索实施损坏

Question

我一直在试验深度优先搜索的不同方式。我找到了一些工作方式，但他们涉及一些相当乏味的字典工作。我已经使用列表开发了一个新想法，但是这个实现返回的行为与所需的结果不匹配。我会尝试尽我所能地评论代码：

start = problem.getStartState()   ## returns an (x, y) tuple 
children = problem.getSuccessors(start) ##returns the children of a parent node in ((start     
              state), action, cost) format. 
stack = Stack()       ##creates a Stack (LIFO) data structure 
visited = []        ##list of visited nodes 
visited.append(start) 
for child in children: 
    stack.push((child, [], [], 0))   ##push children to fringe in the format of (child, 
    while stack:       ##path taken, actions taken, cost) 
     parent = stack.pop() 
     node = parent[0] 
     if parent[0] in visited: continue 
     visited.append(parent[0]) 
     path = parent[1] + [node[0]]   ##assigns previous path/actions/cost to new 
     actions = parent[2] + [node[1]]  ##node, creating a cumulative, ordered list of 
     print actions       ##the path/actions and a cumulative cost 
     cost = parent[3] + node[2] 
     if problem.isGoalState(node[0]): 
      print parent[2] 
      return parent[2]     ## returns list of actions 
     children = problem.getSuccessors(node[0]) 
     if children != []: 
      for child in children: 
       stack.push((child, path, actions, cost)) ##assigns cumulative lists to child 

任何人都可以看到我的问题可能出现在这个实现中吗？顺便说一句，我知道DFS在大多数情况下是一种效率低下的算法。但是一旦我得到这个实现的权利，它应该能够通过简单地改变存储父节点的子节点的数据结构来跨越到其他搜索算法。

Answer 1

CS188 PAL：d这真的很难读到这里你的代码......所有这些指标％） 使用

一般情况下，DFS使用recursive function，大致是如下（未经测试）最好的实现更多的变量，它会更清晰。 我的解决方案：

 
def depthFirstSearch(problem): 
    fringe = util.Stack(); 
    expanded = set(); 
    fringe.push((problem.getStartState(),[],0)); 

    while not fringe.isEmpty(): 
     curState, curMoves, curCost = fringe.pop(); 

     if(curState in expanded): 
      continue; 

     expanded.add(curState); 

     if problem.isGoalState(curState): 
      return curMoves; 

     for state, direction, cost in problem.getSuccessors(curState): 
      fringe.push((state, curMoves+[direction], curCost)); 
    return []; 

我希望我不需要评论它。这很容易阅读:) 有一个美好的一天;）

Answer 2

您似乎有一个名称冲突。请注意：

children = problem.getSuccessors(start) ##returns the children of a parent node in ((start     
... 
for child in children: 
    ... 
    while stack: 
     ... 
     children = problem.getSuccessors(node[0]) 
     ... 

第一次迭代后，由于内部循环中的子项覆盖原来的子项，所以原来的子项会丢失。

def dfs(problem, state, visited): 
    visited.append(state) 

    # have we reached the goal? 
    if problem.isGoalState(state): 
     return [state] 

    for child in problem.getSuccessors(state): 
     # if child is already visited, don't bother with it 
     if child in visited: continue 

     # otherwise, visit the child 
     ret = dfs(problem, child, visited) 

     if ret is not None: 
      # goal state has been reached, accumulate the states 
      ret.append(state) 
      return ret 

    return None # failed to find solution here 
    # note that Python return None by default when reaching the end of a function