删除几条边是否会删除到节点的所有路径？
Does the removal of a few edges remove all paths to a node?
我正在为一个名为 Blockade 的棋盘游戏制作游戏引擎，现在我正在尝试生成一个位置的所有合法移动。规则与实际游戏并不完全相同，它们并不重要。要点是：棋盘是一个矩阵，你每次移动一个棋子并放置一堵墙。
简而言之，我必须找到在每次可能的合法移动后是否存在从每个棋子到每个目标的有效路径（假设一个棋子不动， wall 刚刚放置），以排除非法移动。或者更确切地说，如果我将它简化为一个子问题，是否移除一些边（放置一堵墙）是否会移除到节点的所有路径。
暴力破解需要 O(k*n*m)，其中 n 和 m 是棋盘尺寸，k 是潜在的合法移动数。搜索路径（最坏的情况；遍历大部分板）非常昂贵，但我正在考虑使用动态编程或其他一些 idea/algorithm 它可以更快地完成，因为位置相同，墙的位置只是改变，或者更确切地说，在图形方面，图形是相同的，删除的边只是改变了。欢迎任何形式的优化。
编辑：
细说墙（封锁）。一面墙是两个正方形wide/tall（取决于它是水平的还是垂直的）因此它通常会移除至少四个边，例如：
p |
问 | t
在这个 2x2 矩阵中，在中间放置一堵墙（如图所示）将消除跳转：
p 和 t，q 和 r，p 和 r，以及 q 和 t
几点建议：
检查A到B之后是否有路径
每一步都会从 graph/grid 中删除一个节点。所以我们想知道的是从 A 到 B 的路径上是否有关键节点（单点可以被阻止以破坏路径。这是一个经典的 flow problem。对于这个应用程序，您要设置顶点capacity 为 1 并推送 2 个单位的流量（基本上只是为了验证至少有 2 条路径）。如果有 2 条路径，则没有一个块可以使您与目的地断开连接。您可以使用隐式图对其进行一些优化，但如果您是新手，可以创建图形以更好地可视化它。这应该是 O(N*M)，即网格的大小。
优化
由于这是一款游戏，您知道设置不会从一步到另一步发生显着变化。因此，您可以跟踪这两条路径。如果 blocade 没有放置在任何路径上，您可以忽略它。您已经有 2 条到达目的地的路径。
如果块确实落在其中一条路径上，则仅取消该路径，然后寻找另一条路径（重复使用您已有的路径）。
你还可以加快棋子的移动速度。这可能有点技巧，但你想要的是移动源。我假设 pawn 一次只移动几个单元格，也许您可以简单地调整它们以连接到新位置，而不是寻找全新的路径，从而加快更新速度。
如果我没有完全理解您提出的问题，我提前表示歉意；您在问题中似乎暗示了一些关于封锁游戏如何运作的知识（我完全不熟悉。）
但是，根据对维基百科游戏规则的快速浏览，以及我从你的问题中收集到的信息，我的理解是你实际上是在问如何确保一步棋 合法。根据我的理解，非法移动是 wall/blockade 放置，这将使任何棋子都无法达到其目标状态。
在这种情况下，我认为相当有效的可行解决方案如下。
将pawn的路径树定义为从pawn到每个可达位置的（可能但不一定是最短的）路径树。这个想法是，您希望为每个 pawn 维护一个路径树，以便它可以在每次封锁放置时有效地更新。上一句中描述的内容可以通过观察和执行以下内容来完成：
- 放置封锁后，它会从图中删除 2 条边，这最多（最多）切断所有现有路径树中的两条边
- 在使用 Boykov-Komolgrov maxflow 算法的“采用”算法切断边后，可以有效地重新计算每个 pawn 的路径树。
- 一旦每个 pawns 路径树都被有效地重新计算，只需检查每个 pawn 是否仍然可以访问其目标状态，如果不能则将移动标记为非法
- 对每个可能的移动重复（在搜索过程中根据需要重置图表）
以下是关于采用算法的资源，这些资源对于有效执行所描述的事情至关重要：
- 作为 BK-maxflow 一部分的开源实现：https://www.boost.org/doc/libs/1_66_0/libs/graph/doc/boykov_kolmogorov_max_flow.html
- 作者作为 BK-maxflow 的一部分实施：https://pub.ist.ac.at/~vnk/software.html
- BK maxflow算法采用（阶段）算法详解：https://www.csd.uwo.ca/~yboykov/Papers/pami04.pdf
第3.2.3节
注意阅读上一节收养算法的说明
上面的要点对于理解如何采用最为关键
有效地分离了路径树的孤立部分。
就此方法的效率而言，我相信平均而言，您应该期望对每个采用的边缘进行平均 O(1) 次操作，这意味着此方法应该花费大约 O(k) 时间来计算 k 是您希望计算的棋盘状态数。
请注意，典当路径树实际上应该是以目标节点为根的反向定向树，这将允许在给定封锁配置的情况下对所有合法典当放置进行计算。
我正在为一个名为 Blockade 的棋盘游戏制作游戏引擎，现在我正在尝试生成一个位置的所有合法移动。规则与实际游戏并不完全相同，它们并不重要。要点是：棋盘是一个矩阵，你每次移动一个棋子并放置一堵墙。
简而言之，我必须找到在每次可能的合法移动后是否存在从每个棋子到每个目标的有效路径（假设一个棋子不动， wall 刚刚放置），以排除非法移动。或者更确切地说，如果我将它简化为一个子问题，是否移除一些边（放置一堵墙）是否会移除到节点的所有路径。
暴力破解需要 O(k*n*m)，其中 n 和 m 是棋盘尺寸，k 是潜在的合法移动数。搜索路径（最坏的情况；遍历大部分板）非常昂贵，但我正在考虑使用动态编程或其他一些 idea/algorithm 它可以更快地完成，因为位置相同，墙的位置只是改变，或者更确切地说，在图形方面，图形是相同的，删除的边只是改变了。欢迎任何形式的优化。
编辑：
细说墙（封锁）。一面墙是两个正方形wide/tall（取决于它是水平的还是垂直的）因此它通常会移除至少四个边，例如：
p |
问 | t
在这个 2x2 矩阵中，在中间放置一堵墙（如图所示）将消除跳转：
p 和 t，q 和 r，p 和 r，以及 q 和 t
几点建议：
检查A到B之后是否有路径
每一步都会从 graph/grid 中删除一个节点。所以我们想知道的是从 A 到 B 的路径上是否有关键节点（单点可以被阻止以破坏路径。这是一个经典的 flow problem。对于这个应用程序，您要设置顶点capacity 为 1 并推送 2 个单位的流量（基本上只是为了验证至少有 2 条路径）。如果有 2 条路径，则没有一个块可以使您与目的地断开连接。您可以使用隐式图对其进行一些优化，但如果您是新手，可以创建图形以更好地可视化它。这应该是 O(N*M)，即网格的大小。
优化
由于这是一款游戏，您知道设置不会从一步到另一步发生显着变化。因此，您可以跟踪这两条路径。如果 blocade 没有放置在任何路径上，您可以忽略它。您已经有 2 条到达目的地的路径。
如果块确实落在其中一条路径上，则仅取消该路径，然后寻找另一条路径（重复使用您已有的路径）。
你还可以加快棋子的移动速度。这可能有点技巧，但你想要的是移动源。我假设 pawn 一次只移动几个单元格，也许您可以简单地调整它们以连接到新位置，而不是寻找全新的路径，从而加快更新速度。
如果我没有完全理解您提出的问题，我提前表示歉意；您在问题中似乎暗示了一些关于封锁游戏如何运作的知识（我完全不熟悉。）
但是，根据对维基百科游戏规则的快速浏览，以及我从你的问题中收集到的信息，我的理解是你实际上是在问如何确保一步棋 合法。根据我的理解，非法移动是 wall/blockade 放置，这将使任何棋子都无法达到其目标状态。
在这种情况下，我认为相当有效的可行解决方案如下。
将pawn的路径树定义为从pawn到每个可达位置的（可能但不一定是最短的）路径树。这个想法是，您希望为每个 pawn 维护一个路径树，以便它可以在每次封锁放置时有效地更新。上一句中描述的内容可以通过观察和执行以下内容来完成：
- 放置封锁后，它会从图中删除 2 条边，这最多（最多）切断所有现有路径树中的两条边
- 在使用 Boykov-Komolgrov maxflow 算法的“采用”算法切断边后，可以有效地重新计算每个 pawn 的路径树。
- 一旦每个 pawns 路径树都被有效地重新计算，只需检查每个 pawn 是否仍然可以访问其目标状态，如果不能则将移动标记为非法
- 对每个可能的移动重复（在搜索过程中根据需要重置图表）
以下是关于采用算法的资源，这些资源对于有效执行所描述的事情至关重要：
- 作为 BK-maxflow 一部分的开源实现：https://www.boost.org/doc/libs/1_66_0/libs/graph/doc/boykov_kolmogorov_max_flow.html
- 作者作为 BK-maxflow 的一部分实施：https://pub.ist.ac.at/~vnk/software.html
- BK maxflow算法采用（阶段）算法详解：https://www.csd.uwo.ca/~yboykov/Papers/pami04.pdf 第3.2.3节
注意阅读上一节收养算法的说明 上面的要点对于理解如何采用最为关键 有效地分离了路径树的孤立部分。
就此方法的效率而言，我相信平均而言，您应该期望对每个采用的边缘进行平均 O(1) 次操作，这意味着此方法应该花费大约 O(k) 时间来计算 k 是您希望计算的棋盘状态数。
请注意，典当路径树实际上应该是以目标节点为根的反向定向树，这将允许在给定封锁配置的情况下对所有合法典当放置进行计算。