Python Lee算法

在本教程中，我们将学习Lee算法，该算法用于解决迷宫路由问题。我们将使用Python编程语言来实现此算法。迷宫路由问题是最有趣且最常提出的编程问题之一。基于广度优先搜索算法，Lee算法是解决迷宫问题的一种方法之一。现在，让我们理解问题陈述。

问题陈述

在此问题中，给定一个二进制矩形状的迷宫，并且我们需要找到从给定源单元格到目标单元格的最短路径。迷宫表示为MxN矩阵，其中每个元素可以是0或1。只有值为1的单元格才能创建路径。在任何给定时间，我们只能沿四个方向之一前进一个步长。有效的步骤如下：

向上移动：（x，y）->（x-1，y）

向左移动：（x，y）->（x，y-1）

向下移动：（x，y）->（x + 1，y）

向右移动：（x，y）->（x，y + 1）

让我们更好地解释一下，以便我们可以轻松理解。假设矩阵如下所示 –

输入 –

matrix =
[1 0 1 1 1
1 0 1 0 1
1 1 1 0 1
 0 0 0 0 1
1 1 1 0 1 ]
Source cell = {0, 0}
Destination cell = {2, 1}

输出：

最短路径的长度为3

解决方案方法

为了解决这样的问题，我们将使用基于广度优先搜索（BFS）过程的Lee算法。我们将使用队列和矩阵来识别已访问的单元格，并重复此过程，直到我们找到从源单元格到目标单元格的最短路径。

BFS是查找最短路径的最佳技术之一，因为它不是一次考虑单个路径，而是同时考虑从源开始的所有路径，并沿着这些路径中的所有路径一次走一步。让我们理解算法。

算法

首先，我们创建一个空队列，并使用距离源本身0的矩阵坐标存储（源单元格）。将其标记为已访问。
对源单元格调用BFS过程。
初始化与输入矩阵大小相同的布尔数组，并将所有值设置为false。
运行循环，直到队列为空。
从队列中取消队列前面的单元格。如果到达目标单元格，则返回。否则，对于当前单元格的所有四个相邻单元格中的每个单元格，如果单元格值为1且它们未被访问，则将单元格加入队列并标记为已访问。
如果在处理所有队列节点后未到达目标，则返回False。

伪代码

让我们理解Lee算法的伪代码。

初始化移动数组=>

rowNum：= [-1,0,0,1]，colNum：= [0，-1，1，0]

LeeAlgo（mat，src，dest）

如果mat [src.x] [src.y]！= 1或mat [dest.x] [dest.y]！= 1，则
   返回-1

初始化矩阵：visited [Row] [Col]：= False
visited [src.x] [src.y]：= True
初始化空队列：q：= Queue()

q.add（src）

while q is not Empointy，loop

   curr：= q.Pop（）

   point：= curr.coordinates

   如果point.x = dest.x并且point.y = dest.y，则
         返回curr.distance

   for i in 0 to 4
      row：= point.x + rowNum [i]
      col：= point.y + colNum [i]
      if mat（row，col）有效且mat（row，cell）= 1且mat（row，cell）未被访问，则
         visited [row] [col]：= True
         q.add(current_Adjacent_Cell)

return -1

解释 –

在上面的伪代码中，我们首先创建两个数组rowNums和colNum，用于通过将这些数组的值添加到当前单元格坐标来访问当前单元格的所有四个相邻单元格。
* LeeAlgo()方法检查给定的起始和结束单元格是否有效，即它们的值为1。如果源或目标无效或路径无法形成，则返回-1。
* 如果起点和终点合适，我们将所有值设置为False的访问矩阵进行初始化。我们还初始化了一个空队列(q)，然后将源单元格添加到此队列中并将其标记为已访问。
* 在此之后，我们运行循环，直到队列为空，并通过弹出它并处理它来检查每个节点。当前单元格的坐标存储在指针中，然后我们检查坐标是否等于目标单元格，并返回到该指针的距离。如果没有到达目标，则使用rowNum和colNum数组检查所有相邻单元格，并将它们添加到我们的队列中，如果可以通过它们获得路径且它们尚未被访问，则应用BFS模式，通过检查当前单元格的所有可能路径。
* 如上所述的循环重复迭代，直到达到目的地或队列为空为止。如果在访问目标单元格之前队列变空，则从源单元格无法到达目标单元格，此时返回-1。

现在将上述伪代码实现为Python代码。

Python代码

from collections import deque
ROW = 5
COL = 5

# 存储单元格坐标
class Cell:
    def __init__(self,x: int, y: int):
        self.x = x
        self.y = y

# 声明队列进行BFS
class queueNode:
    def __init__(self,point: Cell, dist: int):
        self.point = point # 单元格坐标
        self.dist = dist # 单元格到源的距离

# 检查给定的单元格 (row, col) 是否为有效单元格
def check_valid(row: int, col: int):
    return ((row >= 0) and (row < ROW) and (col >= 0) and (col < COL))

# 这些数组显示来自单元格的四个可能的移动
rowNum = [-1, 0, 0, 1]
colNum = [0, -1, 1, 0]

# 查找源单元格和目标单元格之间的最短路径的函数。
def LeeAlgo(mat, src: Cell, dest: Cell):

    # 检查源和目的地单元格是否有值为 1
    if mat[src.x][src.y]!=1 or mat[dest.x][dest.y]!=1:
        return -1

    visited = [[False for i in range(COL)]
                    for j in range(ROW)]

    # 将源单元格标记为已访问
    visited[src.x][src.y] = True

    # 创建BFS队列
    q = deque()

    # 源单元格的距离为 0
    s = queueNode(src,0)
    q.append(s) # 加入源单元格

    # 从源单元格开始执行BFS
    while q:

        curr = q.popleft() # 从队列首部出队

        # 如果达到了目的地单元格，返回最终距离
        point = curr.point
        if point.x == dest.x and point.y == dest.y:
            return curr.dist

        # 否则，将其相邻单元格（值为1且未访问）加入队列
        for i in range(4):
            row = point.x + rowNum[i]
            col = point.y + colNum[i]

            if (check_valid(row,col) and
            mat[row][col] == 1 and
                not visited[row][col]):
                visited[row][col] = True
                Adjcell = queueNode(Cell(row,col),
                                    curr.dist+1)
                q.append(Adjcell)

    # 如果无法到达目标单元格，则返回 -1
    return -1

mat = [ [ 1, 0, 1, 1, 1 ],
    [ 1, 0, 1, 0, 1 ],
    [ 1, 1, 1, 0, 1 ],
    [ 0, 0, 0, 0, 1 ],
    [ 1, 1, 1, 0, 1 ]]
source = Cell(0,0)
dest = Cell(2,1)

dist = LeeAlgo(mat,source,dest)

if dist!=-1:
        print("最短路径的长度为：",dist)
else:
        print("不存在最短路径")

输出：

最短路径的长度为：3

说明 –

在代码中，我们从“collections”模块导入了“deque”和“namedtuple”类。

开头定义了“ROW”和“COL”变量，并用于设置迷宫的尺寸。使用“namedtuple”类创建了两个自定义类，“Cell”和“Node”，分别存储关于迷宫中单元格的坐标和距离源的信息。
“LeeAlgo”函数接受三个参数：表示迷宫的二维矩阵、”src”单元格和”dest”单元格。函数首先检查源单元格和目标单元格是否有效（即矩阵中是否设置为1）。如果无效，则函数返回-1。

然后，函数初始化了一个名为”visited”的二维布尔数组，它用于跟踪迷宫中的哪些单元格已被访问。源单元格被标记为已访问。

创建了一个双向队列并将源单元格添加到其中，距离为0。然后，一个while循环通过广度优先搜索（BFS）遍历迷宫。循环会一直执行，直到队列为空。

对于每次迭代，函数检查当前单元格是否为目标单元格。如果是，则返回源与目标之间的距离。否则，函数查看所有相邻的单元格（上、下、左、右），如果该单元格有效（即在矩阵中设置为1且尚未访问），则将其添加到队列中并标记为已访问。

最后，如果未找到源到目标的路径，则函数返回-1。

在代码的结尾，创建了一个矩阵来表示迷宫，并定义了源和目标坐标。将这些输入作为参数调用”LeeAlgo”函数，并将源到目标的距离打印出来。