递归函数的问题

问题描述 投票：0回答：1

我最近挑战自己编写用于迷宫生成的深度优先搜索算法，并且即将完成它，但在项目最后一半的大部分时间里我一直在与一个特定的错误作斗争。

我使用二进制来表示树上两个相邻节点之间的连接（如果您还没有学习网络理论，它绝对很棒并且与编程非常相关），如下所示：0：无方向，1：左,2:右,4:上,8:下,以及任何这些加在一起产生它们的方向,即:3:左-右,12:上-下,7:左-右-上...

以下函数是主要函数，理论上适用于任何大小的 2d 列表（不考虑 Python 因为太多迭代而将我切断>：^<).

def DepthFirstSearch(map,inX,inY,priorPoses,iteration,seed,mapSize):
    if len(priorPoses) == mapSize:
        print(F"Finished in {iteration} iterations")
        print(map)
        return map
    x = inX
    y = inY
    mapHold = map
    history = priorPoses
    random.seed(seed + iteration)
    if CheckNeighbors(map, x, y) == []:
        CheckPriorPositions(map,priorPoses)
        print(F"Check prior positions, {CheckNeighbors(map,x,y)}")
        return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
                         priorPoses,iteration+1,seed,mapSize)
    else:
        move = CheckNeighbors(map, x, y)
        move = random.choice(move)
        if move == 1:
            mapHold[inY][inX] += move
            x -= 1
            mapHold[y][x] += 2
        else:
            if move == 2:
                mapHold[inY][inX] += move
                x += 1
                mapHold[y][x] += 1
            else:
                if move == 4:
                    mapHold[inY][inX] += move
                    y += 1
                    mapHold[y][x] += 8
                else:
                    if move == 8:
                        mapHold[inY][inX] += move
                        y -= 1
                        mapHold[y][x] += 4
        history.append([x,y])
        return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)



CheckNeighbors
函数工作得很好，但
CheckPriorPositions
函数一直令人担忧，但我找不到问题，但无论如何我都会包含它。如果您有任何提示，请提供提示，我有点觉得我错过了一些会完全忽略这个 
CheckPriorPositions
功能的东西。

def CheckPriorPositions(map,priorPoses):
    posesToSearch = priorPoses
    posesToSearch.reverse()
    for poses in range(0,len(posesToSearch)):
        if CheckNeighbors(map,posesToSearch[poses][0],posesToSearch[poses][1]) != []:
            return posesToSearch[poses]

我不断抛出的特定错误如下：

Traceback (most recent call last):
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 87, in <module>
    DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
    return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
    return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 71, in DepthFirstSearch
    return DepthFirstSearch(mapHold,x,y,priorPoses,iteration+1,seed,mapSize)
  File "C:\Users\Wyatt\Desktop\python prjects\DepthFirstSearchMazeGenProject\DepthFirstSearch.py", line 46, in DepthFirstSearch
    return DepthFirstSearch(mapHold,CheckPriorPositions(map,priorPoses)[0],CheckPriorPositions(map,priorPoses)[1],
TypeError: 'NoneType' object is not subscriptable

我真的不知道从哪里开始，但我确实有一些测试数据可以提供。

以下场景是真实场景的简化版本，旨在测试功能：

testMapA = [[0,0],[0,0],[0,0]]
testHistoryA = []
DepthFirstSearch(testMapA,0,0,testHistoryA,0,5,6)

testMapB = [[4,0],[10,5],[2,9]]
testHistoryB = [[0,0],[0,1],[1,1],[1,2],[0,2]]
DepthFirstSearch(testMapB,0,2,testHistoryB,5,5,6)

testMapC = [[4,0],[14,5],[8,8]]
testHistoryC = [[0,0],[0,1],[0,2],[1,1],[1,2]]
DepthFirstSearch(testMapC,1,2,testHistoryC,5,5,6)

testMapD = [[0,0],[0,0]]
testHistoryD = []
DepthFirstSearch(testMapD,0,0,testHistoryD,0,5,4)

testMapE = [[0,0]]
testHistoryE = []
DepthFirstSearch(testMapE,0,0,testHistoryE,0,5,2)
python algorithm recursion maze
1个回答
0
投票

有几个问题：

  • 通过深度优先遍历，回溯时不会重复更深。回溯涉及“摆脱”递归。这也意味着您不需要像 priorPoses 那样的显式堆栈，...等。调用堆栈就是用于此目的。

    

    • 由于上一点的原因，您不需要
  • CheckPriorPositions
    ，但这也是运行时错误的原因：当
    None
    条件永远不为真时，它可以返回
    if
    。并且您有代码尝试获取返回值的第一个索引，因此当它恰好是 
    None
     时会引发异常。
    

    • 您的代码表明您认为像
  • history = priorPoses
    这样的赋值会创建列表的
    副本
    。这不是真的。两个名称都将引用相同的列表，因此您使用 history 对该列表所做的更改将反映在您使用 
    priorPoses
     看到的内容中，反之亦然。例如，
    priorPoses.reverse()
    的叫声就是这样的突变。
    

    

    • 您还可以通过避免重复类似的代码来减少大部分代码。位配置允许使用位运算符，例如 
^
 来获得相反的方向。
没问题，但我不会使用以大写字母开头的函数名称。这通常用于类名。我更喜欢 Snake_case 作为函数名称：


import random

LEFT = 1
RIGHT = 2
UP = 4
DOWN = 8
SIDES = ((0, -1), (0, 1), (-1, 0), (1, 0))

def get_moves_to_nonvisited(visited, x, y):
    height = len(visited)
    width = len(visited[0])
    return [
        (side, y + dy, x + dx)
        for side, (dy, dx) in enumerate(SIDES)
        if 0 <= y + dy < height and 0 <= x + dx < width and not visited[y + dy][x + dx]
    ]

def depth_first_search(maze):
    row = [False] * len(maze[0])
    visited = [row[:] for _ in maze]

    def recur(y, x):
        visited[y][x] = True
        while True:
            moves = get_moves_to_nonvisited(visited, x, y)
            if not moves:
                return  # just backtrack!
            move, y2, x2 = random.choice(moves)
            maze[y][x] |= 1 << move  # Formula to convert 0,1,2,3 to 1,2,4,8
            maze[y2][x2] |= 1 << (move ^ 1) # Formula for opposite direction 
            recur(y2, x2)

    recur(0, 0)



我使用这个辅助函数来可视化迷宫：


def stringify(maze):
    row = [0] * (len(maze[0])*2+1)
    spots = [row[:] for _ in range(len(maze)*2+1)]
    for y, row in enumerate(maze):
        for x, cell in enumerate(row):
            if (cell & UP) == 0:
                spots[y*2][x*2  ] |= RIGHT
                spots[y*2][x*2+1] |= RIGHT | LEFT
                spots[y*2][x*2+2] |= LEFT
            if (cell & DOWN) == 0:
                spots[y*2+2][x*2  ] |= RIGHT
                spots[y*2+2][x*2+1] |= RIGHT | LEFT
                spots[y*2+2][x*2+2] |= LEFT
            if (cell & RIGHT) == 0:
                spots[y*2  ][x*2+2] |= DOWN
                spots[y*2+1][x*2+2] |= UP | DOWN
                spots[y*2+2][x*2+2] |= UP
            if (cell & LEFT) == 0:
                spots[y*2  ][x*2  ] |= DOWN
                spots[y*2+1][x*2  ] |= UP | DOWN
                spots[y*2+2][x*2  ] |= UP
    crosses = " ╴╶─╵┘└┴╷┐┌┬│┤├┼"
    return "\n".join(
        "".join(crosses[spot]  * (1 + (x % 2)*2) for x, spot in enumerate(row))
        for y, row in enumerate(spots)
    )



运行示例：


width = height = 8
maze = [[0] * width for _ in range(height)]
depth_first_search(maze)
print(stringify(maze))



...输出如下：


┌───────────┬───────────────────┐
│           │                   │
├───────┐   └───┐   ╷   ╶───┐   │
│       │       │   │       │   │
│   ╷   ├───┐   └───┴───┐   │   │
│   │   │   │           │   │   │
│   │   ╵   ├───────╴   │   └───┤
│   │       │           │       │
│   ├───╴   │   ┌───────┴───╴   │
│   │       │   │               │
│   └───────┤   └───┐   ╶───────┤
│           │       │           │
│   ╶───┐   └───┐   ├───────╴   │
│       │       │   │           │
├───╴   └───┐   ╵   ╵   ┌───╴   │
│           │           │       │
└───────────┴───────────┴───────┘


    
	

      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.