似乎无法为无墙迷宫创建递归算法

Question

我已经为此工作了一段时间，这就是我到目前为止所得到的...这段代码不起作用。此代码仅供参考。作业是一个没有围墙的迷宫。我必须使用递归算法。每个 space 都有一个数字，当我降落在 space 上时，这个数字告诉我我可以在特定方向上移动多少。我必须return路径。（如果有解决方案，我已经做了 return True 或 False 的版本。）我似乎无法 return 路径本身。

def pathsolve(self, start, end, vis=None):


    z=self.__getitem__(start)
    x,y=start




    b=False

    if path==None:
        path=deque()

    if vis==None:
        vis=deque()

    if start == end:
        vis.appendleft(start)
        return True
    elif start in path:
        return False
    elif z==0:
        return False
    else:
        #visited.add(start)
        path.append(start)


        if self.onboard((x+z,y)) and (x+z,y) not in path:
            #print("going to"+str((x+z,y))+" by "+str(z)+" from "+str    (start))
            b=self.pathsolve((x+z,y),end, path)

            #print()
        if self.onboard((x,y+z)) and (x,y+z) not in path and b == False:
            #print("xgoing to"+str((x,y+z))+" by "+str(z)+" from "+str(start))
            b=self.pathsolve((x,y+z),end, path)

            #print()
        if self.onboard((x,y-z)) and (x,y-z) not in path and b == False:
            #print("ygoing to"+str((x,y-z))+" by "+str(z)+" from "+str(start))
            #print(self.onboard((x,y-z)))
            b=self.pathsolve((x,y-z),end, path)
            #print(path)
        if self.onboard((x-z,y)) and (x-z,y) not in path and b == False:
            #print("zgoing to"+str((x-z,y))+" by "+str(z)+" from "+str(start))
            #print(end)
            b=self.pathsolve((x-z,y),end, path)

       # if b==True and start is not  
            vis.appendleft(start)
    return b

Answer 1

一些注意事项：

与 vis 作为参数传递的方式相反，并且需要在整个递归搜索过程中保持其状态，这不是 path 的工作方式：它应该是本地的仅从递归调用中获取 return 值并将当前单元格 (start) 添加到该值的变量。
vis不应该是deque，而是set，更适合快速了解某个单元格是否被访问过[=20] =]

以下是您的编码方式：

def pathsolve(self, start, end, vis=set()):
    z=self.__getitem__(start)
    x,y=start
    if start == end:
        return [end]
    if start in vis or z==0:
        return None
    vis.add(start)
    for step in [(x+z,y),(x-z,y),(x,y+z),(x,y-z)]:
        if self.onboard(step):
            path=self.pathsolve(step, end, vis)
            if path: # prepend current cell to the path that was found
                return [start] + path
    return None # None of the possible directions led to the end point.

这当然假设您的其他方法都得到了很好的实施。

在 repl.it 上查看运行。

对于以下迷宫：

[
    [1,1,2,0,0],
    [3,1,0,1,3],
    [1,0,2,0,2]
]

...并从 lower-left 角开始，以 top-right 角为目标，它给出了这条 (x, y) 坐标路径（x = 列，y = 行）：

[(0, 2), (0, 1), (3, 1), (4, 1), (1, 1), (1, 0), (2, 0), (4, 0)]

似乎无法为无墙迷宫创建递归算法

Can't seem to create recursive algorithm for wallless maze

python

recursion

maze