8

I have a computer science problem that I've been thinking a lot about lately, and I'd be interested to hear other people's feedback:

Let's say you have a 3d blockworld (like minecraft). The world is "stable" if, for any block, there exists a solid path from that block to the bottom-most row of blocks. When the world is generated, it's guaranteed to be stable, but as players go around digging up the blocks, they could make the world unstable. For example, the player could dig out the trunk of a tree, in which case the top of the tree would be hovering in midair, and thus the world is unstable.

The goal is to quickly figure out if the world becomes unstable as the result of a dig, and which cubes should be removed to restore the world to a stable state. The algorithm should be fast and work in the context of a world where many digs are taking place, most of which do not make the world unstable.

One naive approach would be to take each adjacent cube after a dig and find a path to the bottom of the earth. If you can't find a path to the bottom from any of the neighbors, the world is now unstable (and you also learn which cubes to remove as part of the process). This falls apart when the path to the bottom is very long. It's pretty easy to come up with an example where this becomes computationally expensive (Imagine removing the top of a large, winding tower).

This problem can be thought of as a graph problem where you want to quickly detect if a single vertex can divide the graph into two or more components.

I'm interested to hear if anyone has other ideas of ways to make this problem tractable.

4

5 回答 5

5

链接/切割树可能会对您有所帮助。 该结构的作者之一Daniel Sleator分享了他对类似问题的解决方案。查看他在 codeforces.ru 上的评论，您可能会发现它们很有用。

我会在这里写下我的想法。让我们在底层创建一个顶点。该顶点是您建筑物的地下室。将 basement_vertex 与底层的所有顶点连接起来。从地下室顶点运行深度优先搜索 (DFS)。此 dfs 将生成有根树。这棵树应该是一些链接切割树的基础（初始阶段）。

更新

Link-Cut Trees 仅在给定图是树时才有效。对于任何图，我们都必须解决 动态连接问题。 这里 有更多关于动态连接问题的信息。

于 2013-08-07T03:32:56.223 回答
1

如果每个块是“unstable-if-dug”，我会考虑存储，也称为cut-vertex或biconnected component。然后您可以在单击时以恒定时间查找它。

基本上，这个想法是能够立即知道它是否稳定。然后在等待下一个用户输入时重新计算图形。用户体验更流畅，除非有人点击非常快，否则他们永远不会注意到速度变慢。

您可以使用 DFS 在 O(n) 时间内找到所有图形的切割顶点。

来自双连接组件的维基百科：

这个想法是在保持以下信息的同时运行深度优先搜索：

  • 深度优先搜索树中每个顶点的深度（一旦被访问）
  • 对于每个顶点 v，深度优先搜索树中 v 所有后代的邻居的最低深度，称为低点。

v 的低点可以在访问 v ... 的所有后代后计算为 的最小值：

  • v 的深度
  • v 的所有邻居的深度（在深度优先搜索树中 v 的父级旁边）
  • 深度优先搜索树中 v 的所有子节点的低点。

关键事实是，当且仅当存在这样的子节点时，非根顶点 v 是分隔两个双连通分量的切割顶点（或关节y点v）lowpoint(y) ≥ depth(v)。

根顶点必须单独处理：当且仅当它至少有两个孩子时，它才是切割顶点。

于 2013-08-07T21:09:27.760 回答
0

您可以考虑所谓的Flood-fill算法，对节点进行标记并查看成员资格是否相同。

这是一个简单的图表。我们有原始图 G，然后我们分别移除一个立方体以获得图 H 和 I。

在此处输入图像描述

该igraph软件包非常适合测试图形连接性。在上面的测试示例中，G 和 H 都可以，但是去除边 (3,5) 会导致 5, 6,7 的成员资格与节点 1（“地球节点”）的成员资格不同。（所以在第三张图，图 I 中，您应该删除立方体 5、6 和 7。）

在 R 语言中，使用 igraph 库

library(igraph)
edges <- c(c(1,2), c(2,3), c(2,4), c(3,5), c(5,6), c(5,7), c(6,7))
g<- graph(edges, directed=FALSE)
clusters(g)$membership  # 1 1 1 1 1 1 1

edges <- c(c(1,2), c(2,3), c(2,4), c(3,5), c(5,6), c(5,7)) # drop edge(6,7)
h<- graph(edges, directed=FALSE)
clusters(h)$membership # 1 1 1 1 1 1 1


edges <- c(c(1,2), c(2,3), c(2,4), c(5,6), c(5,7), c(6,7)) # drop (3,5)
i<- graph(edges, directed=FALSE)
clusters(i)$membership # 1 1 1 1 2 2 2

clusters是 igraph 包自带的一个函数。它的membership值显示了图中每个节点的标签。如果任何节点（在您的情况下为立方体）具有与“地球节点”不同的成员值，则它没有连接到地面，应该被移除。

于 2013-08-07T04:23:33.510 回答
0

一个简单的解决方案是使用 BFS（广度优先搜索）来检查被移除节点（minecraft 块）的所有直接邻居是否属于同一个连接组件。

第一个邻居被标记，然后检查所有其他邻居是否连接到某个标记节点。

这是我测试过的代码（C#）：

public bool CanRemoveNode(int indexNode)
{
    var initialNeighbors = this.nodeNeighbors[indexNode];

    if (initialNeighbors.Count() < 2)
    {
        // leaf node - can be safely removed
        return true;
    }

    HashSet<int> nodesComponent = new HashSet<int>(initialNeighbors.Take(1));
    HashSet<int> nodesProcessed = new HashSet<int>();
    Queue<int> nodesVisit = new Queue<int>();

    foreach (int indexNodeStart in initialNeighbors.Skip(1))
    {
        nodesProcessed.Clear();

        nodesVisit.Clear();
        nodesVisit.Enqueue(indexNodeStart);

        while (nodesVisit.Any())
        {
            int indexNodeCurrent = nodesVisit.Dequeue();

            nodesProcessed.Add(indexNodeCurrent);
            nodesComponent.Add(indexNodeCurrent);

            foreach (int indexNodeNeighbor in this.nodeNeighbors[indexNodeCurrent])
            {
                    if (indexNodeNeighbor == indexNode)
                    {
                        // do not inspect removed node
                        continue;
                    }

                    if (nodesProcessed.Contains(indexNodeNeighbor))
                    {
                        // neighbor node already processed
                        continue;
                    }

                    if (nodesComponent.Contains(indexNodeNeighbor))
                    {
                        // neighbor node belongs to the component - we can terminate search
                        goto NextStartNode;
                    }

                    // mark neighbor node for further inspection
                    nodesVisit.Enqueue(indexNodeNeighbor);
            }
        }

        return false;

        NextStartNode:
        ;
    }

    return true;
}

'nodeNeighbors' 字典包含每个节点的邻居索引。

在最坏的情况下，我们需要运行与任意两个直接相邻节点之间的最长路径长度一样多的 BFS 迭代。

一种更快的方法是用唯一的数字标签标记每个直接邻居，然后执行连接组件标记。我们可以对每个标签运行并行 BFS 搜索，并在两个标签相遇时终止，并对底层的 Union-Find 结构执行联合操作。

当执行的联合操作与初始标签减一一样多时，整个搜索可以终止，即所有标签属于同一组件。

另一个速度改进是创建多个均匀分布在移除点周围的“种子”。每个种子都是一个具有唯一标签的节点。这保证了组件将更快地连接成一个。

您也可以在经过一定次数的迭代（例如 10 000 次）后终止搜索，因为这意味着立方体连接的距离非常远，玩家甚至不会发现有断开连接。

此后，也可以在后台执行搜索。

于 2016-07-13T11:36:21.703 回答
0

检查下面的代码，graphA 已损坏而 graphB 未损坏，isGraphBroken 方法会为您检查，甚至告诉您调用堆栈有多少，以及哪些节点与其他节点损坏：

let graphA = [
  ['A', 'B'],
  ['C', 'D'],
  ['D', 'E']
];

let graphB = [
  ['A', 'B'],
  ['B', 'C'],
  ['C', 'D'],
  ['D', 'E']
];
        
function isGraphBroken(graph) {
    let map = new Map();
    let allNodes = new Set();
    let callStack = 0;

    graph.forEach(([x, y]) => {
        allNodes.add(x);
        allNodes.add(y);
        callStack++;
        if (map.has(x)) {
            map.get(x).add(y);
        } else {
            map.set(x, new Set([y]));
        }

        if (map.has(y)) {
            map.get(y).add(x);
        } else {
            map.set(y, new Set([x]));
        }
    });

    if (allNodes.size <= 1) {
        console.log("there is a way between each node pairs");
        return false;
    } 
    
    let traverseNode = (node => {
        callStack++;
        if (allNodes.size == 0) {
            return;
        }

        if (allNodes.has(node))
            allNodes.delete(node);

        if (allNodes.size == 0) {
            return;
        }

        let childs = map.get(node);
        if (childs && childs.size > 0)
            childs.forEach(child => {
                if (allNodes.has(child)) {
                    traverseNode(child);
                }
            });
    });

    traverseNode(allNodes.values().next().value);

     console.log("callstack length", callStack);
    if (allNodes.size == 0) {
        console.log("there is a way between each node pairs");
        return false;
    }
    console.log("no way from these nodes to others:", ...allNodes);
    return true;

}

console.log("checking ... graphA:")
isGraphBroken(graphA);
console.log("checking ... graphB:")
isGraphBroken(graphB);

于 2020-10-11T04:48:46.260 回答