使用 BFS 的网格中的最短路径
Shortest path in a grid using BFS
网格由以下项目组成 python 列表列表
g = [
['1', '1', '1', '1', '1'],
['S', '1', 'X', '1', '1'],
['1', '1', '1', '1', '1'],
['X', '1', '1', 'E', '1'],
['1', '1', '1', '1', 'X']
]
S表示开始,E表示结束
1表示允许的路径,X是不允许的路径
一个简单的BFS遍历代码是
def find_path_bfs(s, e, grid):
queue = list()
path = list()
queue.append(s)
while len(queue) > 0:
node = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
break
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if is_visited(item, v) is False:
queue.append(item)
return path
据我所知,该算法正确地遍历了以下输出
[(1, 0), (1, 1), (2, 0), (0, 0), (2, 1), (0, 1), (2, 1), (0, 1), (2, 2), (3, 1), (0, 2), (2, 2), (3, 1), (0, 2), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 4), (3, 3)]
列表中的每个元组代表原始图中节点的索引。
如何将我的 BFS 代码重写为 return 最短路径而不是到达目标节点所遵循的整个遍历路径? 我花了几个小时来寻找答案靠我自己,但到目前为止我还没有成功。
为了获得最短路径,您也应该在队列中保存到当前节点的路径,因此队列项的格式为:
(node, path_to_this_node)
修改后的代码:
def find_path_bfs(s, e, grid):
queue = [(s, [])] # start point, empty path
while len(queue) > 0:
node, path = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
return path
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if not is_visited(item, v):
queue.append((item, path[:]))
return None # no path found
网格由以下项目组成 python 列表列表
g = [
['1', '1', '1', '1', '1'],
['S', '1', 'X', '1', '1'],
['1', '1', '1', '1', '1'],
['X', '1', '1', 'E', '1'],
['1', '1', '1', '1', 'X']
]
S表示开始,E表示结束
1表示允许的路径,X是不允许的路径
一个简单的BFS遍历代码是
def find_path_bfs(s, e, grid):
queue = list()
path = list()
queue.append(s)
while len(queue) > 0:
node = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
break
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if is_visited(item, v) is False:
queue.append(item)
return path
据我所知,该算法正确地遍历了以下输出
[(1, 0), (1, 1), (2, 0), (0, 0), (2, 1), (0, 1), (2, 1), (0, 1), (2, 2), (3, 1), (0, 2), (2, 2), (3, 1), (0, 2), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 3), (3, 2), (3, 2), (4, 1), (0, 3), (2, 4), (3, 3)]
列表中的每个元组代表原始图中节点的索引。
如何将我的 BFS 代码重写为 return 最短路径而不是到达目标节点所遵循的整个遍历路径? 我花了几个小时来寻找答案靠我自己,但到目前为止我还没有成功。
为了获得最短路径,您也应该在队列中保存到当前节点的路径,因此队列项的格式为:
(node, path_to_this_node)
修改后的代码:
def find_path_bfs(s, e, grid):
queue = [(s, [])] # start point, empty path
while len(queue) > 0:
node, path = queue.pop(0)
path.append(node)
mark_visited(node, v)
if node == e:
return path
adj_nodes = get_neighbors(node, grid)
for item in adj_nodes:
if not is_visited(item, v):
queue.append((item, path[:]))
return None # no path found