伯克利CS188 Pacman项目DFS实现与自动grader争议问题

我并非伯克利大学学生，仅出于兴趣学习该校CS188课程，已完成Project1的DFS（深度优先搜索）实现，但仅Question1未通过自动grader测试。我通常不认同“是grader出错”的说法，但此次我认为自动grader存在问题。

两种DFS实现对比 #

未通过测试的实现（标记visited时机：生成邻居时） #

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:
    """
    start = problem.getStartState()
    frontier = util.Stack()
    frontier.push([(start,None)])
    visited = {start}
    while frontier:
        path = frontier.pop() # path = [(pt1,dir1),(pt2,dir2)...]        
        pt0, dir0 = state = path[-1]
        if problem.isGoalState(pt0):
            p = [p[1] for p in path if p[1]] # return dirs only, not points, first dir is "None" so filter that out
            return p
        for pt1,dir1,cost1 in problem.getSuccessors(pt0):
            if pt1 not in visited:
                visited.add(pt1)
                frontier.push(path + [(pt1,dir1)])

通过测试的实现（标记visited时机：弹出节点时） #

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:
    """
    start = problem.getStartState()
    frontier = util.Stack()
    frontier.push([(start,None)])
    visited = {start}
    while frontier:
        path = frontier.pop() # path = [(pt1,dir1),(pt2,dir2)...]        
        pt0, dir0 = state = path[-1]
        if problem.isGoalState(pt0):
            p = [p[1] for p in path if p[1]] # return dirs only, not points, first dir is "None" so filter that out
            return p
        visited.add(pt0) # ADDED
        for pt1,dir1,cost1 in problem.getSuccessors(pt0):
            if pt1 not in visited:
                # visited.add(pt1) # REMOVED
                frontier.push(path + [(pt1,dir1)])

两者唯一差异在于标记节点为visited的时机：前者在生成邻居时检查并标记visited，可避免重复入队已访问状态，效率更优；后者仅在从栈中弹出节点时标记visited。我认为两种实现均为正确的图搜索DFS实现。

失败测试用例分析 #

失败的测试为一个图搜索测试：

Graph where BFS finds the optimal solution but DFS does not #

class: "GraphSearchTest"
algorithm: "depthFirstSearch"

diagram: """
/-- B
| ^
| |
| *A -->[G]
| | ^
| V |
-->D ----/

A is the start state, G is the goal. Arrows
mark possible transitions
"""

The following section specifies the search problem and the solution. #

The graph is specified by first the set of start states, followed by #

the set of goal states, and lastly by the state transitions which are #

of the form: #

<start state> <actions> <end state> <cost> #

graph: """
start_state: A
goal_states: G
A 0:A->B B 1.0
A 1:A->G G 2.0
A 2:A->D D 4.0
B 0:B->D D 8.0
D 0:D->G G 16.0
"""

我的实现找到的路径是A->G，而grader期望A->D->G，这完全取决于邻居加入frontier的顺序。

问题根源与结论 #

查看测试用例的graphProblem.py后发现：

• 我的实现会在生成A的邻居时就将G标记为visited，导致后续无法从A->D扩展到G；
• Grader认可的实现仅在弹出节点时标记visited，因此可以走A->D->G的路径。

DFS的合法路径本身就依赖于邻居的遍历顺序，只要找到能到达目标的路径即为正确实现，Grader强制要求唯一路径的行为存在错误。

内容的提问来源于stack exchange，提问作者Solaxun