我目前正在进行一个人工智能项目，其中一个智能体需要将箱子从其原始位置推拉到某个目标位置。该项目随后将扩展到包括多个智能体，因此我们有一个监督者负责创建“高级”目标，而智能体则负责实际的实现。

在实践中，目前监督者应该决定将箱子放置到目标位置的顺序。实际上，将一个箱子放置到其目标位置可能会阻塞通往另一个目标的路径。

我们解决这个问题的第一种方法是尝试考虑“切割位置”。如果某个位置将可行走空间分成两个子集，其中一个子集中有智能体，另一个子集中有一个或多个目标，那么这个位置就是一个切割位置。例如，考虑以下关卡，其中“x”是智能体，“A”和“B”是箱子，“a”和“b”是各自的目标位置：

+++++++++++++++++++++++++++++++++++++++++x                        a             b++++++   +++++++++++++++++++++++++++++++++    +AB +    +++++ 

在这种情况下，目标“a”的位置是一个切割位置，因为如果在那里放置一个箱子，智能体将无法到达目标“b”。

你能建议一个快速计算切割位置的算法，并且可能返回每个切割位置阻塞的目标数量吗？

回答：

你所说的网格世界的切割位置，在一般图中被称为切割顶点或关节点。根据维基百科的说法：

具体来说，切割顶点是指移除该顶点会增加连通分量数量的顶点。

在同一文章的稍后部分：

John Hopcroft 和 Robert Tarjan（1973年）提出的计算连通分量的经典顺序算法[1]在连通的无向图中运行时间为线性，基于深度优先搜索。这个算法也在《算法导论》（第二版和第三版）中作为问题22-2进行了概述。

确定了双连通分量后，确定关节点应该相当容易：所有包含在多个双连通分量中的节点都是关节点。