我的DFS算法在回溯情况下不能正常工作

Question

我有一个问题，我需要使用DFS来解决。到目前为止，这是我的功能，根据我提供的自动分级器，它适用于4/5测试，仅在回溯情况下失败:

def depthFirstSearch(problem):
    stack=Stack()
    if problem.isGoalState(start):
    return actions
while stack:
    parent=stack.pop()
    if flag==1:
            action=actionStack.pop()
    if parent in visited: continue
    visited.add(parent)
    if problem.isGoalState(parent):
                    while parent!=None:
                            actions.append(action)
                            parent=parentMap[parent]
                            action=actionMap[parent]
                    return actions
    children=problem.getSuccessors(parent)
    for child in children:
            stack.push(child[0])
            actionStack.push(child[1])
            parentMap[child]=parent
            if flag==1:
                    actionMap[child] = child[1]
    flag=1
util.raiseNotDefined()

getsuccessor返回一个三元组列表(状态、操作、成本)，我需要返回一个操作列表来引导代理从开始到目标。提前抱歉，我是python的新手。有提示吗?

编辑:这是它在

失败的树

失败:test_cases/q1/graph_backtrack.test图:

     B   
     ^
     |
    *A --> C --> G
     |
     V
     D
    A is the start state, G is the goal.  Arrows mark 
    possible state transitions.  This tests whether
    you extract the sequence of actions correctly even
    if your search backtracks.  If you fail this, your
    nodes are not correctly tracking the sequences of
    actions required to reach them.
student solution:       ['2:A->D', '1:A->C', '0:C->G']
student expanded_states:    ['A', 'D', 'C']
correct solution:       ['1:A->C', '0:C->G']
correct expanded_states:    ['A', 'D', 'C']
correct rev_solution:       ['1:A->C', '0:C->G']
correct rev_expanded_states:    ['A', 'B', 'C']

Answer 1

您只有一组操作。而不是每一步一个动作。如果你要往下走到7，那么你的动作应该是1,2,3,4,5,6,7，而不是1,2,3,6,7

1-2-3-4-5
0-0-6-0-0
0-0-7-0-0

不要害怕将当前状态打包到每个下一步操作中。除非你有一个大得离谱的解决方案空间，否则你应该没问题。