在BFS中,曼哈顿距离通常被用作估计从当前节点到目标节点的距离。这是因为曼哈顿距离内对角线的移动是不允许的,当搜索算法使用曼哈顿距离时,移动方式被限制到了四个方向上。
下面是一个使用BFS和曼哈顿距离来搜索迷宫的Python示例代码:
from queue import Queue
def bfs(maze, start, end):
q = Queue()
visited = set()
q.put((start, 0))
visited.add(start)
while not q.empty():
current, dist = q.get()
if current == end:
return dist
x, y = current
for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
newx, newy = x + dx, y + dy
if 0 <= newx < len(maze) and 0 <= newy < len(maze[0]) and (newx, newy) not in visited and maze[newx][newy] == 0:
q.put(((newx, newy), dist + 1 + abs(newx - end[0]) + abs(newy - end[1])))
visited.add((newx, newy))
return -1
maze = [
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0]
]
print(bfs(maze, (0, 0), (4, 3)))
在上述示例中,maze
数组表示了一个迷宫,0表示可通行的路径,1表示墙壁。start
和end
分别表示了B
下一篇:BFS五个字母单词链