algorithm - 渐进式连通分量标记

Question

我正在使用具有两种状态“ON”和“OFF”的正方形网格。我有一个相当简单的 Connected Component Labeling找到所有“ON”组件的算法。通常，但并非总是如此，只有一个“ON”组件。

我希望构建一个算法，它将开/关单元格矩阵、组件标签(可能格式化为单元格哈希集列表)以及自标签形成以来发生变化的单元格列表作为输入, 并输出一个新的标签。显而易见的解决方案是从头开始重新计算，但效率不高。一般来说，已更改的单元格列表会很小。

如果更改列表只有已打开的单元格，这很容易做到:

Groups G;
Foreach changed cell C:
  Group U = emptygroup;
  U.add(C);
  Foreach Group S in G:
    if (S contains a cell which is adjacent to C)
      G.Remove(S);
      U.UnionWith(S);
  G.add(C);

但是，如果更改包含任何已关闭的单元格，我不确定该怎么做。请记住，所有 ON 单元格必须恰好是一个组的成员。因此，一种解决方案是获取与新 OFF 单元格相邻的每个单元格，看看它们是否相互连接(例如使用 * 寻路)。这将产生 1-4 个连续的组(除非该单元格是其组中唯一的单元格，因此有 0 个相邻单元格要检查，在这种情况下它会产生 0 个组)。然而，这只比从头开始好一点，因为通常(但不总是)将这些相邻的方 block 连接在一起就像找到一个连续的组一样困难(除非有人提出了一个聪明的方法来做到这一点)。此外，如果有很多变化的细胞，这样做会有点可怕……尽管我承认通常不会。

上下文，对于那些坚持要知道我为什么这样做的人: Nurikabe 中的一条规则难题是您可能只有一组连续的墙。上面是我试图解决的问题的简化，以提高速度(并玩寻路)。基本上，我希望在不浪费从以前的此类测试中获得的信息的情况下检查是否有连续的墙。我想看看我的求解器中有多少地方可以利用以前的信息来提高速度，因为在 O(f(Δ)) 时使用 O(f(N)) 算法似乎有点痛苦算法就足够了(N 是拼图的大小，Δ 是自上次运行算法以来所做的更改)。

分析确实表明改进该算法将对执行时间产生影响，但这是一个有趣而不是盈利的项目，所以它并不重要，除了能够衡量变化是否有任何影响。

注意: 我没有解释我当前的算法，但它基本上是通过基于堆栈的 Flood Fill 来工作的。算法在它找到的第一个 ON 方 block 上，然后检查是否还有更多 ON 方 block (这意味着有多个组，它不会费心去检查)。

编辑:增强的想法:Yairchu 和 John Kugelman 的建议在我的脑海中具体化为这个改进，这实际上并不是解决这个问题本身的方法，但可能会使这部分代码和其他几段代码运行得更快:

当前循环:

foreach (Square s in m.Neighbors[tmp.X][tmp.Y])    
{
    if (0 != ((byte)(s.RoomType) & match) && Retval.Add(s)) curStack.Push(s);
}

改进思路:

foreach (Square s in m.NeighborsXX[tmp.X][tmp.Y])    
{
    if (Retval.Add(s)) curStack.Push(s);
}

这将需要维护多个 m.NeighborsXX 实例(每个实例对应需要增强的每种匹配类型)并在方 block 发生变化时更新它们。我需要对此进行基准测试，看看它是否真的有帮助，但它看起来像是用一些内存换取一些速度的标准案例。

Answer 1

不是一个完整的解决方案，但这里是:

• 为每个连接的组件在内存中保留一棵生成树
  • 树属性 A:我们的生成树有一个概念，即哪个节点在哪个节点“之上”(就像在搜索树中一样)。选择哪个在哪个上面随意
• 让我们讨论删除和添加边
• 添加边时:
  • 通过检查树的根是否相同来检查两个节点是否在同一组件中
    • 树属性 B:树应该是密集的，所以这个检查是 O(log n)
  • 如果在同一组，则什么也不做
  • 如果他们在不同的组中，则用新边加入树。
    • 这将需要转换其中一棵树的“形状”(定义谁在谁之上)，以便我们的新边缘可以在它“之上”
• 删除边缘时:
  • 如果这条边不参与组的生成树，则什么也不做。
  • 如果是，我们需要检查该组是否仍然连接
    • 一组的 DFS 尝试影响另一组
    • 最好从两者中较小的一个开始
      • 树属性 C:我们为树中的每个节点维护其子树的大小
      • 使用属性 C 我们可以知道两个组的大小
    • 因为属性B:通常较小的群体会非常小而较大的群体会非常大
    • 如果这些组是连接的，那么我们就好像添加了连接边一样
    • 如果组没有连接，那么我们应该爬树以保持属性 C(从祖先的子树大小中减去先前连接的子树的大小)
• 问题:我们如何保持属性 B(树很密集)？

我希望这是有道理的:)