Python DFS (CS 188 Berkeley Pacman)

Question

我不是伯克利的学生，我只是为了好玩而学习这门课程（所以你不是在帮助我作弊）。我已经实现了他们的项目 1，但我在问题 1 (DFS) 上没有通过自动评分器，而且只有问题 1。我总是对“是评分器错了！”表示怀疑。陈述，但在这种情况下......我认为自动评分器有一个错误:)

以下是我的实现，自动评分器失败了：

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)])

此代码通过（除了标记为添加/删除的两行之外相同）：

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(p0) # ADDED
        for pt1,dir1,cost1 in problem.getSuccessors(pt0):
            if pt1 not in visited:
                # visited.add(pt1) # REMOVED
                frontier.push(path + [(pt1,dir1)])

两者之间的唯一区别在于何时将节点标记为已访问。在后一个版本中，您在从堆栈中弹出时进行标记，然后生成邻居，如果您尚未访问过它们，则将它们添加到边界。在后者中，您生成邻居first，然后对于each邻居，您检查它们是否已被访问过，如果没有，则将它们添加到访问集和边界中。

两个版本都会找到相同的路径，并且据我了解，两个版本都是正确的。如果有的话，第一个版本实际上是一个更好的实现，因为它避免了对已经访问过的状态重新排队，如类似问题的“这个答案”中所述。您可以通过在排队之前检查状态是否不在边界上来避免第二个实现中固有的重新排队问题，但是扫描每个邻居的边界会浪费大量工作。 我在这里是否犯了一些概念上的误解，或者我的怀疑是否有根据？我尝试剖析自动评分器测试用例，但其中存在很多魔力，很难遵循

evaluate

中的

autograder.py

函数。但据我

可以

判断，这是失败的测试：

# 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

开始的，而评分者想要看到

A->D->G

（在这两种情况下

{A,D}

都是访问过的集合）。对我来说，这完全取决于邻居添加到边缘的顺序。如果

G

是添加到边缘的

A

的最终邻居（此处堆叠），那么我的解决方案是有意义的。如果不是的话就没有。这就是我陷入困境的地方，由于元编程的魔力，我无法从测试用例中看出邻居被添加的顺序。 编辑

发布此内容后不久，我发现了一个文件，该文件允许我在进行一些修改后检查失败的测试用例。对于未来的学习者，它位于“graphProblem.py”中。使用此文件加载上述图表并向我的 DFS 添加一些打印语句后，结果如下：

我的版本：

Step 1: Frontier = [A], Visited = {A}
Step 2: Frontier = [A->B,A->G,A->D], Visited = {A,G,D,B}
Step 3: Frontier = [A->B,A->G], Visited = {A,G,D,B}
Step 4: Goal

步骤 2 和步骤 3 之间是关键的区别。结束第 2 步，我们在堆栈顶部有 A->D，因此从第 3 步开始，我们处于状态 D。但是，由于我们在将所有节点生成为后继节点后就记录了所有已访问的节点（在步骤 3 中） 2），我们不向边界添加任何额外的路径，然后在第4步我们弹出A->G并到达目标。

将此与自动评分器要求的“正确”操作顺序进行对比：

Step 1: Frontier = [A], Visited = {A}
Step 2: Frontier = [A->B,A->G,A->D], Visited = {A}
Step 3: Frontier = [A->B,A->G,A->D->G], Visited = {A,D}
Step 4: Goal

这里，由于我们在步骤 2 中生成后继时没有将 

G

添加到访问集中（只有在出队时才将项目添加到访问集中），因此我们可以扩展路径

A->D

来添加

G 

尽管事实上

G

已经处于前沿。所以，

自动评分器是错误的

。

Answer 1

节点在被添加到边缘后不会立即被分类为已访问。相反，已访问意味着该节点已被扩展（即，尚未访问的所有邻居都被添加到边缘）。我想这就是你误解的根本原因。

因此，您找到的路径并不是 DFS 实际找到的路径（A->D->G 是 DFS 会选择的正确路径，因为 DFS 总是优先考虑更深的路径）。

这对于 DFS 来说可能看起来很迂腐（因为无论如何我们都不能保证 DFS 的良好路径），但对于 UCS 和 A* 来说这是至关重要的，因为如果我们在扩展节点之前将其分类为已访问的节点，我们可能会错过更好的路径。因此，

我们失去了 UCS 和 A* 所保证的最优路径属性（具有可接受的启发式）

。 我建议观看第三讲，教授回顾了 A* 的证明：

https://youtu.be/WhWA-a9GV5s?t=2478

您可能还想观看其中的一些早期部分以获得更多背景信息（例如什么是启发式以及可受理性意味着什么）。