渐进连通分量标号

Question

我用的是一个正方形网格，它有两个状态，"ON“和”OFF“。我有一个相当简单的连通元件标号算法，它查找所有"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);

然而，如果这些更改包含关闭的单元格，我不知道该怎么办。请记住，所有的单元格都必须是一个组的成员。因此，一种解决方案是将每个相邻于新离开单元的单元单元，并查看它们是否相互连接(例如，使用*路径查找)。这将产生1-4个连续的组(除非该单元是其组中唯一的单元，因此有0相邻的单元要检查，在这种情况下，它会产生0组)。然而，这仅仅比从头开始要好一点，因为通常(但并不总是)将这些相邻的方块连接在一起就像找到一个相邻的组一样困难(除非有人有一个聪明的方法来这样做)。而且，如果有很多改变的cells...though，我承认通常没有改变，这样做有点吓人。

上下文，对于那些坚持知道我为什么要这么做的人来说：努里卡比难题中的一个规则是，您可能只有一个连续的墙壁组。一个简单的问题，我正试图解决，以获得更快的速度(和玩寻路)在上面。基本上，我希望检查相邻的墙壁，而不浪费从以前的测试中获得的信息。我试图了解在我的求解器中有多少位置可以利用先前的信息来提高速度，因为当O(f(Δ)算法将足够(N是谜题的大小，Δ是自算法最后运行以来所做的更改)时，使用O(f(N))算法似乎有点痛苦。

分析确实表明，改进该算法将对执行时间产生影响，但这是一个为了乐趣而不是为了利润的项目，因此，除了能够衡量更改是否有任何影响外，这并不重要。

注意:我忽略了解释我当前的算法，但是它基本上是通过在它找到的第一个平方上执行一个基于堆栈的洪水填埋场算法来工作的，然后检查是否有更多的平方(这意味着有多个组，它不去检查)。

编辑:增强思想: 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实例(每种需要增强的匹配类型都要维护一个实例)，并在广场发生更改时对它们进行更新。我需要对此进行基准测试，看看它是否真的有帮助，但它看起来像是用某种内存换取某种速度的标准情况。

Answer 1

这不是一个完整的解决方案，但如下所示：

• 对于每个连接的组件，在内存中保留一个生成树( )
  • 树属性A:我们的生成树有一个关于哪个节点“在上面”的概念(就像在搜索树中)。以上的选择是任意的。

​

• 让我们讨论删除和添加边
• 添加边缘时：
  • 通过检查两个节点的树根是否为相同的，检查它们是否位于同一个组件中
    • 树属性B:树应该是密集的，所以这个检查应该是O(log )。

​

- If in same group then do nothing
- If they are in different groups then join the trees with the new edge.  
    - This would require to transform "the shape" (the definition of who is above who) of one of the trees so our new edge could be "above" it

​

​

• 删除边缘时：
  • 如果这个边不参与一个组的生成树，那么什么也不做。
  • 如果是这样的话，我们需要检查这个组是否仍然是连接的。
    • DFS从一组尝试到达另一组
    • 最好是从两个中较小的那个开始
      • 树属性C:我们为树中的每个节点维护子树的大小
      • 使用属性C，我们可以告诉两个组的大小

​

    - Because of property B: usually the smaller group will be very small and the larger group will be very large
    - If the groups are connected then we act as if we added the connecting edge
    - If the groups are not connected then we should climb the tree to maintain property C (subtract the size of the previously connected subtree from the ancestors' subtree sizes)

​

​

• 问题:我们如何维护属性B(树是密集的)？

我希望这是有意义的:)

Answer 2

这与计算(假设网格上的4连接)在围棋游戏(在日本的Igo)中连接的串是相同的问题，并且递增地这样做是高性能Go播放算法的关键之一。

尽管如此，在这个领域中，同样简单的情况是当您打开一个网格元素(在板上添加一块石头)，因为那时您只能加入以前未连接的组件。有问题的情况是，当您关闭一个网格元素(由于算法中的撤销而移除一块石头)时，就可以将单个组件划分为两个断开连接的组件。

基于我对这个问题的有限理解，我建议您使用union--当您打开一个元素来合并标记的组时，然后在关闭一个网格元素时从头开始重新计算相关的组。为了优化这一点，每当打开和关闭网格元素时，首先处理OFF情况，这样联合查找操作就不会浪费。如果您想要一个更高级的增量算法，您可以开始以增量方式维护每个元素的连接性数据，但是它很可能不会有回报。

Answer 3

有趣的问题！这是我最初的想法。希望我有更多的答案，当他们来的时候我会更新这个答案..。

更新2，因为您只关心一个组，A*搜索似乎是理想的。你分析过A*搜索和重新命名吗？我不得不认为，写得好的A*搜索会比洪水泛滥的速度更快。如果不是，也许您可以发布实际的代码以获得优化帮助？

Update 1如果您知道新关闭的单元格C在组G中，则可以重新运行CCL算法，但只需重新标记组G中的单元格。细胞上的另一个可以保留它们现有的标签。您不必检查网格的其余部分，与整个网格的初始CCL相比，这可能节省了很多费用。(作为一个狂热的Nurikabe解决者，这至少应该是在一个解决的谜题中节省33%，而在一个正在进行中的谜题中，这应该是一个非常大的节省，不是吗？"33%“来自我的猜测，解决了谜题的大约2/3黑色和1/3白色。)

要做到这一点，您必须存储每个组中包含的单元格列表，这样您就可以快速遍历组G中的单元格，并且只重新标记这些单元格。