4

我目前正在从事一个人工智能项目，其中代理需要将盒子从其原始位置推拉到某个目标位置。然后，该项目将扩展为包括多个代理，因此我们有一个主管负责创建“高级”目标，而代理负责实际的实现。

在实践中，目前，主管应该决定将箱子放在球门位置的顺序。事实上，将一个盒子放在它的目标位置可能会阻塞通往另一个目标的路径。

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

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

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

您能否建议一种快速算法来计算切入位置，并且可能会返回每个切入位置阻挡的目标数量？

4

2 回答 2

3

您所说的网格词的切割位置在一般图形中称为切割顶点或关节点。来自维基百科：

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

在同一篇文章中更进一步：

由 John Hopcroft 和 Robert Tarjan (1973) [1] 提出的用于计算连通无向图中的双连通分量的经典顺序算法以线性时间运行，并且基于深度优先搜索。该算法也被概述为算法介绍（第 2 版和第 3 版）的问题 22-2。

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

于 2013-04-17T17:40:46.193 回答
1

您可以将该区域放入无向图中，其中每个节点是地图的一个位置，如果位置彼此相邻，则两个节点连接。然后，您可以在图表上标记那些“切割位置”，并查看切割位置上的框会阻塞的所有路径。

于 2013-04-17T16:31:30.193 回答