algorithm - 如何在网格中找到所有可能的唯一路径？

Question

我有一个 3 x 3 的网格，其中随机放置障碍物，其中有一个随机起点但没有终点。当没有更多的单元格可供占用时，将创建端点。可以向上、向下、向左或向右移动。

如何查看网格中所有可能的唯一路径？

例子:

• 一旦在查找路径时使用了一个单元格，就不能再次使用它(1 变为 0)。
• 如果没有更多的相邻单元移动到路径结束。无论天气如何，所有细胞都已被访问过。

# bottom left is (0, 0) and top right is (2, 2)...
# start is (1, 1) and obstacle is (2, 1)
    
[1] [1] [1]
[1] [S] [0]
[1] [1] [1]
    
S = starting point
0 = obstacle
1 = open cell

在上面的示例中，将有 6 条不同的路径。

path_1 = (1, 2), (2, 2) # up, right
path_2 = (1, 0), (2, 0) # down, right
path_3 = (0, 1), (0, 2), (1, 2), (2, 2) # left, up, right, right
path_4 = (0, 1), (0, 0), (1, 0), (2, 0) # left, down, right, right
path_5 = (1, 2), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0) # up, left, down, down, right, right
path_6 = (1, 0), (0, 0), (0, 1), (0, 2) (1, 2), (2, 2) # down, left, up, up, right, right

Answer 1

要获取所有路径，您可以使用 DFS 或 BFS，但每个路径都需要具有唯一的 visited设置为跟踪您:

1. 不要在一条路径中两次返回到同一坐标
2. 允许不同的路径在同一个坐标上走

我为网格编写了 DFS 实现 here解决方案将依赖于此示例。

解决方案

要进行图搜索，需要定义状态，在本例中为坐标，但对于这个问题，为了方便起见，我们将跟踪两个参数:

1. 所采取的路径将通过破解代码(右=0，下=1，左=2，上=3)记录，这是chain code的一种形式。
2. visited出于上述原因，将为每个路径设置的文件将被取消记录

Python 中的实现如下(在我的例子中，对于 nXn 网格，左上角匹配坐标 (0,0)，右下角匹配 (n-1,n-1))

import collections
def find_paths(grid, start_coord):
    paths       = set()  # paths will be added here
    state_queue = collections.deque([]) # Pending states which have not been explored yet
    # State is a tuple consists of:
    # 1. current coordinate
    # 2. crack code path
    # 3. set of visited coordinates in that path
    state       = [start_coord, [], {start_coord}]  # Starting state
    while True:
        # Getting all possible neighboring states
        # Crack code (right=0, down=1, left=2, up=3)
        state_right = [(state[0][0],state[0][1]+1), state[1] + [0], state[2].copy()] if state[0][1]+1 < len(grid[state[0][0]]) else None
        state_down  = [(state[0][0]+1,state[0][1]), state[1] + [1], state[2].copy()] if state[0][0]+1 < len(grid) else None
        state_left  = [(state[0][0],state[0][1]-1), state[1] + [2], state[2].copy()] if state[0][1]-1 >= 0 else None
        state_up    = [(state[0][0]-1,state[0][1]), state[1] + [3], state[2].copy()] if state[0][0]-1 >= 0 else None
        # Adding to the queue all the unvisited states, as well as to the visited to avoid returning to states
        blocked_counter = 0
        for next_state in [state_right, state_down, state_left, state_up]:
            if next_state is None:
                blocked_counter += 1
            elif next_state[0] in state[2] or grid[next_state[0][0]][next_state[0][1]] == 0:
                blocked_counter += 1
            else:
                next_state[2].add(next_state[0])
                state_queue.append(next_state)
                
        # After checking all directions' if reached a 'dead end', adding this path to the path set
        if blocked_counter == 4:
            paths.add(tuple(state[1]))
        # Popping next state from the queue and updating the path if needed
        try:
            state = state_queue.pop()
        except IndexError:
            break
    return paths

解释

1. 一开始我们创建了初始状态，以及一个空列表的初始路径和visited。集合，仅包含起始坐标

2. 对于我们所处的每个状态，我们执行以下操作:2.1.创建四个相邻状态(向右、向上、向左或向下前进)

   2.2。通过检查我们所在的路径是否已经访问过该坐标以及该坐标是否有效来检查我们是否可以在每个方向上前进

   2.3。如果我们可以朝上述方向前进，请添加此 next_state到 state_queue以及 visited路径集合

   2.4。如果我们不能在四个方向中的任何一个方向上前进，我们就到达了“死胡同”，我们将我们所在的路径添加到 paths 中。设置

   2.5。从 state_queue 弹出下一个状态这是一个不好的名字，因为它是一个堆栈(由于从 deque() 的同一侧追加和弹出

3. 当 state_queue为空，我们完成搜索，我们可以返回所有找到的路径

当用给定的例子运行它时，即

start_coord = (1,1)
grid = [[1, 1, 1],
        [1, 1, 0],
        [1, 1, 1]]

我们得到:

find_paths(grid, start_coord)
# {(2, 3, 0, 0), (3, 2, 1, 1, 0, 0), (3, 0), (2, 1, 0, 0), (1, 0), (1, 2, 3, 3, 0, 0)}