如何在网格中找到所有可能的唯一路径？
How to find all possible unique paths in a grid?
我有一个 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
要获取所有路径，您可以使用 DFS 或 BFS，但每个路径都需要有一个唯一的 visited 设置以跟踪您：
- 不要在一条路径中两次返回同一坐标
- 允许不同的路径在同一个坐标上走
我为网格编写了 DFS 实现 ，解决方案将依赖于此示例。
解决方案
要进行图形搜索，需要定义状态，在本例中为坐标，但为了方便起见，对于这个问题，我们将跟踪两个参数：
- 所采取的路径将通过破解代码（右=0，下=1，左=2，上=3）记录，这是chain code
的一种形式
- 由于上述原因，将为每个路径设置的
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
说明
一开始我们创建初始状态，以及初始路径，它是一个空列表和 visited 集，仅包含起始坐标
对于我们所处的每个状态，我们执行以下操作：
2.1.创建四个相邻状态（向右、向上、向左或向下前进）
2.2。通过检查我们所在的路径是否已经访问过该坐标以及该坐标是否有效来检查我们是否可以在每个方向上前进
2.3。如果我们可以朝上述方向前进，请将此 next_state 添加到 state_queue 以及路径 visited 集
2.4。如果我们不能在四个方向中的任何一个方向前进，我们到达了 'dead end' 并且我们将我们所在的路径添加到 paths 集合
2.5。从 state_queue 弹出下一个状态，这是一个糟糕的名字，因为它是一个堆栈（由于从 deque()
的同一侧追加和弹出
当state_queue为空时，我们搜索完毕，可以return所有找到的路径
当运行这与给定的例子，即
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)}
我想用动态规划来解决这个问题，以避免指数时间复杂度，但没有成功。但是，这里是 Javascript 中的密集版本，它使用 DFS（考虑到这个问题与 brute-forcing 相同，因为我们对所有可能的路径都感兴趣）和具有 es6 功能的函数式递归。我们还使用 single-dimension 数组来表示棋盘，并使用 directions 方法说明从给定位置可以到达哪些位置。 single-dimension 数组包含从上到下按顺序排列的棋盘行。
[ 0 1 2 ]
[ 3 4 5 ] => [0, 1, 2, 3, 4, 5, 6, 7, 8]
[ 6 7 8 ]
该算法适用于任何 m by n 网格，因此我们必须将宽度指定为输入参数。
const directions = (pos, board, width) => {
const [n, s, w, e] = [pos - width, pos + width, pos - 1, pos + 1]
return [
n >= 0 && board[n] ? n : null,
s < board.length && board[s] ? s : null,
pos % width !== 0 && board[w] ? w : null,
e % width !== 0 && board[e] ? e : null
]
.filter(pos => pos !== null)
}
const solve = (pos, board, width, path) => {
const next = directions(pos, board, width)
return next.length === 0 ?
[[...path, pos]] // have a complete path
:
next
.map(nextPos => solve(nextPos, [...board.slice(0, pos), 0, ...board.slice(pos + 1)], width, [...path, pos]))
.flat()
}
const oneDim2TwoDim = (oneDimCoord, width) =>
[Math.floor(oneDimCoord / width), oneDimCoord % width]
const res = solve(4, [1, 1, 1, 1, 1, 0, 1, 1, 1], 3, [])
console.log(res.map(path => path.map(step => oneDim2TwoDim(step, 3))))
在每一步，我们检查哪些方向可以进入。如果没有可用的方向，我们return当前路径，否则我们在每个方向进行递归调用。
像这样使用
solve(4, [1, 1, 1, 1, 1, 0, 1, 1, 1], 3, [])
/*
[
[ 4, 1, 0, 3, 6, 7, 8],
[ 4, 1, 2 ],
[ 4, 7, 6, 3, 0, 1, 2],
[ 4, 7, 8 ],
[ 4, 3, 0, 1, 2 ],
[ 4, 3, 6, 7, 8 ]
]
*/
每条路径都从起始位置开始，您可以使用
轻松将其转换回(x, y)坐标样式
const oneDim2TwoDim = (oneDimCoord, width) =>
[Math.floor(oneDimCoord / width), oneDimCoord % width]
const res = solve(4, [1, 1, 1, 1, 1, 0, 1, 1, 1], 3, [])
.map(path => path.map(step => oneDim2TwoDim(step, 3)))
/*
[
[ [ 1, 1 ], [ 0, 1 ], [ 0, 0 ], [ 1, 0 ], [ 2, 0 ], [ 2, 1 ], [ 2, 2 ] ],
[ [ 1, 1 ], [ 0, 1 ], [ 0, 2 ] ],
[ [ 1, 1 ], [ 2, 1 ], [ 2, 0 ], [ 1, 0 ], [ 0, 0 ], [ 0, 1 ], [ 0, 2 ] ],
[ [ 1, 1 ], [ 2, 1 ], [ 2, 2 ] ],
[ [ 1, 1 ], [ 1, 0 ], [ 0, 0 ], [ 0, 1 ], [ 0, 2 ] ],
[ [ 1, 1 ], [ 1, 0 ], [ 2, 0 ], [ 2, 1 ], [ 2, 2 ] ]
]
*/
这其实并不像看起来那么难。因为在我看来你是在学习，所以我不会给你代码，而是专注于思路。
解决方案
因为你需要找到所有的解，所以这是一个经典的backtracking问题。回溯的思想是尝试每一种可能性并存储所有的解决方案。关于您的问题的特殊性：
- 网格
- 运动
- 障碍
- 独特的解决方案
如何检查所有内容？
您需要循环网格，对于每个点和每个点，从深度 0 开始，重复以下操作：
- if depth < available points map the possible moves (no obstacles, not visited) (1)
- 对于每个点：
- 深度增加 1
- 将当前点标记为已访问
- 检查是否有解决方案，有则处理
- 根据当前状态，跳转到(1)
- 取消标记当前点被访问
- 深度减少 1
处理解决方案
您的解决方案需要有一个独特的、可预测的签名，例如您按顺序移动到的点，并存储您目前拥有的所有解决方案。在您输入新的解决方案之前，请检查它是否已经在解决方案中，如果不存在则只添加它。
修剪
如果 problem-space 是 big-enough，您可以根据之前的发现删减您的发现，以实现性能优化，但您应该只在已经有了解决方案时才考虑这一点。
我有一个 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
要获取所有路径，您可以使用 DFS 或 BFS，但每个路径都需要有一个唯一的 visited 设置以跟踪您：
- 不要在一条路径中两次返回同一坐标
- 允许不同的路径在同一个坐标上走
我为网格编写了 DFS 实现
解决方案
要进行图形搜索，需要定义状态，在本例中为坐标，但为了方便起见，对于这个问题，我们将跟踪两个参数：
- 所采取的路径将通过破解代码（右=0，下=1，左=2，上=3）记录，这是chain code 的一种形式
- 由于上述原因，将为每个路径设置的
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
说明
一开始我们创建初始状态，以及初始路径，它是一个空列表和
visited集，仅包含起始坐标对于我们所处的每个状态，我们执行以下操作： 2.1.创建四个相邻状态（向右、向上、向左或向下前进）
2.2。通过检查我们所在的路径是否已经访问过该坐标以及该坐标是否有效来检查我们是否可以在每个方向上前进
2.3。如果我们可以朝上述方向前进，请将此
next_state添加到state_queue以及路径visited集2.4。如果我们不能在四个方向中的任何一个方向前进，我们到达了 'dead end' 并且我们将我们所在的路径添加到
paths集合2.5。从
的同一侧追加和弹出state_queue弹出下一个状态，这是一个糟糕的名字，因为它是一个堆栈（由于从deque()当
state_queue为空时，我们搜索完毕，可以return所有找到的路径
当运行这与给定的例子，即
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)}
我想用动态规划来解决这个问题，以避免指数时间复杂度，但没有成功。但是，这里是 Javascript 中的密集版本，它使用 DFS（考虑到这个问题与 brute-forcing 相同，因为我们对所有可能的路径都感兴趣）和具有 es6 功能的函数式递归。我们还使用 single-dimension 数组来表示棋盘，并使用 directions 方法说明从给定位置可以到达哪些位置。 single-dimension 数组包含从上到下按顺序排列的棋盘行。
[ 0 1 2 ]
[ 3 4 5 ] => [0, 1, 2, 3, 4, 5, 6, 7, 8]
[ 6 7 8 ]
该算法适用于任何 m by n 网格，因此我们必须将宽度指定为输入参数。
const directions = (pos, board, width) => {
const [n, s, w, e] = [pos - width, pos + width, pos - 1, pos + 1]
return [
n >= 0 && board[n] ? n : null,
s < board.length && board[s] ? s : null,
pos % width !== 0 && board[w] ? w : null,
e % width !== 0 && board[e] ? e : null
]
.filter(pos => pos !== null)
}
const solve = (pos, board, width, path) => {
const next = directions(pos, board, width)
return next.length === 0 ?
[[...path, pos]] // have a complete path
:
next
.map(nextPos => solve(nextPos, [...board.slice(0, pos), 0, ...board.slice(pos + 1)], width, [...path, pos]))
.flat()
}
const oneDim2TwoDim = (oneDimCoord, width) =>
[Math.floor(oneDimCoord / width), oneDimCoord % width]
const res = solve(4, [1, 1, 1, 1, 1, 0, 1, 1, 1], 3, [])
console.log(res.map(path => path.map(step => oneDim2TwoDim(step, 3))))
在每一步，我们检查哪些方向可以进入。如果没有可用的方向，我们return当前路径，否则我们在每个方向进行递归调用。
像这样使用
solve(4, [1, 1, 1, 1, 1, 0, 1, 1, 1], 3, [])
/*
[
[ 4, 1, 0, 3, 6, 7, 8],
[ 4, 1, 2 ],
[ 4, 7, 6, 3, 0, 1, 2],
[ 4, 7, 8 ],
[ 4, 3, 0, 1, 2 ],
[ 4, 3, 6, 7, 8 ]
]
*/
每条路径都从起始位置开始，您可以使用
轻松将其转换回(x, y)坐标样式
const oneDim2TwoDim = (oneDimCoord, width) =>
[Math.floor(oneDimCoord / width), oneDimCoord % width]
const res = solve(4, [1, 1, 1, 1, 1, 0, 1, 1, 1], 3, [])
.map(path => path.map(step => oneDim2TwoDim(step, 3)))
/*
[
[ [ 1, 1 ], [ 0, 1 ], [ 0, 0 ], [ 1, 0 ], [ 2, 0 ], [ 2, 1 ], [ 2, 2 ] ],
[ [ 1, 1 ], [ 0, 1 ], [ 0, 2 ] ],
[ [ 1, 1 ], [ 2, 1 ], [ 2, 0 ], [ 1, 0 ], [ 0, 0 ], [ 0, 1 ], [ 0, 2 ] ],
[ [ 1, 1 ], [ 2, 1 ], [ 2, 2 ] ],
[ [ 1, 1 ], [ 1, 0 ], [ 0, 0 ], [ 0, 1 ], [ 0, 2 ] ],
[ [ 1, 1 ], [ 1, 0 ], [ 2, 0 ], [ 2, 1 ], [ 2, 2 ] ]
]
*/
这其实并不像看起来那么难。因为在我看来你是在学习，所以我不会给你代码，而是专注于思路。
解决方案
因为你需要找到所有的解，所以这是一个经典的backtracking问题。回溯的思想是尝试每一种可能性并存储所有的解决方案。关于您的问题的特殊性：
- 网格
- 运动
- 障碍
- 独特的解决方案
如何检查所有内容？
您需要循环网格，对于每个点和每个点，从深度 0 开始，重复以下操作：
- if depth < available points map the possible moves (no obstacles, not visited) (1)
- 对于每个点：
- 深度增加 1
- 将当前点标记为已访问
- 检查是否有解决方案，有则处理
- 根据当前状态，跳转到(1)
- 取消标记当前点被访问
- 深度减少 1
处理解决方案
您的解决方案需要有一个独特的、可预测的签名，例如您按顺序移动到的点，并存储您目前拥有的所有解决方案。在您输入新的解决方案之前，请检查它是否已经在解决方案中，如果不存在则只添加它。
修剪
如果 problem-space 是 big-enough，您可以根据之前的发现删减您的发现，以实现性能优化，但您应该只在已经有了解决方案时才考虑这一点。