[已解决]关于 Python 递归时修改全局变量失败的问题

ElmLiu

def dfs_maze(path, target):
        global paths
        maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]

        if path[-1] == target:
                paths.append(path)
                print(path)
                return
        for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
                node = [path[-1][0] + each[0], path[-1][1] + each[1]]
                if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
                        path.append(node)
                        dfs_maze(path, target)
                        path.pop(-1)

def main():
        dfs_maze([[0,0]], [4, 4])

        for each in paths:
                print(each)
paths = []
main()

就是一个深搜解决迷宫最短路径的函数，path 是一个二维数组，储存已经走过的每一个点，target 是终点。在边界条件满足时，打印出来的路径是没问题的。但在深搜结束后，打印出来的 paths 是一堆[[0,0]]的二维数组，这是为何?

最佳答案

月排行榜 / 总排行榜

塔利班

2018-9-23 20:10:33

path分配的地址一样，每次做个切片

def dfs_maze(path, target):
        global paths
        maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]

        if path[-1] == target:
                paths.append(path[:])
                print(path)
                return
        for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
                node = [path[-1][0] + each[0], path[-1][1] + each[1]]
                if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
                        path.append(node)
                        dfs_maze(path, target)
                        path.pop(-1)

def main():
        dfs_maze([[0,0]], [4, 4])

        for each in paths:
                print(each)
paths = []
main()

跳转到最佳答案楼层

claws0n

paths.extend(path)

append 多了 [], 比较无效

ElmLiu

claws0n 发表于 2018-9-23 19:07
append 多了 [], 比较无效

不好意思，不是太懂，打印出来的path是二维数组，描述了走过的路径，用append(path)会出问题吗？我希望最终得到的paths是三维的，即包含所有可行的路径。换成extend的话，paths就成二维了，每条路径的点都罗列到一起了。

claws0n

ElmLiu 发表于 2018-9-23 19:16
不好意思，不是太懂，打印出来的path是二维数组，描述了走过的路径，用append(path)会出问题吗？我希望最 ...

塔利班

path分配的地址一样，每次做个切片

def dfs_maze(path, target):
        global paths
        maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]

        if path[-1] == target:
                paths.append(path[:])
                print(path)
                return
        for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
                node = [path[-1][0] + each[0], path[-1][1] + each[1]]
                if -1 not in node and 5 not in node and node not in path and maze[node[0]][node[1]] != '#':
                        path.append(node)
                        dfs_maze(path, target)
                        path.pop(-1)

def main():
        dfs_maze([[0,0]], [4, 4])

        for each in paths:
                print(each)
paths = []
main()

ElmLiu

塔利班 发表于 2018-9-23 20:10
path分配的地址一样，每次做个切片

您好，能说的详细一点不，每次给函数传path这个值难道不是新分配空间吗？

塔利班

不会啊，你从头到位一共就用了一共path，只不过过程中一直在变化

塔利班

print(id(path))
函数里加上这个，你可以确认下

RIXO

塔利班 发表于 2018-9-23 20:17
print(id(path))
函数里加上这个，你可以确认下

呃，代码我看懂了，不过你们讨论的是个什么东西，我怎么跟不上你们的思路。。。。。、
什么叫三维的数组，哪三维啊。。。。。。
还有你知不知道如果路径不允许重复的话，怎么写这个代码啊

ElmLiu

塔利班 发表于 2018-9-23 20:17
print(id(path))
函数里加上这个，你可以确认下

确实，传入列表是可以修改原值的，类似于引用， 那请问做切片的意义是什么呢？

塔利班

ElmLiu 发表于 2018-9-23 20:50
确实，传入列表是可以修改原值的，类似于引用， 那请问做切片的意义是什么呢？

放一个深拷贝，path后续的变化不会影响添加进的元素

塔利班

RIXO 发表于 2018-9-23 20:48
呃，代码我看懂了，不过你们讨论的是个什么东西，我怎么跟不上你们的思路。。。。。、
什么叫三维的数组 ...

这个已经是不重复版本了吧

claws0n

塔利班 发表于 2018-9-23 20:54
这个已经是不重复版本了吧

按照 C 的思路是没有问题的，我只是好奇，每一次 append, 是有添加数组，但是对之前的数据覆盖了

ElmLiu

RIXO 发表于 2018-9-23 20:48
呃，代码我看懂了，不过你们讨论的是个什么东西，我怎么跟不上你们的思路。。。。。、
什么叫三维的数组 ...

就是paths储存所有可行的路径，每条路径又是一个二维数组，包含路径的每个点。
这个不重复，给路径添加新节点的时候判断过了新节点是否包含在走过的节点中

塔利班

claws0n 发表于 2018-9-23 21:03
按照 C 的思路是没有问题的，我只是好奇，每一次 append, 是有添加数组，但是对之前的数据覆盖了

添加了多少个，都是path，虽然放进去时Path内容不一样

ElmLiu

塔利班 发表于 2018-9-23 20:52
放一个深拷贝，path后续的变化不会影响添加进的元素

嗯... 我还是在以后的实践中慢慢去体会这道理  谢谢了！

claws0n

RIXO 发表于 2018-9-23 20:48
呃，代码我看懂了，不过你们讨论的是个什么东西，我怎么跟不上你们的思路。。。。。、
什么叫三维的数组 ...

递归、回溯法
都是一维扩展，还没有到 3 维，2 维而已

claws0n

塔利班 发表于 2018-9-23 21:05
添加了多少个，都是path，虽然放进去时Path内容不一样

啊，我知道哥哥说什么了，高维数组……

claws0n

ElmLiu 发表于 2018-9-23 21:05
嗯... 我还是在以后的实践中慢慢去体会这道理  谢谢了！

def dfs_maze(path, target):
        global paths
        maze = [[" ","#","#"," "," "],[" "," "," ","#"," "],["#"," "," ","#"," "],[" "," "," ","#","#"],[" "," "," "," "," "]]
        
        if path[-1] == target:
                print(path)
                paths.append(path[:])  ##这个要深拷贝
                return paths
            
        for each in [[0,1], [0,-1], [1, 0], [-1, 0]]:
                node = [path[-1][0] + each[0], path[-1][1] + each[1]]
                if (-1 not in node) and (5 not in node) and (node not in path) and (maze[node[0]][node[1]] != '#'):
                    path.append(node)
                    dfs_maze(path, target)
                    path.pop(-1)

def main():
        dfs_maze([[0,0]], [4, 4])

        print("printing all paths")
        for each in paths:
                print(each)
               
paths = []
main()