使用强化学习解决Leetcode问题
用强化学习解决Leetcode问题
实践介绍强化学习
最近，我在leetcode上遇到了一个问题：消除网格中的障碍的最短路径。消除网格中的障碍的最短路径问题涉及在包含障碍物的二维网格中从起始单元到目标单元的最短路径，其中允许您消除沿路径的最多k个障碍物。网格由“m x n”的二维数组表示，其中0表示空单元，1表示障碍单元。
目标是通过穿越空单元并消除最多k个障碍物，从起始单元(0, 0)到目标单元(m-1, n-1)找到最短路径。消除一个障碍物意味着将障碍单元(1)转换为空单元(0)，以便路径可以通过。
当我解决这个问题时，我意识到它可以为理解强化学习原理提供一个有用的框架。在我们深入探讨之前，让我们看看传统上如何解决这个问题。
为了理想地解决这个问题，我们需要从起始单元开始进行图搜索，同时跟踪到目前为止消除的障碍物数量。在每一步中，我们考虑移动到相邻的空单元或消除相邻的障碍单元（如果我们还有剩余的消除机会）。最短路径是达到目标单元的路径，步数最少，并且最多消除k个障碍物。我们可以使用广度优先搜索（BFS）和深度优先搜索（DFS）来高效地找到最优最短路径。
以下是使用BFS方法解决此问题的Python函数：
class Solution: def shortestPath(self, grid: List[List[int]], k: int) -> int: rows, cols = len(grid), len(grid[0]) target = (rows - 1, cols - 1) # 如果我们在最坏情况下有足够的配额来消除障碍物，则最短距离是曼哈顿距离 if k >= rows + cols - 2: return rows + cols - 2 # (行，列，剩余的消除障碍物配额) state = (0, 0, k) # (步数，状态) queue = deque([(0, state)]) seen = set([state]) while queue: steps, (row, col, k) = queue.popleft() # 我们到达目标单元 if (row, col) == target: return steps # 在下一步中探索四个方向 for new_row, new_col in [(row, col + 1), (row + 1, col), (row, col - 1), (row - 1, col)]: # 如果(new_row, new_col)在网格边界内 if (0 <= new_row < rows) and (0 <= new_col < cols): new_eliminations = k - grid[new_row][new_col] new_state = (new_row, new_col, new_eliminations) # 如果新状态符合条件，则将下一步添加到队列中 if new_eliminations >= 0 and new_state not in seen: seen.add(new_state) queue.append((steps + 1, new_state)) # 未到达目标 return -1强化学习简介
强化学习（RL）是机器学习的一个领域，其中代理通过奖励机制学习策略，通过学习其环境来完成任务。我一直对强化学习很着迷，因为我相信这个框架密切反映了人类通过经验学习的方式。这个想法是构建一个可学习的代理，通过试错来了解环境以解决问题。
我们逐个解释这些术语：
- 代理：代理是一个控制行动过程的假设实体。你可以想象一个假设的机器人，比如代理雷亚（Agent Raya），它从一个位置开始并探索其环境。例如，雷亚有两个可能的选择：位置（0，0）向右移动或位置（0，1）向下移动，而这些位置具有不同的奖励。
- 环境：环境是我们的代理操作的上下文，本例中是一个二维网格。
- 状态：状态表示玩家的当前情况。在我们的例子中，它给出了玩家当前的位置和剩余违规次数。
- 奖励系统：奖励是由于采取某种行动而获得的得分。在这种情况下：空单元格扣除1分，到达目的地加20分，如果违规次数k用完则扣除10分。
通过迭代过程，我们学习到了一个最优策略，使我们能够在每个时间步骤找到最佳的可能行动，并最大化总奖励。
为了能够找到最佳策略，我们使用了一个叫做Q函数的东西。你可以将这个函数看作是你的代理迄今为止所做的所有探索的存储库。然后，代理使用这些历史信息来做出更好的决策，以最大化奖励。
Q函数
Q(s, a)表示在状态s下采取行动a时，代理可以获得的预期累积奖励，遵循策略π。
其中
- π：代理采用的策略。
- s：当前状态。
- a：代理在状态s下采取的行动。
γ是平衡探索和利用的折扣因子。它决定代理在即时奖励与未来奖励之间给予多少优先级。接近0的因子使代理专注于短期奖励，而接近1的因子使代理专注于长期奖励。
代理需要平衡利用已知的高奖励行动与探索未知的可能带来更高奖励的行动。使用介于0和1之间的折扣因子有助于防止代理陷入局部最优策略。
现在让我们深入了解整个过程的代码。
这是我们定义代理和与之关联的变量的方式。
奖励函数：奖励函数接受当前状态并返回该状态的奖励。
贝尔曼方程：
我们应该如何更新Q表，以使其对每个位置和行动具有最佳可能的值？在任意数量的迭代中，代理从位置（0，0，k）开始，其中k表示允许的违规次数。在每个时间步骤中，代理通过随机探索或利用学习到的Q值进行贪婪移动，转移到一个新的状态。
到达新状态后，我们评估即时奖励，并根据贝尔曼方程更新该状态-行动对的Q值。这样，我们可以通过将新奖励纳入每个状态-行动的历史累积奖励中，逐步改进Q函数。
这是贝尔曼方程的方程：
这是训练过程在代码中的样子：
构建路径：对于路径，我们利用每个格子位置的最大Q值来确定在该位置采取的最优动作。Q值基本上根据长期奖励编码了在每个位置采取的最佳动作。例如，在位置（0,0）上的所有动作k中，最大Q值对应于动作“1”，表示向右移动。通过在每一步中贪婪地选择具有最高Q值的动作，我们可以构建出一个通过网格的最优路径。
如果您运行提供的代码，您会发现它生成了路径RBRBBB，这确实是考虑到障碍物的最短路径之一。
这里是整个代码的链接：shortest_path_rl.py
结论
在现实世界的强化学习场景中，代理与环境的交互可能是庞大的，只有稀疏的奖励。如果通过更改0和1的配置来改变板的配置，这种硬编码的Q表方法将无法泛化。我们的目标是训练一个代理程序，它可以学习网格世界配置的通用表示，并且可以在新的布局中找到最优路径。在下一篇文章中，我将用深度Q网络（DQN）替换硬编码的Q表值。DQN是一个神经网络，它以状态-动作组合和完整的网格布局作为输入，并输出一个Q值估计。这个DQN应该能够让代理程序在训练期间未曾遇到的新网格布局中找到最优路径。
如果您想进行快速聊天并建立联系，请在LinkedIn上与我联系：https://www.linkedin.com/in/pratikdaher/
