Python深度第一迷宫解算器

Question

我有一个python的作业，在那里我应该制作一个“机器人”从头到尾，并返回到目标的路径。我让机器人搜索，但我希望列表只显示从开始到结束的路径。现在，pathList返回所有访问过的广场。而且，当它到达目标时，它不会停止，而是继续其他节点。我遗漏了什么？

def find(labyrinth, robotPos, pathList = []):

    frontier = adjacent_passages(labyrinth, robotPos)   
    pathList.append(robotPos)

    if len(frontier) == 1:
        print("Corner")
        return []

    for i in range(0, len(frontier)):
        if frontier[i] == goal:
            pathList.append(frontier[i])
            return pathList

    for i in range(0, len(frontier)):
        if frontier[i] not in pathList:
            pathList.append(frontier[i])
            if (find(labyrinth, frontier[i], pathList) == []):
                pathList.pop()

    return pathList

Answer 1

我不知道这是否是您问题的答案，但是我注意到的第一件事是您不应该使用列表作为默认函数参数(pathList = [])。

请参阅"Least Astonishment" and the Mutable Default Argument

Answer 2

即使搜索失败，你也可以append robotPos to pathList而不删除它，这就是为什么这个列表包含了所有访问过的职位。我建议完全避免列表突变(append/pop)，而是将一个新值作为参数传递给下一次迭代：

if (find(labyrinth, frontier[i], pathList + [frontier[i]]) == [])...

其他可能的简化包括：

• drop robotPos。假设当前位置是path参数的最后一项，
• 使用一个循环而不是两个
• in循环，使用for x in stuff而不是for i in range(0, len(stuff))

就像这样

def find(path):

    if path[-1] == goal:
        return path

    for new_position in adjacent_positions(path[-1]):
        if new_position not in path:
            found_path = find(path + [new_position])
            if found_path:
                return found_path

    return None