爲什麼我的深度優先搜索實施損壞

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