了解 python 广度优先搜索算法

Question

我正在尝试理解这个广度优先搜索 python 实现，我理解我的评论中显示的大部分内容，但我在这里没有得到这一行：

for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
           a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

           if maze.in_maze(a, b) and not maze.is_wall(a, b) and (a, b) not in parent: #Check to see if the coordinates that are searching is inside the wall is not a wall and not inside of parent
               parent[(a, b)] = current #?
               dist[(a, b)] = dist[current] + 1; #?
               queue.append((a, b)) #Add the coordinates to the end of the queue

完整的代码可以在这里找到，如有任何评论错误，请随时给我打电话。我对 python 还是个新手，所以我不知道每一行的确切含义，但我有一个大概的想法。

from collections import deque #A double-ended queue, or deque, supports adding and removing elements from either end. Import this from collections

nodes = 0 #Initialise nodes with value 0


def solve(maze, start, end): #Solve function that takes in the maze, start and end points as arguments
   global nodes #Declare nodes as a global variable
   nodes = 0 #Set nodes value to 0

   queue = deque() #Set queue as a double ended queue
   parent, dist = dict(), dict() #Set parent and dist

   queue.append(start) #Add start point to the queue
   parent[start], dist[start] = start, 1

   while len(queue): #While there are items in the list
       current = queue.popleft() #Set current to the first thing in the queue from the left
       nodes += 1 #Increment nodes by 1

       if current == end: #If the current place is the end target then solution has been found and we can exit the loop
           break #Exit the loop

       for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
           a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

           if maze.in_maze(a, b) and not maze.is_wall(a, b) and (a, b) not in parent: #Check to see if the coordinates that are searching is inside the wall is not a wall and not inside of parent
               parent[(a, b)] = current #Set later
               dist[(a, b)] = dist[current] + 1; #set later
               queue.append((a, b)) #Add the coordinates to the end of the queue

   if end not in parent: #If there is no solution
      return [] #Return an empty solution
   else: #Otherwise if there is a solution
      path = [] #Initialise path as an empty list
      while start != end: #While the starting point is not the end point, the solution has not be found so
          path.append(end) #Keep appending the end node to the path queue until they meet the condition
          end = parent[end] #Set end point to the position it is in the parent dictionary
      path.append(start) #Insert the starting point to the end of the queue
      path.reverse() #Reverse the path queue since the solution was found back to front
      return path #Return the final solution

Answer 1

parent[(a, b)] = current

用于存储位置的坐标(current)，您从到达坐标(a, b)。哦，顺便说一句，这里的评论是错误的：

   for dx, dy in [(-1, 0), (0, +1), (+1, 0), (0, -1)]:
       a, b = current[0] + dx, current[1] + dy #Start searching in a random direction

应该是"Search in every direction, one at a time"。这里没有什么随机的。

Answer 2

所以，在上面的代码中，阅读后，我假设开始和结束由 (x, y) 这样的坐标表示。另外，如果你select"maze"中的任何坐标，你只能向上、下、左、右方向移动，即如果你在坐标（x，y）上，你只能去一个以下坐标： (x+1, y), (x-1, y), (x, y+1), (x, y-1)

所以基本上，for循环用于select你可以遍历的相邻坐标，一个接一个。那么a, b = current[0] + dx, current[1] + dy这一行就是用来获取相邻坐标的绝对坐标。然后我们检查新坐标是否存在于迷宫中或者它是否是一堵墙。如果它在迷宫中而不是墙中，而且我们还没有穿过它，我们更新 parent 字典并更新 dist 字典（距离）。

parent dict 存储坐标的父级。因此，对于 (x+1, y)，父级将是 (x, y)，这是当前的。 parent[(x+1, y)] = (x, y) 表示 (x+1, y) 的父级是 (x, y)

dist 字典存储到达新坐标所需的步数或步数。 dist[(x+1, y)] = dist[(x,y)] + 1 也就是说，新坐标的距离等于父坐标的距离 + 1 个新步长。

然后我们将它添加到队列中。

了解 python 广度优先搜索算法

Understanding a python breadth-first-search algorithm

python

algorithm

breadth-first-search